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

Negative Cycle Finder using Howard's policy iteration method.

Template parameters
DiGraph Type of the directed graph representation

This class implements Howard's algorithm for efficient negative cycle detection in directed graphs. Unlike traditional Bellman-Ford approaches, Howard's method uses policy iteration to maintain a set of candidate cycles and iteratively improves them until convergence.

Algorithm overview:

  1. Initialize a policy (predecessor mapping)
  2. Perform relaxation steps to improve the policy
  3. Detect cycles in the current policy graph
  4. Verify if detected cycles are negative
  5. Yield negative cycles and continue until no improvements possible

Advantages over Bellman-Ford:

  • No source node required
  • Detects negative cycles during iteration, not just at the end
  • Reuses previous distance estimates instead of restarting
  • Often faster for graphs with many negative cycles

Template requirements for DiGraph:

  • Must be iterable with begin()/end()
  • Each element must be a pair: (node, neighbors_mapping)
  • neighbors_mapping must be iterable with begin()/end()
  • Each neighbor must be a pair: (target_node, edge_data)

Constructors, destructors, conversion operators

NegCycleFinder(const DiGraph& digraph) explicit
Construct a Negative Cycle Finder for the given graph.

Public functions

template<typename Mapping, typename Callable>
auto howard(Mapping& dist, const Callable& get_weight) -> cppcoro::generator< Cycle > -> auto
Execute Howard's algorithm to find negative cycles.

Function documentation

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

Construct a Negative Cycle Finder for the given graph.

Parameters
digraph in The directed graph to search for negative cycles

Creates a new NegCycleFinder instance that will operate on the provided directed graph. The graph is stored by reference, so it must remain valid for the lifetime of the NegCycleFinder object.

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

Execute Howard's algorithm to find negative cycles.

Template parameters
Mapping Type of the distance mapping (node -> distance)
Callable Type of the weight extraction function
Parameters
dist in/out Initial and updated distance estimates
get_weight in Function to extract weight from an edge
Returns cppcoro::generator<Cycle> Generator yielding negative cycles

This is the main method that implements Howard's policy iteration algorithm for negative cycle detection. It repeatedly performs relaxation steps and cycle detection until no more negative cycles can be found.

Algorithm flow:

  1. Clear predecessor mapping (start fresh)
  2. While relaxation makes changes and no negative cycles found: a. Perform relaxation step to improve policy b. Search for cycles in current policy graph c. For each cycle found, verify it's negative d. Yield all negative cycles found

The method uses a generator to efficiently return cycles as they are found, avoiding the need to store all cycles simultaneously.