Content deleted Content added
Kalmankeri (talk | contribs) No edit summary |
|||
Line 221:
A recent edit, {{oldid2|647184742|01:55, 15 February 2015}}, attempts a technique to determine in constant time if a node is on the stack. The cited original paper by Tarjan mentions, "Testing to see if a vertex is on the point stack can be done in a fixed time if a Boolean array is kept which answers this question for each vertex." The recent edit however, introduces an "isRemoved" value per node, which is the opposite sense of "on the stack." The algorithm may work with this change, but it's difficult to see. It does not "answer the question for each vertex" as Tarjan suggested because the value is meaningless until the node is visited. Much more clear and following Tarjan's suggestion would be an "onStack" value. Further, if all onStack values were initialized to false at the start of the algorithm, then it would be clear that all nodes have valid values. —[[User:Fifteen Minutes Of Fame|Fifteen Minutes Of Fame]] ([[User talk:Fifteen Minutes Of Fame|talk]]) 04:26, 27 February 2015 (UTC)
== The pseudocode didn't work for me ==
I've carefully implemented the pseudocode and it produced incorrect results for me. I found a link above ([http://web.cecs.pdx.edu/~herb/cs410f99/scc.htm web.cecs.pdx.edu]) that helped me out.
It seems that an extra condition is missing here:
'''else if''' (''w''.onStack) '''then'''
''// Successor w is in stack S and hence in the current SCC''
''v''.lowlink := min(''v''.lowlink, ''w''.index)
'''end if'''
This version worked for me:
'''else if''' (''w''.index < ''v''.index '''and''' ''w''.onStack) '''then'''
''// Successor w is in stack S and hence in the current SCC''
''v''.lowlink := min(''v''.lowlink, ''w''.index)
'''end if'''
--[[User:Kalmankeri|Kalmankeri]] ([[User talk:Kalmankeri|talk]]) 15:15, 10 March 2015 (UTC)
| |||