| 14 | | |
| 15 | | Replying to [comment:16 ncohen]: |
| 16 | | |
| 17 | | > Helloooooooooooo, |
| 18 | | > |
| 19 | | > |
| 20 | | > |
| 21 | | > |
| 22 | | > > 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. |
| 23 | | > > |
| 24 | | > > |
| 25 | | > > |
| 26 | | > |
| 27 | | > 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". |
| 28 | | > |
| 29 | | > 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. |
| 30 | | > |
| 31 | | > |
| 32 | | > |
| 33 | | > |
| 34 | | > > 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. |
| 35 | | > > |
| 36 | | > > |
| 37 | | > > |
| 38 | | > |
| 39 | | > 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. |
| 40 | | > |
| 41 | | > 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. |
| 42 | | > |
| 43 | | > 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.: |
| 44 | | > - "real vertices from the original graphs" and |
| 45 | | > - "fake vertices that only appear because of the merge operation" |
| 46 | | > |
| 47 | | > 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). |
| 48 | | > |
| 49 | | > |
| 50 | | > |
| 51 | | > > 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? |
| 52 | | > > |
| 53 | | > > |
| 54 | | > > |
| 55 | | > |
| 56 | | > 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? |
| 57 | | > |
| 58 | | > 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. |
| 59 | | > |
| 60 | | > Sorry for the misunderstanding, and thank you for your attention with respect to this issue. |
| 61 | | > |
| 62 | | > Nathann |
