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 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)