digraphx/neg_cycle_q.hpp file

Negative cycle detection with constraints using Howard's method.

This module extends the basic negative cycle detection to support constrained optimization problems. It implements both predecessor and successor versions of Howard's algorithm, allowing for more flexible cycle detection strategies.

Key features:

• Support for distance update constraints via callback functions
• Both predecessor-based and successor-based algorithms
• Flexible constraint handling for complex optimization problems
• Generator-based cycle enumeration for memory efficiency

Constraint types supported:

• Upper bounds on distance updates
• Lower bounds on distance updates
• Custom constraint functions
• Domain-specific validation rules

Example usage with constraints:

// Define a graph
std::unordered_map<int, std::unordered_map<int, double>> graph = {
    {0, {{1, 2.0}, {2, 3.0}}},
    {1, {{2, -5.0}}},
    {2, {{0, 1.0}}}
};

// Create constrained cycle finder
NegCycleFinderQ finder(graph);

// Define constraint: only allow updates that improve by at least 0.1
auto update_ok = [](double old_val, double new_val) {
    return new_val < old_val - 0.1;
};

// Initialize distances
std::unordered_map<int, double> dist = {{0, 0.0}, {1, 0.0}, {2, 0.0}};

// Find cycles with predecessor-based algorithm
for (const auto& cycle : finder.howard_pred(dist,
        [](const auto& edge) { return edge; }, update_ok)) {
    std::cout << "Found constrained negative cycle\n";
}

Performance characteristics:

• Time complexity: O(V * E * C) where C is constrained by update_ok
• Space complexity: O(V + E) for predecessor/successor mappings
• Constraints can significantly reduce search space

Classes

template<typename DiGraph, typename Domain>

class NegCycleFinderQ

Negative Cycle Finder with constraints using Howard's method.