Template Function max_parametric

Function Documentation

template<typename Graph, typename T, typename Fn1, typename Fn2, typename Container>
auto max_parametric(const Graph &G, T &r_opt, Fn1 &&d, Fn2 &&zero_cancel, Container &&dist, size_t max_iter = 1000)

maximum parametric problem

This function solves the following network parametric problem: 

max  r
s.t. dist[v] - dist[u] \ge d(u, v, r)
     \forall e(u, v) \in G(V, E)

Template Parameters

  • Graph –

  • T –

  • Fn1 –

  • Fn2 –

  • Container –

Parameters

  • G – [in] directed graph

  • r_opt – [inout] parameter to be maximized, initially a large number

  • d – [in] monotone decreasing function w.r.t. r

  • zero_cancel – [in]

  • dist – [inout]

Returns

optimal r and the critical cycle