Is it able to get the flow allocation after applying maxflow?
leobxpan opened this issue · 1 comments
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
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!