Content deleted Content added
→The pseudocode didn't work for me: quite possible |
→Status of the algorithm: Clarify difference to Tarjan original code |
||
Line 177:
* Well, I just went through every one of the above claims and added a comment there. I don't think any of them present a problem for the algorithm in its current state. However, there are a number of small differences between the algorithm as it currently stands on Wikipedia, and the original Tarjan paper (see below). I don't think any of them actually change the behaviour of the algorithm though.
** Tarjan surrounds the "was successor on the stack" clause with "ELSE IF NUMBER (w) < NUMBER (v) DO", which in our algorithm would be written as "<code>else if v'.number < v.number</code>". I don't see a reason for this, though. By definition, all nodes which already have an index will have one less than the current node, so I think we can leave this out.
**: ''This is because Tarjan in his paper states that he will only consider (i) edges that are in the search tree, (ii) edges that connect back to some search tree ancestor ([[frond]]s), and (iii) edges between sibling branches in the search tree (cross-links); the fourth class of edges that go to an already visited direct descendant are to be ignored, and that is what this test achieves. But it is indeed a pointless test, as the min in that fourth case is just the current lowlink anyway.'' [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 13:47, 9 December 2015 (UTC)
** Tarjan's "pop" loop is "WHILE w on top of point stack satisfies NUMBER (w) >= NUMBER (v) DO", which in our algorithm would be written as "<code>while v'.index >= v.index</code>". First, it is a while loop rather than a do-while loop (it is required to succeed on the first iteration). Second, it succeeds for v' == v (hence the do-while loop is not needed). Third, it fails if a node is encountered with an index smaller than the current node. I think you could reason that this accomplishes the same thing as popping all nodes up to and including the current node: the nodes on the stack should always be sorted by index, so popping until a node is found with a smaller index than the current is the same as popping until the current node is found.
** Therefore, I would consider the Wikipedia version to be functionally equivalent to the original. I will therefore remove the "dispute" box I put up earlier.
| |||