Opened 7 years ago

Closed 4 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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 follow-up: Changed 5 years ago by foosterhof

  • Cc rudi added

This bug can quite easily be fixed by replacing in the code the part:

g = self.copy()
for u,v,l in flow_graph.edge_iterator():
    if (not use_edge_labels or
        (weight(g.edge_label(u,v)) == weight(l))):
        g.delete_edge(u,v)

by:

g = self.copy()
for u,v,l in flow_graph.edge_iterator():
    g.add_edge(v, u)                         # <-- Added line
    if (not use_edge_labels or
        (weight(g.edge_label(u,v)) == weight(l))):
        g.delete_edge(u,v)

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 back-edges. Therefore, the partition of vertices is calculated incorrectly, and therefor the edges exhibiting the cut as well.

Last edited 5 years ago by foosterhof (previous) (diff)

comment:5 in reply to: ↑ 4 Changed 5 years ago by ncohen

>     g.add_edge(v, u)                         # <-- Added line

If g is a graph, adding vu or uv are equivalent operations.

Nathann

comment:6 Changed 5 years ago by ncohen

  • 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 5 years ago by git

  • Commit set to 8f1ad732bd60a20b70626aaeb3f566a31214581e

Branch pushed to git repo; I updated commit sha1. New commits:

8f1ad73trac #12797: The cut returned by edge_cut of undirected weighted graphs is sometimes incorrect

comment:8 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen

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: Changed 5 years ago by foosterhof

  • Authors changed from Nathann Cohen to Nathann Cohen, Florian Oosterhof

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 5 years ago by ncohen

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 5 years ago by Rudi

  • Cc Rudi added; rudi removed

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:13 Changed 4 years ago by ncohen

Is there anybody available for a review here?

comment:14 follow-up: Changed 4 years ago by dcoudert

  • 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: Changed 4 years ago by ncohen

  • 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 4 years ago by git

  • Commit changed from 8f1ad732bd60a20b70626aaeb3f566a31214581e to f7c8b16d912c1f8368e8188542887f3cf1c3dd1c

Branch pushed to git repo; I updated commit sha1. New commits:

f7c8b16trac #12797: Merged with 6.5.beta5

comment:17 in reply to: ↑ 15 Changed 4 years ago by dcoudert

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 4 years ago by git

  • Commit changed from f7c8b16d912c1f8368e8188542887f3cf1c3dd1c to 25d1b9ffdcf9744635fdab5cbc9ae92a83383e02

Branch pushed to git repo; I updated commit sha1. New commits:

25d1b9ftrac #12797: Review

comment:19 Changed 4 years ago by dcoudert

  • Status changed from needs_review to positive_review

Good ;)

comment:20 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/12797 to 25d1b9ffdcf9744635fdab5cbc9ae92a83383e02
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.