MaxFlow - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

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 returns the optimal value for the max flow problem along with an optimal flow (as a Matrix).
 • The algorithm used is 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=|V| is the number of vertices of G and m=|E| 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,1,0,3,0\right],\left[0,1,0,0,0,1\right],\left[0,0,3,0,1,0\right],\left[0,0,0,1,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}& {1}& {0}& {3}& {0}\\ {0}& {1}& {0}& {0}& {0}& {1}\\ {0}& {0}& {3}& {0}& {1}& {0}\\ {0}& {0}& {0}& {1}& {0}& {4}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (1)
 > $N≔\mathrm{Digraph}\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{MaxFlow}\left(N,1,6\right)$
 ${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)