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 |