id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
16475 Bug in Gomory-Hu tree algorithm foosterhof "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]
}}}" defect closed major sage-6.6 graph theory fixed gomory hu tree gomory-hu gomory_hu_tree Rudi Nathann Cohen Michele Borassi N/A b0bbcd4119209e2b0e158ac3f83a5d2068009993 b0bbcd4119209e2b0e158ac3f83a5d2068009993 #12797