## `Network::maxFlow` -- computes a maximal flow through a network

#### Introduction

``Network::maxFlow`(G, q, s)` computes a maximal flow through network `G` from node `q` to node `s`.

#### Call(s)

`Network::maxFlow(G, q, s)`

#### Parameters

`G` | - | network
`q,s` | - | expressions (nodes in `G`)

#### Returns

a list, containing a number and a table

#### Details

- ``Network::maxFlow`(G,q,s)` computes a maximal flow from `q` to `s` in `G` with respect to the edge capacities. `q` and `s` must be nodes in `G`.
- ``Network::maxFlow`(G,q,s)` returns a sequence containing the flow value, that is the inflow of `s`, which equals the outflow of `q`, and the flow itself in form of table `t` with the flow from node `v` to node `w` is `t[[v,w]]`.

#### Example 1

In the complete network with four vertices and default capacities of 1, the maximum flow from one vertex to another one consists of sending one unit through each of the remaining vertices and one directly, which makes three units altogether.

    >> N1 := Network::complete(4):
       Network::maxFlow(N1,1,4)

                                    table(
                                      [4, 3] = 0,
                                      [4, 2] = 0,
                                      [4, 1] = 0,
                                      [3, 4] = 1,
                                      [3, 2] = 0,
                                 3,   [3, 1] = 0,
                                      [2, 4] = 1,
                                      [2, 3] = 0,
                                      [2, 1] = 0,
                                      [1, 4] = 1,
                                      [1, 3] = 1,
                                      [1, 2] = 1
                                    )

#### Example 2

A more complex example, the following network shows that this function also finds flows through multiple edges, unlike `Network::admissibleFlow`, which only works on completely described flows.

    >> V := [1,2,3,q,s]:
       Edge := [[q,1], [q,2], [1,2], [1,3], [2,3], [3,s]]:
       up := [5, 5, 2, 6, 6, 1]:
       N2 := Network(V, Edge, Capacity=up):
       Network::maxFlow(N2, q, s)

                                    table(
                                      [3, s] = 1,
                                      [2, 3] = 1,
                                 1,   [1, 3] = 0,
                                      [1, 2] = 0,
                                      [q, 2] = 1,
                                      [q, 1] = 0
                                    )

#### Background

- The implemented algorithm is the preflow-push algorithm of Goldberg &Tarjan with the FIFO selection strategy and an exact distance labeling (``A new approach to the maximum-flow problem'', Journal of the ACM 35(4), 1988).
- The running time is O(n3), where n is the number of vertices in the network.

#### Changes

- used to be called `Network::MaxFlow`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000