Opened 9 years ago
Closed 6 years ago
#12797 closed defect (fixed)
The cut returned by edge_cut of undirected weighted graphs is sometimes incorrect
Reported by: | hartke | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | ncohen, Rudi | Merged in: | |
Authors: | Nathann Cohen, Florian Oosterhof | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 25d1b9f (Commits) | Commit: | 25d1b9ffdcf9744635fdab5cbc9ae92a83383e02 |
Dependencies: | Stopgaps: |
Description
When using the Ford-Fulkerson method for edge_cut of an undirected weighted graph, the value of the minimum cut is correct, but sometimes the returned edge cut does not have that value. The LP method for edge_cut does seem to always return the correct answer.
Below is a simplified example due to Doug McNeil?.
sage: G = Graph([(0, 3, 1), (0, 4, 1), (1, 2, 1), (2, 3, 1), (2, 4, 1)]) sage: G.edge_cut(0,1,value_only=False,use_edge_labels=True) [1, [(0, 3, 1), (1, 2, 1), (2, 3, 1)]] sage: G.edge_cut(0,1,value_only=False,use_edge_labels=True,method='LP') (1.0, [(1, 2)])
Initial discussion on https://groups.google.com/d/topic/sage-support/fKixuZ2wZmw/discussion|sage-support.
Change History (20)
comment:1 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:2 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:4 follow-up: ↓ 5 Changed 7 years ago by
- Cc rudi added
comment:5 in reply to: ↑ 4 Changed 7 years ago by
> g.add_edge(v, u) # <-- Added line
If g
is a graph, adding vu
or uv
are equivalent operations.
Nathann
comment:6 Changed 7 years ago by
- Branch set to u/ncohen/12797
- Status changed from new to needs_review
OKayyyyyyyyyyyy, looks like converting the digraph was sufficient :-)
By the way it also fixes a "theoretical bug" : I am not sure that this code was meant to handle the situation where there is a cycle in the residual graph (I don't know if it ever happens). With this, no problem.
Thanks for the report ! Now this patch just needs a review before being merged into Sage.
Nathann
comment:7 Changed 7 years ago by
- Commit set to 8f1ad732bd60a20b70626aaeb3f566a31214581e
Branch pushed to git repo; I updated commit sha1. New commits:
8f1ad73 | trac #12797: The cut returned by edge_cut of undirected weighted graphs is sometimes incorrect
|
comment:8 Changed 7 years ago by
foosterhof : given that you found the bugfix, can you add your full name to the "Authors" field along with mine ?
Nathann
comment:9 follow-up: ↓ 10 Changed 7 years ago by
Should a sanity check be made that the label is positive? Not sure if a flow graph with a 0 label can even be created.
comment:10 in reply to: ↑ 9 Changed 7 years ago by
Should a sanity check be made that the label is positive? Not sure if a flow graph with a 0 label can even be created.
Well, with this at the end of GenericGraph._fork_fulkerson
I guess we are safe
g.add_edges([(x,y,l) for ((x,y),l) in flow.iteritems() if l > 0])
Nathann
comment:11 Changed 7 years ago by
- Cc Rudi added; rudi removed
comment:12 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:13 Changed 6 years ago by
Is there anybody available for a review here?
comment:14 follow-up: ↓ 15 Changed 6 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_work
You should add another line of example with method='LP'
.
Furthermore, the conversion to digraph should be done only if self is undirected, right?
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 17 Changed 6 years ago by
- Status changed from needs_work to needs_review
Yo !
You should add another line of example with
method='LP'
.
To test what exactly? The LP method does not use the code that is being changed here, and there are already some doctests with the LP method in this function?...
Furthermore, the conversion to digraph should be done only if self is undirected, right?
Well, edges are added/removed from the copy several lines later?...
Patch merged with the latest beta.
Nathann
comment:16 Changed 6 years ago by
- Commit changed from 8f1ad732bd60a20b70626aaeb3f566a31214581e to f7c8b16d912c1f8368e8188542887f3cf1c3dd1c
Branch pushed to git repo; I updated commit sha1. New commits:
f7c8b16 | trac #12797: Merged with 6.5.beta5
|
comment:17 in reply to: ↑ 15 Changed 6 years ago by
Replying to ncohen:
Yo !
You should add another line of example with
method='LP'
.To test what exactly? The LP method does not use the code that is being changed here, and there are already some doctests with the LP method in this function?...
The description of this patch compares the result returned by FF with the one of LP. Adding one line will show that everything is in order.
Furthermore, the conversion to digraph should be done only if self is undirected, right?
Well, edges are added/removed from the copy several lines later?...
OK
David.
comment:18 Changed 6 years ago by
- Commit changed from f7c8b16d912c1f8368e8188542887f3cf1c3dd1c to 25d1b9ffdcf9744635fdab5cbc9ae92a83383e02
Branch pushed to git repo; I updated commit sha1. New commits:
25d1b9f | trac #12797: Review
|
comment:20 Changed 6 years ago by
- Branch changed from u/ncohen/12797 to 25d1b9ffdcf9744635fdab5cbc9ae92a83383e02
- Resolution set to fixed
- Status changed from positive_review to closed
This bug can quite easily be fixed by replacing in the code the part:
by:
This is because the usual algorithms search for the vertices reachable by s in the residual graph. However, the original graph is not a residual graph, and thus the constructed graph "g" not as well, as it has no back-edges. Therefore, the partition of vertices is calculated incorrectly, and therefor the edges exhibiting the cut as well.