Content deleted Content added
Line 217:
As I see, we read the parameter "lowlink" only from child nodes and current node and we write it only to current node. Therefore, we can have this parameter as a local variable and return it from "strongconnect". I. e. we can store "lowlink" on the stack for recursive calls (= [[Depth-first search|DFS]] algorithm stack). In such a way, this algorithm is connected to [[path-based strong component algorithm]]. From the stack of lowlinks we can compute the ''P'' stack. --[[User:Beroal|Beroal]] ([[User talk:Beroal|talk]]) 14:55, 24 June 2013 (UTC)
== Constant time check for a node (vertex) on the stack ==
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)
| |||