Is it able to get the flow allocation after applying maxflow?

[leobxpan]

Hi there,

Thanks for sharing this wonderful codebase! I'm wondering is it possible to get the actual flow allocation in the entire network after applying maxflow with this library? Or can I only get the maximum value?

Thanks,

Boxiao

[pmneila]

Hi,

This is tricky. Indeed, you can get the remaining capacity of the edges using the get_nx_graph method after maxflow computation and looking at the weight attribute of the edges. However, interpreting the results is not that simple. For example, with the graph from simple.py:

import maxflow

# Build the graph.
g = maxflow.Graph[int](2, 2)
nodes = g.add_nodes(2)
g.add_edge(nodes[0], nodes[1], 1, 2)
g.add_tedge(nodes[0], 2, 5)
g.add_tedge(nodes[1], 9, 4)

flow = g.maxflow()

nxg = g.get_nx_graph()

# Remaining capacity in terminal edge 's'->1
print(nxg.edges[('s', 1)]
# {'weight': 3}

# Remaining capacity in terminal edge 0->'t'
print(nxg.edges[(0, 't')]
# {'weight': 1}

# Remaining capacity in edge 0 -> 1
print(nxg.edges[(0, 1)]
# {'weight': 3}

# Edges with no remaining capacity are not included in the graph.
print((1, 0) in nxg.edges)
# False

Note that for non-terminal edges the capacity after the maxflow can be higher than the initial capacity! (For example in the edge (0, 1) above.) This is a consequence of how the maxflow algorithm works. In particular, the flows are skew symmetric, with f(u, v) = -f(v, u). Therefore, the sum of the capacities of symmetric edges c(u, v) + c(v, u) remains the same before and after the maxflow computation.

Also, for terminal edges the capacity you set with add_tedge is not the capacity the algorithm uses internally. Check this explanation I wrote a few years ago to understand the details.

Hope that helps!