min_cycle_ratio.hpp File Reference

Minimum cost-to-time cycle ratio problem solver. More...

#include <algorithm>
#include <py2cpp/py2cpp.hpp>
#include "parametric.hpp"

Include dependency graph for min_cycle_ratio.hpp:

Go to the source code of this file.

Functions
template<typename Graph , typename T , typename Fn1 , typename Fn2 , typename Mapping >
auto	min_cycle_ratio (const Graph &gra, T &r0, Fn1 &&get_cost, Fn2 &&get_time, Mapping &&dist, size_t max_iters=1000)
	Solve the minimum cost-to-time cycle ratio problem.

Detailed Description

Minimum cost-to-time cycle ratio problem solver.

This module implements an algorithm to find the minimum cycle ratio in a weighted directed graph where each edge has both a cost and a time value. The cycle ratio is defined as the total cost divided by the total time.

The problem formulation: max r s.t. dist[vtx] - dist[utx] ≥ cost(utx, vtx) - r * time(utx, vtx) ∀ edge(utx, vtx) ∈ gra(V, E)

This is equivalent to finding the cycle with minimum cost/time ratio. The algorithm uses a parametric search approach combined with negative cycle detection via Howard's method. Edge weights are accessed using the graph's native edge data type (the "get_weight" method).

Function Documentation

min_cycle_ratio()

template<typename Graph , typename T , typename Fn1 , typename Fn2 , typename Mapping >

auto min_cycle_ratio	(	const Graph &	gra,
		T &	r0,
		Fn1 &&	get_cost,
		Fn2 &&	get_time,
		Mapping &&	dist,
		size_t	max_iters = 1000
	)

Solve the minimum cost-to-time cycle ratio problem.

This function finds the cycle in a graph that minimizes the ratio of total cost to total time. It uses a parametric search algorithm that iteratively adjusts the ratio parameter and searches for negative cycles using Howard's method.

The algorithm works by:

1. Converting the ratio problem to a parametric weight problem
2. Using Howard's negative cycle detection to find violating cycles
3. Adjusting the ratio based on the found cycles
4. Repeating until convergence

Given a directed graph \(G = (V, E)\) with cost and time on each edge, the minimum cycle ratio problem finds:

\[ r^* = \min_{C \in \text{cycles}(G)} \frac{\sum_{e \in C} \text{cost}(e)}{\sum_{e \in C} \text{time}(e)} \]

The algorithm uses parametric weights \(w_r(e) = \text{cost}(e) - r \cdot \text{time}(e)\) and searches for the smallest \(r\) such that no negative cycles exist.

Template Parameters

Graph	Type of the graph, must provide key_type and edge iteration
T	Numeric type for ratio values (e.g., double, Fraction)
Fn1	Type of cost function (edge_data -> cost)
Fn2	Type of time function (edge_data -> time)
Mapping	Type of distance mapping (vertex -> distance)

Parameters

[in]	gra	The input graph
[in,out]	r0	Initial ratio value, updated with optimal result
[in]	get_cost	Function to extract cost from edge data
[in]	get_time	Function to extract time from edge data
[in,out]	dist	Distance mapping used in the algorithm
[in]	max_iters	Maximum number of iterations (default: 1000)

Returns

auto A cycle (vector of native edge data) with the minimum ratio