Network::maxFlow
-- computes a
maximal flow through a network
computes a
maximal flow through network Network::maxFlow
(G, q, s)G
from node q
to
node s
.
Network::maxFlow(G, q, s)
G |
- | network |
q,s |
- | expressions (nodes in G ) |
a list, containing a number and a table
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]]
.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 )
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 )
Network::MaxFlow