NetworkX Produces Different Graph than Documentation

[jarednielsen]

I took the code exactly from the tutorial and exported it to a NetworkX graph for better visualization. It appears to be missing terminal edges. Why is this?

[pmneila]

Hi,

I explain this behavior in the second part of this comment. In short, maxflow internally stores the terminal edges of a node just as the difference between the source and the sink edges. This is the only quantity that matters in practice. For example, setting the source capacity to 3 and the sink capacity to 1 is equivalent to setting the source to 2 and sink to 0, and therefore, it stores 3-1 = 2-0 = 2 in both cases.

In your case, when you call g.add_tedge(nodes[0], 2, 5), it stores 2-5=-3. This means that the source edge capacity is 0 and the sink edge capacity is 3. In the plot this is represented as a non-existing edge from s to 0.

A similar thing happens with g.add_tedge(nodes[1], 9, 4): it stores 5 (source edge capacity = 5, sink edge capacity = 0). In the plot, no sink edge.