#include <netoptim/neg_cycle.hpp>
template<typename DiGraph>
NegCycleFinder class

negative cycle

Template parameters
DiGraph Note: Bellman-Ford's shortest-path algorithm (BF) is NOT the best way to detect negative cycles, because

Negative cycle detection for weighed graphs.

  1. BF needs a source node.
  2. BF detect whether there is a negative cycle at the fianl stage.
  3. BF restarts the solution (dist[utx]) every time.

Constructors, destructors, conversion operators

NegCycleFinder(const DiGraph& gra) explicit
Construct a new neg Cycle Finder object.

Public functions

template<typename Mapping, typename Callable>
auto find_neg_cycle(Mapping&& dist, Callable&& get_weight) -> Cycle -> auto
find negative cycle

Function documentation

template<typename DiGraph>
NegCycleFinder<DiGraph>::NegCycleFinder(const DiGraph& gra) explicit

Construct a new neg Cycle Finder object.

Parameters
gra in

template<typename DiGraph> template<typename Mapping, typename Callable>
auto NegCycleFinder<DiGraph>::find_neg_cycle(Mapping&& dist, Callable&& get_weight) -> Cycle

find negative cycle

Template parameters
Mapping
Callable
Parameters
dist in/out
get_weight in
Returns Cycle