The cut returned by edge_cut of undirected weighted graphs is sometimes incorrect

[hartke]

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.

[foosterhof]

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

[ncohen]

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

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

Nathann

[ncohen]

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

[git]

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

[ncohen]

foosterhof : given that you found the bugfix, can you add your full name to the "Authors" field along with mine ?

Nathann

[foosterhof]

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.

[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

[ncohen]

Is there anybody available for a review here?

[dcoudert]

You should add another line of example with method='LP'.

Furthermore, the conversion to digraph should be done only if self is undirected, right?

[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?...

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

[git]

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

​f7c8b16

trac #12797: Merged with 6.5.beta5

[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.

[git]

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

​25d1b9f

trac #12797: Review

[dcoudert]

Good ;)