# Changes between Initial Version and Version 1 of Ticket #16475, comment 17

Ignore:
Timestamp:
05/18/15 15:03:17 (6 years ago)
Comment:

### Legend:

Unmodified
 initial Michele Replying to [comment:16 ncohen]: > Helloooooooooooo, > > > > > > 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. > > > > > > > > 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". > > 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. > > > > > > 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. > > > > > > > > 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. > > 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. > > Assuming the existence of a gomory-hu tree, I apply Lemma 15.14alpha to two points to obtain a bipartition U,V 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.: > - "real vertices from the original graphs" and > - "fake vertices that only appear because of the merge operation" > > 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). > > > > > 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? > > > > > > > > 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? > > 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. > > Sorry for the misunderstanding, and thank you for your attention with respect to this issue. > > Nathann