digraphx/neg_cycle.hpp file

Negative cycle detection for weighted directed graphs.

This module implements Howard's method for efficient negative cycle detection in directed graphs. It provides a policy iteration algorithm that maintains candidate cycles and iteratively updates them until convergence.

Key features:

• Efficient negative cycle detection without requiring a source node
• Policy iteration approach for faster convergence
• Generator-based cycle enumeration for memory efficiency
• Template-based design for various graph representations

Example usage:

// Define a directed graph with weighted edges
std::unordered_map<int, std::unordered_map<int, double>> graph = {
    {0, {{1, 2.0}, {2, 3.0}}},
    {1, {{2, -5.0}}},  // Creates negative cycle 0->1->2->0
    {2, {{0, 1.0}}}
};

// Create negative cycle finder
NegCycleFinder finder(graph);

// Initialize distances (typically all zeros)
std::unordered_map<int, double> dist;
for (const auto& [node, _] : graph) {
    dist[node] = 0.0;
}

// Find negative cycles
for (const auto& cycle : finder.howard(dist, [](const auto& edge) { return edge; })) {
    std::cout << "Found negative cycle with " << cycle.size() << " edges\n";
}

Performance characteristics:

• Time complexity: O(V * E * C) where C is the number of policy iterations
• Space complexity: O(V + E) for storing predecessor information
• Typically faster than Bellman-Ford for dense graphs with many cycles

Classes

template<typename DiGraph>

class NegCycleFinder

Negative Cycle Finder using Howard's policy iteration method.