Sage: Ticket #16475: Bug in Gomory-Hu tree algorithm
https://trac.sagemath.org/ticket/16475
<p>
When trying to come up with a doctest to verify ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16404" title="enhancement: logic error in code of _gomory_hu_tree (closed: duplicate)">#16404</a>, I stumbled across this error:
</p>
<pre class="wiki">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
</pre><p>
This is a violation of the property that defines a Gomory-Hu tree.
</p>
<p>
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:
</p>
<pre class="wiki">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]
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16475
Trac 1.1.6foosterhofThu, 12 Jun 2014 15:32:45 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/16475#comment:1
https://trac.sagemath.org/ticket/16475#comment:1
<ul>
<li><strong>changetime</strong>
changed from <em>06/12/14 08:40:17</em> to <em>06/12/14 08:40:17</em>
</li>
<li><strong>branch</strong>
set to <em>u/foosterhof/ticket/16475</em>
</li>
<li><strong>time</strong>
changed from <em>06/12/14 08:40:17</em> to <em>06/12/14 08:40:17</em>
</li>
</ul>
TicketfoosterhofFri, 13 Jun 2014 08:53:09 GMTstatus changed; commit set
https://trac.sagemath.org/ticket/16475#comment:2
https://trac.sagemath.org/ticket/16475#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>27025d1708e3bc7c0589b266bbf1f2f143e6b97a</em>
</li>
</ul>
<p>
The problem with the algorithm was that after the recursion, an edge was added. This edge was added to just any 2 vertices before, but there is are 2 specific vertices to which this edge should be added. These vertices are now calculated correctly (hopefully)
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=27025d1708e3bc7c0589b266bbf1f2f143e6b97a"><span class="icon"></span>27025d1</a></td><td><code>Fixed Gomory-Hu tree algorithm by adding the partitions</code>
</td></tr></table>
TicketgitFri, 13 Jun 2014 13:10:39 GMTcommit changed
https://trac.sagemath.org/ticket/16475#comment:3
https://trac.sagemath.org/ticket/16475#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>27025d1708e3bc7c0589b266bbf1f2f143e6b97a</em> to <em>9326d1518c32d30978e7b4ce9e39720f1bf8083d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9326d1518c32d30978e7b4ce9e39720f1bf8083d"><span class="icon"></span>9326d15</a></td><td><code>Added doctest</code>
</td></tr></table>
TicketfoosterhofFri, 13 Jun 2014 13:12:43 GMTdependencies set
https://trac.sagemath.org/ticket/16475#comment:4
https://trac.sagemath.org/ticket/16475#comment:4
<ul>
<li><strong>dependencies</strong>
set to <em>12797</em>
</li>
</ul>
<p>
This fix works correctly, as far as I tested, when ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/12797" title="defect: The cut returned by edge_cut of undirected weighted graphs is ... (closed: fixed)">#12797</a> is applied as well.
</p>
<p>
Florian
</p>
TicketncohenTue, 17 Jun 2014 07:42:28 GMT
https://trac.sagemath.org/ticket/16475#comment:5
https://trac.sagemath.org/ticket/16475#comment:5
<p>
Hello !
</p>
<p>
Just some cosmetic remarks :
</p>
<ul><li>Set is *MUCH* slower than set or frozenset, so if you don't need Set for a specific reason don't use it:
</li></ul><pre class="wiki">sage: %timeit Set(range(50))
10000 loops, best of 3: 29.1 µs per loop
sage: %timeit frozenset(range(50))
100000 loops, best of 3: 2.05 µs per loop
</pre><ul><li>It would be cool if you could add some comments about what the following block of code does. Just a line or 5 words, i.e. something to say with words what is happening there
</li></ul><pre class="wiki">+ C = {}
...
+ C[r] = C2[r]
</pre><p>
Thanks for fixing that, btw <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketchapotonTue, 17 Jun 2014 08:32:38 GMTdependencies changed
https://trac.sagemath.org/ticket/16475#comment:6
https://trac.sagemath.org/ticket/16475#comment:6
<ul>
<li><strong>dependencies</strong>
changed from <em>12797</em> to <em>#12797</em>
</li>
</ul>
TicketgitTue, 17 Jun 2014 09:43:52 GMTcommit changed
https://trac.sagemath.org/ticket/16475#comment:7
https://trac.sagemath.org/ticket/16475#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>9326d1518c32d30978e7b4ce9e39720f1bf8083d</em> to <em>e4604fa9ba9cf8ef5475620ed6b3d156402015d6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e4604fa9ba9cf8ef5475620ed6b3d156402015d6"><span class="icon"></span>e4604fa</a></td><td><code>Added comment on goal and use of Partition code</code>
</td></tr></table>
TicketfoosterhofTue, 17 Jun 2014 09:45:15 GMT
https://trac.sagemath.org/ticket/16475#comment:8
https://trac.sagemath.org/ticket/16475#comment:8
<p>
Hi
</p>
<p>
I am trying to convert to use your suggestion, using frozenset, but the call g1.vertices() (and thus also g2.vertices()) complains that it cannot compare a (frozen)set to an int, as it will sort them. I have been trying to give it a nice key lambda function to circumvent this problem, but no luck so far. Any suggestions? Or does this mean that I can better just leave it as using Set?
</p>
<p>
I have added a comment, including a reference to a piece of a book by A. Schrijver, which explains the use of the partitions. (A Gomory-Hu tree can be defined for a specific subset R of V, in which case these partitions play a big role)
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e4604fa9ba9cf8ef5475620ed6b3d156402015d6"><span class="icon"></span>e4604fa</a></td><td><code>Added comment on goal and use of Partition code</code>
</td></tr></table>
TicketncohenTue, 17 Jun 2014 09:51:30 GMT
https://trac.sagemath.org/ticket/16475#comment:9
https://trac.sagemath.org/ticket/16475#comment:9
<p>
Hello !
</p>
<blockquote class="citation">
<p>
I am trying to convert to use your suggestion, using frozenset, but the call g1.vertices() (and thus also g2.vertices()) complains that it cannot compare a (frozen)set to an int, as it will sort them.
</p>
</blockquote>
<p>
HMmmmmmmmm <code>O_o</code>
</p>
<p>
I do not understand what you mean. Could you give me an example of code that produces it ? It looks that you cannot use "&" on a frozenset, but it has an "intersection" method
</p>
<pre class="wiki">sage: range(5) & frozenset(range(8))
...
TypeError: unsupported operand type(s) for &: 'list' and 'frozenset'
sage: frozenset(range(8)).intersection(range(5))
frozenset({0, 1, 2, 3, 4})
</pre><blockquote class="citation">
<p>
I have added a comment, including a reference to a piece of a book by A. Schrijver, which explains the use of the partitions. (A Gomory-Hu tree can be defined for a specific subset R of V, in which case these partitions play a big role)
</p>
</blockquote>
<p>
Thanks ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketfoosterhofTue, 17 Jun 2014 10:03:28 GMT
https://trac.sagemath.org/ticket/16475#comment:10
https://trac.sagemath.org/ticket/16475#comment:10
<p>
In Graph.vertices():
</p>
<pre class="wiki">if not boundary_first:
return sorted(list(self.vertex_iterator()), key=key)
</pre><p>
Apparently, it is possible to compare Set and int (or sage.blabla.Integer) objects, but not (frozen)set and int.
</p>
<pre class="wiki">sage: Set([252,35]) < 1
True
sage: set([252,35]) < 1
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-16-ea79432632b4> in <module>()
----> 1 set([Integer(2352),Integer(2352)]) < Integer(1)
TypeError: can only compare to a set
sage: frozenset([2352,2352]) < 1
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-17-55b270cfd9be> in <module>()
----> 1 frozenset([Integer(2352),Integer(2352)]) < Integer(1)
TypeError: can only compare to a set
</pre><p>
And thus, when doing:
</p>
<pre class="wiki">R1 = vertices & frozenset(g1.vertices())
</pre><p>
it gives a <a class="missing wiki">TypeError?</a>, as g1 contains a vertex that is a frozenset, namely g1_v:
</p>
<pre class="wiki">g1_v = frozenset(set2)
g2_v = frozenset(set1)
g1.add_vertex(g1_v)
g2.add_vertex(g2_v)
</pre><p>
Florian
</p>
<p>
EDIT:
</p>
<p>
This can be fixed very easily, but also more efficiently.
First of all, we can pass g1.vertex_iterator() to frozenset(), which will probably solve it all together.
</p>
<p>
Second of all, we know exactly which vertices g1 has, namely all vertices in set1, and the extra vertex g1_v. None more. Since g1_v is not in the variable vertices, we can just pass set1 to frozenset(), and analogously set2 for g2.
</p>
<p>
EDIT2:
</p>
<p>
Ok, so apparently Graph._backend.iterator_edges() also compares vertices before yielding them, to make sure the 'lesser' one is reported as the first vertex. And _ford_fulkerson uses this function through Graph.edge_iterator().
</p>
<p>
I guess there is no way around using a Set?
</p>
TicketncohenTue, 17 Jun 2014 10:28:29 GMT
https://trac.sagemath.org/ticket/16475#comment:11
https://trac.sagemath.org/ticket/16475#comment:11
<p>
Oh. I see ! Sorry, I had not realized that the problem came from frozensets inside of the graph !
</p>
<blockquote class="citation">
<p>
This can be fixed very easily, but also more efficiently.
First of all, we can pass g1.vertex_iterator() to frozenset(), which will probably solve it all together.
</p>
</blockquote>
<p>
Right, but that's going too far I guess.
</p>
<blockquote class="citation">
<p>
Ok, so apparently Graph._backend.iterator_edges() also compares vertices before yielding them, to make sure the 'lesser' one is reported as the first vertex. And _ford_fulkerson uses this function through Graph.edge_iterator().
</p>
</blockquote>
<p>
Yepyep. And g.vertices() sorts the vertices, which is not a good idea in itself but has some advantages, still ... <code>:-/</code>
</p>
<blockquote class="citation">
<p>
I guess there is no way around using a Set?
</p>
</blockquote>
<p>
Ahahaah. As you said there are many ways around, but the best is indeed to use Set. I don't think that it is a performance issue in this context, I was just saying aloud that it's better to avoid Set in general. Let's keep the code as it is <code>:-)</code>
</p>
<p>
Nathann
</p>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/16475#comment:12
https://trac.sagemath.org/ticket/16475#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketchapotonWed, 18 Feb 2015 09:14:02 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/16475#comment:13
https://trac.sagemath.org/ticket/16475#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-6.6</em>
</li>
</ul>
<p>
branch does not apply
</p>
TicketncohenSun, 15 Mar 2015 23:18:45 GMTstatus, commit, branch changed; author set
https://trac.sagemath.org/ticket/16475#comment:14
https://trac.sagemath.org/ticket/16475#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>e4604fa9ba9cf8ef5475620ed6b3d156402015d6</em> to <em>573257955a6e18241076d9b7030327bf14dcd562</em>
</li>
<li><strong>branch</strong>
changed from <em>u/foosterhof/ticket/16475</em> to <em>public/16475</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
I had totally forgotten this branch, and this is very bad (wrong results) (EDIT:see below). I looked at the code this week-end and fixed it (the fix actually takes one line ...), and also simplified the function a bit.
</p>
<p>
As the fix actually avoids adding more code to the function, I propose it instead, and change the branch (I hope that nobody minds). Needs review again.
</p>
<p>
Nathann
</p>
<p>
(EDIT 16/05/2015) This sentence is misleading: I meant that the *bug* is very bad, and that forgetting it is dangerous since Sage will return wrong results for as long as it is not fixed.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=df60f70468fc2ebb80d25795f254e311f82d58a8"><span class="icon"></span>df60f70</a></td><td><code>trac #16475: Move connectivity test to the main function</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=005e77c7240821d06c6201468690e204c4c98a27"><span class="icon"></span>005e77c</a></td><td><code>trac #16475: A useless case</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ebc65040552e0915b99daa5a2b0c265ed1fe0a25"><span class="icon"></span>ebc6504</a></td><td><code>trac #16475: simplify handling of edge labels (capacities)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=70ca16296177b0095b9374f9031fabc091805b68"><span class="icon"></span>70ca162</a></td><td><code>trac #16475: slightly Simplify update of edge labels (capacities)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=18c6493ad99fcf1b79b768f47394102f7ea6ecea"><span class="icon"></span>18c6493</a></td><td><code>trac #16475: Set->frozenset</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f8b054ed0242a5d2f7ee6bab05c28fef5243cce0"><span class="icon"></span>f8b054e</a></td><td><code>trac #16475: actual bugfix</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=be53d235332ca514e4a3a44f8c1c9d5f9f345e0a"><span class="icon"></span>be53d23</a></td><td><code>trac #16475: Documentation and renamed variables</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=573257955a6e18241076d9b7030327bf14dcd562"><span class="icon"></span>5732579</a></td><td><code>trac #16475: Bibliographical reference</code>
</td></tr></table>
TicketfoosterhofFri, 15 May 2015 14:46:49 GMT
https://trac.sagemath.org/ticket/16475#comment:15
https://trac.sagemath.org/ticket/16475#comment:15
<p>
Hello,
</p>
<p>
First of all, you say that my code was very bad, because it gave wrong results. Could you tell me why? I see no counter-example or anything to back up your claim.
</p>
<p>
Of course I dont mind any refactoring, and actually I think it is indeed much more readable, and even more efficient, but there is something bugging me:
</p>
<p>
In the bibliographical reference you give (which is actually what I used as well), the proof to show that a Gomory-Hu tree exists uses a Partition { C_r | r \in R }, which dictates how the two induction-obtained trees should be merged. This is what I tried to add to the code with my patch, but you have completely removed it. Why? You simply put the edge between the two trees to be {u, v} where u and v are the picked vertices. However, why would Schrijver put such rigor in proving that this tree obtained using the partition is correct, and not instead simply use 2 arbitrary vertices.
</p>
<p>
You say you have fixed the algorithm by a single line of code, however I still think that it might give incorrect results in some cases, for reasons above. Would you agree?
</p>
<p>
Florian
</p>
TicketncohenSat, 16 May 2015 12:13:26 GMT
https://trac.sagemath.org/ticket/16475#comment:16
https://trac.sagemath.org/ticket/16475#comment:16
<p>
Helloooooooooooo,
</p>
<blockquote class="citation">
<p>
First of all, you say that my code was very bad, because it gave wrong results. Could you tell me why? I see no counter-example or anything to back up your claim.
</p>
</blockquote>
<p>
Oh no sorry, that's a misunderstanding! I just re-read my comment and indeed I see how you could have understood it this way. I will edit it in a second. What I meant to say is "I had forgotten about this *bug*, and it is very bad (that I forgot it) because meanwhile Sage is returning wrong results".
</p>
<p>
I have found nothing wrong with your code. Actually, as I began reading the proof that you followed, I merely noticed that it could be done in a simpler way. Which is why I proposed this alternative implementation, hoping that you would not mind.
</p>
<blockquote class="citation">
<p>
In the bibliographical reference you give (which is actually what I used as well), the proof to show that a Gomory-Hu tree exists uses a Partition { C_r | r \in R }, which dictates how the two induction-obtained trees should be merged. This is what I tried to add to the code with my patch, but you have completely removed it. Why? You simply put the edge between the two trees to be {u, v} where u and v are the picked vertices. However, why would Schrijver put such rigor in proving that this tree obtained using the partition is correct, and not instead simply use 2 arbitrary vertices.
</p>
</blockquote>
<p>
What the current branch does is apply Lemma 15.14alpha (p249 in my edition of it). While I obviously cannot tell you why Schrijver wrote the proof the way he did, I suspect that it is because he wants to *prove* the algorithm while I only want to implement it.
</p>
<p>
Right now, the code applies Lemma 15.14alpha while *assuming* that every graph has a gomory-hu Tree. Schrijver cannot do this for the very obvious reasons that he wants to *prove* this existence result.
</p>
<p>
Assuming the existence of a gomory-hu tree, I apply Lemma 15.14alpha to two points to obtain a bipartition <code>U,V</code> of the graph, then successively contract U and V to obtain two 'reduced' graphs. In each graph you will find 'two kinds' of vertices, i.e.:
</p>
<ul><li>"real vertices from the original graphs" and
</li><li>"fake vertices that only appear because of the merge operation"
</li></ul><p>
With Lemma 15.14alpha, what we know is that the max flow between any two "real points" u,v of a specific "new" graph is equal to their max flow in the original graph. Consequently, the three that is being built must indeed be the gomory-hu tree (that we know exists).
</p>
<blockquote class="citation">
<p>
You say you have fixed the algorithm by a single line of code, however I still think that it might give incorrect results in some cases, for reasons above. Would you agree?
</p>
</blockquote>
<p>
Do you believe that the way it is done is wrong? Or do you believe that it is suspect of being wrong because it is a simpler algorithm than the one given by Schrijver's proofs?
</p>
<p>
In my experience, writing the proof of an algorithm requires much more theoretical machinery than what is actually needed when one implements it. Sometimes, it is even easier to make the (theoretical) algorithm a bit slower in order to make the explanation simpler. Very recently, I had to give a formal proof of an algorithm needed for some research problem: while it was easy to explain on a table, it was so complicated to explain it on paper that I started trying to change the algorithm itself to make the proof easier.
</p>
<p>
Sorry for the misunderstanding, and thank you for your attention with respect to this issue.
</p>
<p>
Nathann
</p>
TicketborassiMon, 18 May 2015 15:02:32 GMT
https://trac.sagemath.org/ticket/16475#comment:17
https://trac.sagemath.org/ticket/16475#comment:17
<p>
Hello!
</p>
<p>
I have analyzed the proofs in Schrijver: foosterhof is right, because you cannot take two arbitrary vertices, but the code is still correct, because the vertices taken are exactly the vertices u,v used in computing the initial u-v cut (these vertices have no name in Schrijver). We could then modify the proof of Theorem 15.14 in Schrijver by using u as r' and v as r'' (r' and r'' are the extremal points of the "new" arc added). In the last sentence of the proof, Lemma 15.14alpha yields the same conclusion for arcs e \neq r'r'', while for the arc r'r'', the two components of the tree obtained by removing r'r'' correspond to a minimum r'-r'' cut because we have chosen u=r' and v=r''.
</p>
<p>
I have no clue on why Schrijver did not use this proof, which looks much simpler (at least to me). If you have any doubts, I can write the whole proof more formally.
</p>
<p>
Other (small) issues:
</p>
<ul><li>in the comments, I'd use "maximum flow" instead of "maximal flow": in my opinion, "maximal" means that there might be other elements that are not comparable (for instance, C is a maximal clique if there is no clique C' \supset C, while it is a maximum clique if it is a clique of maximum cardinality).
</li><li>reading the code, I could not find Schrijver's reference: I think that adding this reference might be a good idea.
</li><li>do you think we should provide a proof that our "simplification" of Schrijver's algorithm works?
</li></ul><p>
Michele
</p>
TicketgitMon, 18 May 2015 17:36:40 GMTcommit changed
https://trac.sagemath.org/ticket/16475#comment:18
https://trac.sagemath.org/ticket/16475#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>573257955a6e18241076d9b7030327bf14dcd562</em> to <em>b0bbcd4119209e2b0e158ac3f83a5d2068009993</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7fadf1fcb8067deb4508a906e875ba0a265a1815"><span class="icon"></span>7fadf1f</a></td><td><code>trac #16475: Merged with 6.7</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b0bbcd4119209e2b0e158ac3f83a5d2068009993"><span class="icon"></span>b0bbcd4</a></td><td><code>trac #16475: maximal->maximum</code>
</td></tr></table>
TicketncohenMon, 18 May 2015 17:44:15 GMT
https://trac.sagemath.org/ticket/16475#comment:19
https://trac.sagemath.org/ticket/16475#comment:19
<p>
Hello !
</p>
<blockquote class="citation">
<ul><li>in the comments, I'd use "maximum flow" instead of "maximal flow"
</li></ul></blockquote>
<p>
I think that there is no confusion possible. I changed it anyway.
</p>
<blockquote class="citation">
<ul><li>reading the code, I could not find Schrijver's reference: I think that adding this reference might be a good idea.
</li></ul></blockquote>
<p>
It appears in the documentation of <code>Graph.gomory_hu_tree</code>, right before the 'INPUT' block.
</p>
<blockquote class="citation">
<ul><li>do you think we should provide a proof that our "simplification" of Schrijver's algorithm works?
</li></ul></blockquote>
<p>
As you please. Just remember that for as long as this ticket is not reviewed, Sage returns wrong answers. Also, Wikipedia contains a description of some algorithm to compute a Gomory-Hu tree (I did not read it). If it is the same then that's cool, and if ours is simpler then it is probably where the proof should be written.
</p>
<p>
<a class="ext-link" href="http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree"><span class="icon"></span>http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree</a>
</p>
<p>
Nathann
</p>
TicketborassiTue, 19 May 2015 09:59:19 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/16475#comment:20
https://trac.sagemath.org/ticket/16475#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Michele Borassi</em>
</li>
</ul>
TicketborassiTue, 19 May 2015 10:02:04 GMT
https://trac.sagemath.org/ticket/16475#comment:21
https://trac.sagemath.org/ticket/16475#comment:21
<p>
Hello!
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>in the comments, I'd use "maximum flow" instead of "maximal flow"
</li></ul></blockquote>
<p>
I think that there is no confusion possible. I changed it anyway.
</p>
</blockquote>
<p>
Ok :-)
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>reading the code, I could not find Schrijver's reference: I think that adding this reference might be a good idea.
</li></ul></blockquote>
<p>
It appears in the documentation of <code>Graph.gomory_hu_tree</code>, right before the 'INPUT' block.
</p>
</blockquote>
<p>
Sorry, I didn't find it!
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>do you think we should provide a proof that our "simplification" of Schrijver's algorithm works?
</li></ul></blockquote>
<p>
As you please. Just remember that for as long as this ticket is not reviewed, Sage returns wrong answers. Also, Wikipedia contains a description of some algorithm to compute a Gomory-Hu tree (I did not read it). If it is the same then that's cool, and if ours is simpler then it is probably where the proof should be written.
</p>
</blockquote>
<p>
I agree: this is not the place where the proof should be written. I think the code is fine as it is!
</p>
TicketvbraunTue, 19 May 2015 22:07:29 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16475#comment:22
https://trac.sagemath.org/ticket/16475#comment:22
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/16475</em> to <em>b0bbcd4119209e2b0e158ac3f83a5d2068009993</em>
</li>
</ul>
Ticket