#include <digraphx/min_cycle_ratio.hpp>
template<typename DiGraph, typename Ratio>
MinCycleRatioSolver class

Minimum Cycle Ratio Solver.

Template parameters
DiGraph Type of the directed graph representation
Ratio Type representing ratio values (typically double)

This class provides algorithms for solving the minimum cycle ratio (MCR) problem in directed graphs. The MCR problem seeks to find the cycle with the minimum ratio of total cost to total time, which is crucial for analyzing performance characteristics of discrete event systems.

Problem definition:

min  (sum(costs) / sum(times))
s.t. cycle is a directed cycle in G(V, E)

Algorithm approach: The solver transforms the MCR problem into a parametric problem:

max  r
s.t. dist[v] - dist[u] >= cost(u,v) - r * time(u,v)
     for all edges (u,v) in G

Key insights:

  • A cycle has ratio ≤ r iff cost - r*time has negative cycle
  • Binary search on r with negative cycle detection
  • Uses Howard's method for efficient cycle detection
  • Converges to optimal minimum cycle ratio

Applications:

  • Digital circuit performance analysis
  • Real-time system scheduling
  • Communication network optimization
  • Manufacturing system analysis
  • Economic equilibrium computation

Constructors, destructors, conversion operators

MinCycleRatioSolver(const DiGraph& digraph) explicit

Public functions

template<typename Mapping, typename Domain>
auto run(Ratio& r0, Mapping& dist, Domain dummy) -> Cycle -> auto
run

Function documentation

template<typename DiGraph, typename Ratio>
MinCycleRatioSolver<DiGraph, Ratio>::MinCycleRatioSolver(const DiGraph& digraph) explicit

Parameters
digraph in The parameter "digraph" is of type DiGraph, which is a directed graph. It is used to represent the graph on which the Min Cycle Ratio Solver operates.

This function constructs a new MinCycleRatioSolver object with a given DiGraph.

template<typename DiGraph, typename Ratio> template<typename Mapping, typename Domain>
auto MinCycleRatioSolver<DiGraph, Ratio>::run(Ratio& r0, Mapping& dist, Domain dummy) -> Cycle

run

Template parameters
Mapping
Domain
Parameters
r0 in Initial and final minimum ratio estimate
dist in Distance mapping that gets updated during execution
dummy in Parameter for type deduction
Returns Cycle The cycle achieving the minimum ratio