#16475: Bug in Gomory-Hu tree algorithm
-------------------------+-------------------------------------------------
Reporter: | Owner:
foosterhof | Status: new
Type: defect | Milestone: sage-6.3
Priority: major | Keywords: gomory hu tree gomory-hu
Component: graph | gomory_hu_tree
theory | Authors:
Merged in: | Report Upstream: N/A
Reviewers: | Branch:
Work issues: | Dependencies:
Commit: |
Stopgaps: |
-------------------------+-------------------------------------------------
When trying to come up with a doctest to verify ticket #16404, I stumbled
across this error:
{{{
sage: G = graphs.PetersenGraph()
sage: for u, v in [(0, 1), (0, 4), (0, 5), (1, 2), (1, 6), (3, 4), (5, 7),
(5, 8)]:
....: G.set_edge_label(u, v, 2)
....: T = G.gomory_hu_tree(method="FF")
....: f = G.flow(1, 9, use_edge_labels = True)
....: f2 = T.edge_label(1, 9)
....: if f != f2:
....: print 'Proper Tree Edge Error:', f, f2
....:
Proper Tree Edge Error: 3 6
}}}
This is a violation of the property that defines a Gomory-Hu tree.
Furthermore, the derived property that the flow between two vertices in a
graph is the minimum of the edge_labels in the constructed Gomory-Hu tree
can be violated, for instance in the above graph:
{{{
sage: f = G.flow(5, 1, use_edge_labels = True)
sage: P = T.shortest_path(5, 1)
sage: E = zip(P, P[1::])
sage: f2 = min(map(lambda x: T.edge_label(x[0], x[1]), E))
sage: if f != f2:
....: print 'Tree Path Error:', f, f2, P
....:
Tree Path Error: 6 3 [5, 9, 1]
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16475>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
