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

Negative cycle finder for weighted directed graphs.

Template parameters
DiGraph

Type of the directed graph, must provide:

  • key_type for vertex identification
  • begin()/end() for vertex iteration
  • at(vertex) for adjacency list access

This class implements an efficient algorithm for detecting negative cycles in weighted directed graphs. Unlike Bellman-Ford algorithm, this approach:

  • Does not require a source node
  • Can detect negative cycles during the relaxation process
  • Maintains distance information across iterations
  • Provides the actual negative cycle path

The algorithm is particularly useful in network optimization problems where negative cycle detection is a core operation.

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 a negative cycle in the graph.

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 a negative cycle in the graph.

Template parameters
Mapping Type of distance mapping (vertex -> distance)
Callable Type of weight function (edge -> weight)
Parameters
dist in/out Distance mapping that gets updated during relaxation
get_weight in Function to get edge weights
Returns Cycle A vector of edges forming the negative cycle, empty if none found

This is the main method that searches for negative cycles. It performs edge relaxations repeatedly and checks for cycles in the predecessor graph after each relaxation phase.

The algorithm continues until either:

  • No more relaxations are possible (no negative cycles)
  • A negative cycle is found and returned