Skip to main content
`Ctrl`+`K`

# build_residual_network

build_residual_network(G, capacity)

  Build a residual network and initialize a zero flow.

  The residual network `R` from an input graph `G` has the same nodes as `G`. `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 in `G`.

  For each edge `(u, v)` in `R`, `R[u][v]['capacity']` is equal to the capacity of `(u, v)` in `G` if it exists in `G` 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 in `R.graph['inf']`. For each edge `(u, v)` in `R`, `R[u][v]['flow']` represents the flow function of `(u, v)` and satisfies `R[u][v]['flow'] == -R[v][u]['flow']`.

  The flow value, defined as the total flow into `t`, the sink, is stored in `R.graph['flow_value']`. If `cutoff` is not specified, reachability to `t` using only edges `(u, v)` such that `R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum `s`-`t` cut.