parametric.hpp File Reference

Maximum parametric problem solver for network optimization. More...

#include <digraphx/neg_cycle.hpp>
#include <type_traits>
#include <vector>

Include dependency graph for parametric.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
template<typename Graph , typename T , typename Fn1 , typename Fn2 , typename Mapping >
auto	max_parametric (const Graph &gra, T &r_opt, Fn1 &&distrance, Fn2 &&zero_cancel, Mapping &&dist, size_t max_iters=1000)
	Solve the maximum parametric problem.

Detailed Description

Maximum parametric problem solver for network optimization.

This module implements a general algorithm for solving parametric network optimization problems. The algorithm finds the maximum parameter value r such that a system of inequalities holds, which is equivalent to finding the most violated cycle in a weighted graph.

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

This is a fundamental building block for many network optimization algorithms including minimum cycle ratio, minimum mean cycle, and other parametric flow problems.

Edge weights are accessed via a callable that receives the actual edge data object from the graph's adjacency structure (the "get_weight" method), rather than synthesized (u,v) node pairs. This eliminates the duplication present in the previous node-pair-based approach and matches the Python sibling implementation.

Function Documentation

max_parametric()

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

auto max_parametric	(	const Graph &	gra,
		T &	r_opt,
		Fn1 &&	distrance,
		Fn2 &&	zero_cancel,
		Mapping &&	dist,
		size_t	max_iters = 1000
	)

Solve the maximum parametric problem.

This function implements an iterative algorithm to find the maximum parameter value r for which the system of constraints is feasible. The algorithm uses Howard's policy iteration for negative cycle detection to identify violations and adjusts the parameter accordingly.

The algorithm proceeds as follows:

1. For the current parameter value, compute edge weights via the distance callable operating on the graph's native edge data
2. Find negative cycles using Howard's method
3. If no negative cycles exist, the current parameter is optimal
4. Otherwise, compute a new parameter value from the violating cycle using the zero_cancel callable
5. Repeat until convergence or max_iters reached

The parametric problem is defined as:

\[ \max \; r \quad \text{s.t.} \quad d_v - d_u \ge w(u, v, r) \; \forall (u, v) \in E \]

where \(w(u, v, r)\) is a monotone decreasing function of \(r\). The algorithm finds the maximum \(r\) such that no negative cycles exist.

Template Parameters

Graph	Type of the directed graph
T	Numeric type for the parameter r
Fn1	Type of the distance function (parameter, edge) -> weight
Fn2	Type of the zero-canceling function (cycle) -> parameter
Mapping	Type of distance mapping (vertex -> distance)

Parameters

[in]	gra	directed graph containing the network structure
[in,out]	r_opt	parameter to be maximized, updated with optimal value
[in]	distrance	monotone decreasing function of parameter r
[in]	zero_cancel	function to compute new parameter from cycle
[in,out]	dist	distance mapping used in the algorithm
[in]	max_iters	maximum number of iterations (default: 1000)

Returns

auto the critical cycle that determines the optimal parameter