search

pmneila / PyMaxflow

Python library for creating flow networks and computing the maxflow/mincut (aka graph-cuts for Python)
http://pmneila.github.io/PyMaxflow/
242 stars 59 forks source link

NetworkX Produces Different Graph than Documentation #38

Closed jarednielsen closed 5 years ago

jarednielsen commented 5 years ago
screen shot 2019-02-04 at 6 06 48 pm

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?

graph

pmneila commented 5 years ago

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.