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:  sage6.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 FordFulkerson 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/sagesupport/fKixuZ2wZmw/discussionsagesupport.
Change History (20)
comment:1 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 followup: ↓ 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 followup: ↓ 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 sage6.3 to sage6.4
comment:13 Changed 6 years ago by
Is there anybody available for a review here?
comment:14 followup: ↓ 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 ; followup: ↓ 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 does not have to have all backedges. Therefore, the partition of vertices is calculated incorrectly, and therefor the edges exhibiting the cut as well.