You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
// Note: The next line may look odd - but is correct.
// It says w.index not w.lowlink; that is deliberate and from the original paper
v.lowlink := min(v.lowlink, w.index)
and explains:
Note that v.lowlink := min(v.lowlink, w.index) is the correct way to update v.lowlink if w is on stack. Because w is on the stack already, (v, w) is a back-edge in the DFS tree and therefore w is not in the subtree of v. Because v.lowlink takes into account nodes reachable only through the nodes in the subtree of v we must stop at w and use w.index instead of w.lowlink.
I do not understand what all this means jet, so I was not able to create an example where the function yields the wrong result, but I wanted to let you know anyways.
The text was updated successfully, but these errors were encountered:
I was comparing the
stronglyConnectedComponents
implementation to the pseudocode from Wikipedia (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) and I noticed, that in the following line they do not agree:collection/lib/src/functions.dart
Line 189 in 9db854d
Wikipedia states in the pseudocode:
and explains:
I do not understand what all this means jet, so I was not able to create an example where the function yields the wrong result, but I wanted to let you know anyways.
The text was updated successfully, but these errors were encountered: