networkx / networkx/networkx

minimum_cut returns correct value, valid partition, but different from what it claims to return

Open
#5,239 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

type: Documentation type: Enhancements
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.