Content deleted Content added
→Status of the algorithm: Finish analysis of the above bugs and discuss differences with the original (includes full copy of original) |
|||
Line 157:
After seeing the large number of bug discussions on this page, I thought it would be prudent to put up a dispute-section template on that page. I intend to address each of the above concerns. Can anybody who is more of an expert in the field check that the algorithm is correct so we can remove the box? I have ported it to Python and it seems to be working okay. —[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 05:37, 8 February 2011 (UTC)
* 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.
** 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.
For reference, the exact algorithm as listed in Tarjan, ''Depth-first search and linear graph algorithms'':
BEGIN
INTEGER i;
PROCEDURE STRONGCONNECT (v);
BEGIN
LOWLINK (v) := NUMBER (v) := i := i + 1;
put v on stack of points;
FOR w in the adjacency list of v DO
BEGIN
IF w is not yet numbered THEN
BEGIN comment (v, w) is a tree arc;
STRONGCONNECT (w);
LOWLINK (v) := min (LOWLINK (v), LOWLINK (w));
END
ELSE IF NUMBER (w) < NUMBER (v) DO
BEGIN comment (v, w) is a frond or cross-link;
if w is on stack of points THEN
LOWLINK (v) := min (LOWLINK (v), NUMBER (w));
END;
END;
If (LOWLINK (v) = NUMBER (v)) THEN
BEGIN comment v is the root of a component;
start new strongly connected component;
WHILE w on top of point stack satisfies NUMBER (w) >= NUMBER (v) DO
delete w from point stack and put w in current component
END;
END;
i := 0;
empty stack of points;
FOR w a vertex IF w is not yet numbered THEN STRONGCONNECT (w);
END;
—[[User:MattGiuca|MattGiuca]] ([[User talk:MattGiuca|talk]]) 10:36, 8 February 2011 (UTC)
| |||