digraphx/min_cycle_ratio.hpp file

Minimum cycle ratio algorithms for directed graphs.

This module provides algorithms for finding the minimum cycle ratio in directed graphs, which is a fundamental problem in graph theory with applications in performance analysis, scheduling, and discrete event systems.

The cycle ratio of a cycle is defined as: ratio(cycle) = sum(costs) / sum(times)

Problem formulation:

min  ratio(cycle)
s.t. cycle is a directed cycle in G(V, E)

Key applications:

  • Performance analysis of digital circuits
  • Scheduling and resource allocation
  • Network flow optimization
  • Timing analysis in real-time systems
  • Economic equilibrium problems

Example cycle ratio calculation:

 a ----2----> b
 |           |
1|           |3
 |           |
 v     4     v
 c ---------> d

 For cycle a->b->d->c->a with costs [2, 3, 4, 1] and times [1, 1, 1, 1]:
 ratio = (2 + 3 + 4 + 1) / (1 + 1 + 1 + 1) = 10 / 4 = 2.5

Algorithm approach:

  • Transforms to parametric problem: max r s.t. cost(e) - r * time(e) >= 0
  • Uses Howard's method for negative cycle detection
  • Iteratively adjusts parameter r until convergence

Performance characteristics:

  • Time complexity: O(V * E * log(C)) where C is the ratio range
  • Space complexity: O(V + E)
  • Efficient for sparse graphs with tight cycles

Classes

template<typename DiGraph, typename Ratio>
class MinCycleRatioSolver
Minimum Cycle Ratio Solver.

Functions

template<typename DiGraph, typename Ratio, typename Fn1, typename Fn2, typename Mapping, typename Domain>
auto min_cycle_ratio(const DiGraph& digraph, Ratio& r0, Fn1&& get_cost, Fn2&& get_time, Mapping& dist, Domain dummy) -> auto
Free function for minimum cost-to-time cycle ratio problem.

Function documentation

template<typename DiGraph, typename Ratio, typename Fn1, typename Fn2, typename Mapping, typename Domain>
auto min_cycle_ratio(const DiGraph& digraph, Ratio& r0, Fn1&& get_cost, Fn2&& get_time, Mapping& dist, Domain dummy)

Free function for minimum cost-to-time cycle ratio problem.

Template parameters
DiGraph Type of the directed graph representation
Ratio Type representing ratio values
Fn1 Type of cost extraction function
Fn2 Type of time extraction function
Mapping Type of distance mapping (node -> distance)
Domain Type of the domain for distance calculations
Parameters
digraph in The directed graph to analyze
r0
get_cost in Function to extract cost from an edge
get_time in Function to extract time from an edge
dist in/out Distance mapping updated during execution
dummy in Parameter for type deduction
Returns Cycle The cycle achieving the minimum ratio

This function provides a functional interface for solving the minimum cycle ratio problem without requiring explicit class instantiation. It solves the parametric network problem:

max  r
s.t. dist[vtx] - dist[utx] ≥ cost(utx, vtx) - r * time(utx, vtx)
     ∀ edge(utx, vtx) ∈ G(V, E)

The function uses the same algorithmic approach as MinCycleRatioSolver but with a more flexible callback-based interface. This is particularly useful when:

  • Edge data is stored in custom formats
  • Cost and time extraction requires complex logic
  • You prefer functional programming style
  • Integration with existing callback-based code

Algorithm details:

  1. Transforms MCR to parametric problem
  2. Uses binary search on parameter r
  3. Employs Howard's method for negative cycle detection
  4. Iteratively refines the minimum ratio estimate

Usage example:

// Define cost and time extraction functions
auto get_cost = [](const Edge& e) { return e["cost"]; };
auto get_time = [](const Edge& e) { return e["time"]; };

// Initialize distances
std::unordered_map<Node, double> dist;
for (const auto& [node, _] : graph) dist[node] = 0.0;

// Find minimum cycle ratio
double ratio = 0.0;  // initial estimate
auto cycle = min_cycle_ratio(graph, ratio, get_cost, get_time, dist, 0.0);