File FlowApplications.h

↰ Parent directory (ADS/graph)

Two uses of the maximum flow of section 15.2 [see File MaxFlow.h]:

Definition (ADS/graph/FlowApplications.h)

Detailed Description

  • edgeDisjointPaths(), at most k paths from s to t with no edge in common, as many as there can be: by the theorem of Menger, their largest number is the maximum flow from s to t with capacity 1 on each edge, which equals the fewest edges whose removal separates t from s. A new source joined to s by capacity k stops the flow at k. The flow is integral, and it is decomposed into paths by walking from s along the edges of flow 1 not used yet, a cycle met on the way being cut out of the walk, so that the paths are simple. On an unoriented graph each edge gives two opposite edges of capacity 1, and their flows, if both are 1, cancel out before the walks. With DINIC the flow takes :math:` O( m min( sqrt{m} , n^{2/3} ) ) ` on these networks of unit capacities (Even and Tarjan), and O( k ( n + m ) ) by k augmenting paths; the walks take O( n + m ) more;

  • decreaseCapacity(), the maximum flow f, kept on matrices of the capacities c and of the flows (f( y , x ) = - f( x , y )), after the capacity of ( u , v ) decreases by 1, without starting over. If the edge is not saturated f is still a maximum flow (SLACK). Otherwise one unit less goes on ( u , v ), which leaves an excess at u and a deficit at v; by the decomposition of f into paths and cycles, that unit lies on a cycle of flow, closed by a path of flow from v to u, or on a path of flow from s to t, through a path from s to u and one from v to t. One unit less on the cycle keeps the value (CYCLE); one unit less on the two paths lowers it by 1, and since a capacity lowered by 1 lowers the maximum by at most 1, one search of an augmenting path makes the flow maximum again (PATH). At most three visits, :math:` O( n^2 ) ` on the matrices, against :math:` O( n^2 m ) ` or more for a new maximum flow; an increase of a capacity by 1 needs one augmenting path.

The contracts [see File Contract.h]: s and t are distinct nodes, k >= 0; the matrices of decreaseCapacity() are square of the same size and c( u , v ) > 0. At the level of the audits edgeDisjointPaths() ensures that its paths are simple, from s to t along the edges of the graph, and use each edge once, and decreaseCapacity() that f is a maximum flow within c before and after. The functions are defined in FlowApplications.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 15.2, https://algoritmicamente.it/materiali/libro/capitoli/cap15.pdf

  1. Menger, Zur allgemeinen Kurventheorie, Fundamenta Mathematicae 10, 96-115, 1927, doi:10.4064/fm-10-1-96-115

    1. Ford, D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics 8, 399-404, 1956, doi:10.4153/CJM-1956-045-5

  1. Even, R. E. Tarjan, Network flow and testing graph connectivity, SIAM Journal on Computing 4(4), 507-518, 1975, doi:10.1137/0204043

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Enums

Functions