build_residual_network¶
- build_residual_network(G, capacity)[source]¶
Build a residual network and initialize a zero flow.
The residual network
R
from an input graphG
has the same nodes asG
.R
is a DiGraph that contains a pair of edges(u, v)
and(v, u)
iff(u, v)
is not a self-loop, and at least one of(u, v)
and(v, u)
exists inG
.For each edge
(u, v)
inR
,R[u][v]['capacity']
is equal to the capacity of(u, v)
inG
if it exists inG
or zero otherwise. If the capacity is infinite,R[u][v]['capacity']
will have a high arbitrary finite value that does not affect the solution of the problem. This value is stored inR.graph['inf']
. For each edge(u, v)
inR
,R[u][v]['flow']
represents the flow function of(u, v)
and satisfiesR[u][v]['flow'] == -R[v][u]['flow']
.The flow value, defined as the total flow into
t
, the sink, is stored inR.graph['flow_value']
. Ifcutoff
is not specified, reachability tot
using only edges(u, v)
such thatR[u][v]['flow'] < R[u][v]['capacity']
induces a minimums
-t
cut.