#12797: The cut returned by edge_cut of undirected weighted graphs is sometimes
incorrect
----------------------------+-----------------------------------------------
Reporter: hartke | Owner: jason, ncohen, rlm
Type: defect | Status: new
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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].
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12797>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
