discrete_modulus::detail Namespace Reference

Functions
FlowEdge	add_capacity_edge (FlowGraph &fg, FlowVertex u, FlowVertex v, long capacity)
	Adds a directed capacity edge u -> v to fg, along with its required zero-capacity reverse-residual companion v -> u.
std::pair< long, std::set< Edge > >	solve_subproblem (Graph &g, FlowContext &ctx, const Edge &e, long q)
	One max-flow step of Cunningham's algorithm: how far can x be increased on edge e without leaving the polymatroid P(qf)?

Function Documentation

add_capacity_edge()

FlowEdge discrete_modulus::detail::add_capacity_edge ( FlowGraph &  fg, FlowVertex  u, FlowVertex  v, long  capacity  )

inline

Adds a directed capacity edge u -> v to fg, along with its required zero-capacity reverse-residual companion v -> u.

boost::push_relabel_max_flow requires every "real" capacity edge to have its own dedicated reverse companion. Representing an undirected edge's capacity (which should be usable in either direction) therefore takes two calls to this function – one per direction – i.e. 4 underlying FlowGraph edges in total, not 2.

solve_subproblem()

std::pair< long, std::set< Edge > > discrete_modulus::detail::solve_subproblem ( Graph &  g, FlowContext &  ctx, const Edge &  e, long  q  )

inline

One max-flow step of Cunningham's algorithm: how far can x be increased on edge e without leaving the polymatroid P(qf)?

Parameters

g	Graph whose edge_weight property map holds the current x.
ctx	Reusable flow network for g, from create_flow_graph.
e	The edge being incremented.
q	See the module-level (file) documentation.

Returns

{eps, crit_edges}: the maximum amount x(e) can be increased, and the critical (tight) edge set found by the min cut.