Possible error in stronglyConnectedComponents

[Quijx]

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

lowLinks[vertex] = math.min(lowLinks[vertex]!, lowLinks[successor]!);

Wikipedia states in the pseudocode:

// 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.

[lrhn]

Thanks for the heads up. I personally have no idea what it means either.

@nex3 … was it you who wrote that code?