template<typename DiGraph, typename Domain>
NegCycleFinderQ class

Negative Cycle Finder with constraints by Howard's method.

Negative cycle detection for weighed graphs with constraints.

// Example of constraint-based negative cycle detection
+-----> a ------+
|      |       |
|      | -1    | 2
|      |       | (with constraint: dist[a] - dist[b] <= 1)
|      v       |
|     b -------> c
|     |  -2     |
|     |         | (with constraint: dist[c] - dist[b] <= 2)
|     +-----><--+
|          1
+---- -3 (weight)

This class implements both predecessor and successor versions of Howard's algorithm for negative cycle detection in directed graphs with constraints.

Predecessor version (pred):
    a <----- b
    |       |
    +--> c <-+
    
Successor version (succ):
    a -----> b
    |       |
    v       v
    d <----- e

Constructors, destructors, conversion operators

NegCycleFinderQ(const DiGraph& digraph) explicit: Initialize the negative cycle finder with a directed graph.

Public functions

template<typename Mapping, typename GetWeight, typename UpdateOk> auto howard_pred(Mapping& dist, GetWeight&& get_weight, UpdateOk&& update_ok) -> cppcoro::generator< Cycle > -> auto: Find negative cycles using predecessor-based Howard's algorithm.
template<typename Mapping, typename GetWeight, typename UpdateOk> auto howard_succ(Mapping& dist, GetWeight&& get_weight, UpdateOk&& update_ok) -> cppcoro::generator< Cycle > -> auto: Find negative cycles using successor-based Howard's algorithm.

Function documentation

template<typename DiGraph, typename Domain>
NegCycleFinderQ<DiGraph, Domain>::NegCycleFinderQ(const DiGraph& digraph) explicit

Initialize the negative cycle finder with a directed graph.

Parameters
digraph	A directed graph represented as a nested mapping

template<typename DiGraph, typename Domain> template<typename Mapping, typename GetWeight, typename UpdateOk>
auto NegCycleFinderQ<DiGraph, Domain>::howard_pred(Mapping& dist, GetWeight&& get_weight, UpdateOk&& update_ok) -> cppcoro::generator< Cycle >

Find negative cycles using predecessor-based Howard's algorithm.

Template parameters
Mapping	Distance mapping type
GetWeight	Callable type for getting edge weights
UpdateOk	Callable type for update constraint
Parameters
dist	Initial distance estimates (often zero-initialized)
get_weight	Function to get weight of an edge
update_ok	Function to determine if distance updates are allowed
Returns	cppcoro::generator<Cycle> Each negative cycle found as a list of edges

template<typename DiGraph, typename Domain> template<typename Mapping, typename GetWeight, typename UpdateOk>
auto NegCycleFinderQ<DiGraph, Domain>::howard_succ(Mapping& dist, GetWeight&& get_weight, UpdateOk&& update_ok) -> cppcoro::generator< Cycle >

Find negative cycles using successor-based Howard's algorithm.

Template parameters
Mapping	Distance mapping type
GetWeight	Callable type for getting edge weights
UpdateOk	Callable type for update constraint
Parameters
dist	Initial distance estimates (often zero-initialized)
get_weight	Function to get weight of an edge
update_ok	Function to determine if distance updates are allowed
Returns	cppcoro::generator<Cycle> Each negative cycle found as a list of edges

template<typename DiGraph, typename Domain> NegCycleFinderQ class