minimum_cut returns correct value, valid partition, but different from what it claims to return
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 17.3k
- Forks
- 3.6k
- Avg merge
- 2d 20h
- Merged PRs (30d)
- 36
Description
I see two open issues related to minimum_cut but I have just encountered yet another problem. The function claims to return a partition (left, right) where left contains all nodes reachable from the source in the residual network and right contains the rest, but the following instance shows that the code behaves differently:
>>> import networkx as nx
>>> G = nx.DiGraph()
>>> for u, v, c in [(35, 36, 2), (36, 37, 2), (37, 39, 2), (39, 40, 2), (40, 41, 1), (41, 46, 1), (46, 47, 1)]:
... G.add_edge(u, v, capacity=c)
>>> nx.minimum_cut(G, 35, 47)
(1, ({35, 36, 37, 39, 40, 41, 46}, {47}))
Although the cut is minimum, the flow on (40, 41) must have value 1, and therefore node 41 is not reachable from 35 in the residual network. So minimum_cut should return ({35, 36, 37, 39, 40}, {41, 46, 47}).
The function I implemented to obtain the partition does this:
sources = ... # fill in with your sources for the max flow computation
left = set.union(
*(descendants(residual, p) for p in sources), sources
)
right = set(residual.nodes).difference(left)
Instead of the snippet from maxflow.py:
# Then, reachable and non reachable nodes from source in the
# residual network form the node partition that defines
# the minimum cut.
non_reachable = set(dict(nx.shortest_path_length(R, target=_t)))
partition = (set(flowG) - non_reachable, non_reachable)
I haven't tried to patch networkx's code yet.
(behaviour noticed in networkx version 2.4, Python 3.8.10 on Ubuntu 20.04.3)
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in maxflow.py at the residual-network partition logic and reproduce the supplied graph with networkx.minimum_cut. Compare the reachable-node calculation with the documented partition, then add or update coverage so the example's expected partition is verified.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- data
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100