#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.
- BF needs a source node.
- BF detect whether there is a negative cycle at the fianl stage.
- 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 |