MaxFlow - Maple Help

GraphTheory

 MaxFlow
 compute optimal value for max flow problem

 Calling Sequence MaxFlow(G, s, t)

Parameters

 G - weighted graph s - vertex of the graph (source) t - vertex of the graph (sink)

Description

 • The MaxFlow command solves the s to t maximum flow problem using edge weights of G as the flow capacities between vertices. If G is not a weighted graph then every edge is taken to have a capacity of 1. If G is a multigraph every edge is taken to have a capacity equal to its multiplicity. An undirected Graph is treated as a directed graph with edges in both directions, but the output flow matrix will be directional.
 • This command returns two things: the optimal value for the maximum flow from the vertex s to the vertex t and a sparse matrix of the flows at each edge which achieve that optimal flow. The maximum flow value is unique, while the flow matrix may be one of several possible flows that achieve that maximum.
 • MaxFlow uses the Push-Relabel (Push-Preflow) algorithm of Goldberg et al. (see Introduction to Algorithms, Cormen, Leiserson, Rivest, 2nd edition). The complexity is $\mathrm{O}\left({n}^{2}m\right)$ where $n$ is the number of vertices of G and $m$ is the number of edges.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $A≔\mathrm{Matrix}\left(\left[\left[0,1,0,4,0,0\right],\left[0,0,2,0,3,0\right],\left[0,1,0,0,0,1\right],\left[0,0,3,0,1,0\right],\left[0,0,0,2,0,4\right],\left[0,0,0,0,0,0\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{cccccc}{0}& {1}& {0}& {4}& {0}& {0}\\ {0}& {0}& {2}& {0}& {3}& {0}\\ {0}& {1}& {0}& {0}& {0}& {1}\\ {0}& {0}& {3}& {0}& {1}& {0}\\ {0}& {0}& {0}& {2}& {0}& {4}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (1)
 > $N≔\mathrm{Graph}\left(A,'\mathrm{weighted}'\right)$
 ${N}{≔}{\mathrm{Graph 1: a directed weighted graph with 6 vertices and 10 arc\left(s\right)}}$ (2)
 > $\mathrm{IsNetwork}\left(N\right)$
 $\left\{{1}\right\}{,}\left\{{6}\right\}$ (3)
 > $\mathrm{DrawNetwork}\left(N\right)$
 > $\mathrm{mf},F≔\mathrm{MaxFlow}\left(N,1,6\right)$
 ${\mathrm{mf}}{,}{F}{≔}{4}{,}\left[\begin{array}{cccccc}{0}& {1}& {0}& {3}& {0}& {0}\\ {0}& {0}& {0}& {0}& {2}& {0}\\ {0}& {1}& {0}& {0}& {0}& {1}\\ {0}& {0}& {2}& {0}& {1}& {0}\\ {0}& {0}& {0}& {0}& {0}& {3}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (4)

The values in F can be used to show the flows on the network N

 > $M≔\mathrm{Graph}\left(F,'\mathrm{weighted}'\right)$
 ${M}{≔}{\mathrm{Graph 2: a directed weighted graph with 6 vertices and 8 arc\left(s\right)}}$ (5)
 > $\mathrm{StyleEdgesByProperty}\left(M,F,\mathrm{colorscheme}=\left["Blue","Purple","Red"\right],\mathrm{thicknessscheme}=\left[1,3\right]\right)$
 > $\mathrm{DrawGraph}\left(M,'\mathrm{layout}'='\mathrm{network}'\right)$

The input to MaxFlow does not have to be a network, or even be a weighted graph

 > $\mathrm{G6}≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{1,6\right\},\left\{2,3\right\},\left\{2,4\right\},\left\{3,4\right\},\left\{3,5\right\},\left\{4,5\right\},\left\{5,6\right\}\right\}\right)$
 ${\mathrm{G6}}{≔}{\mathrm{Graph 3: an undirected graph with 6 vertices and 8 edge\left(s\right)}}$ (6)
 > $\mathrm{DrawGraph}\left(\mathrm{G6}\right)$
 > $\mathrm{mf2},\mathrm{F2}≔\mathrm{MaxFlow}\left(\mathrm{G6},1,6\right)$
 ${\mathrm{mf2}}{,}{\mathrm{F2}}{≔}{2}{,}\left[\begin{array}{cccccc}{0}& {1}& {0}& {0}& {0}& {1}\\ {0}& {0}& {1}& {0}& {0}& {0}\\ {0}& {0}& {0}& {1}& {0}& {0}\\ {0}& {0}& {0}& {0}& {1}& {0}\\ {0}& {0}& {0}& {0}& {0}& {1}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (7)
 > $\mathrm{M2}≔\mathrm{Graph}\left(\mathrm{F2},'\mathrm{weighted}'\right)$
 ${\mathrm{M2}}{≔}{\mathrm{Graph 4: a directed weighted graph with 6 vertices and 6 arc\left(s\right)}}$ (8)
 > $\mathrm{DrawGraph}\left(\mathrm{M2},'\mathrm{layout}'='\mathrm{circle}'\right)$

References

 Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford. Introduction to Algorithms, 2nd edition. Cambridge, Mass., MIT Press, 2001.

Compatibility

 • The GraphTheory[MaxFlow] command was updated in Maple 2024.