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

Negative Cycle Finder by Howard's method.

Template parameters
DiGraph

Negative cycle detection for weighed graphs.

Howard's method is a minimum cycle ratio (MCR) algorithm that uses a policy iteration algorithm to find the minimum cycle ratio of a directed graph. The algorithm maintains a set of candidate cycles and iteratively updates the cycle with the minimum ratio until convergence. To detect negative cycles, Howard's method uses a cycle detection algorithm that is based on the Bellman-Ford relaxation algorithm. Specifically, the algorithm maintains a predecessor graph of the original graph and performs cycle detection on this graph using the Bellman-Ford relaxation algorithm. If a negative cycle is detected, the algorithm terminates and returns the cycle.

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

  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

Public functions

template<typename Mapping, typename Callable>
auto howard(Mapping& dist, Callable get_weight) -> cppcoro::generator< Cycle > -> auto

Function documentation

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

Parameters
gra in The gra parameter is of type DiGraph and represents a directed graph. It is used to initialize the _digraph member variable of the NegCycleFinder class.

The constructor initializes a NegCycleFinder object with a given DiGraph object.

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

Template parameters
Mapping
Callable
Parameters
dist in/out A mapping object that stores the distances between vertices in the graph.
get_weight in The get_weight parameter is a callable object that is used to retrieve the weight of an edge in the graph. It takes in two arguments: the source vertex and the destination vertex of the edge, and returns the weight of the edge.

The function "howard" finds a negative cycle in a graph using the Howard's algorithm.