Talk:Tarjan

Correctness?

The pseudo code from Wikipedia does not seem correct. I ran into problems when trying to translate it into Python. To corroborate, I tested the Perl code on the task page, with a simple graph where there are only two nodes with one directed edge between them: <lang perl>my %test1 = (

 0 => [1],

);

print "Strongly connected components:\n"; print join(', ', sort @$_) . "\n" for tarjan(%test1);</lang> which outputs

Strongly connected components:
1
0

Any thoughts? --Ledrug (talk) 08:37, 9 March 2020 (UTC)

   Perhaps the task description needs better detail. Note that the examples never show reciprocal connections -- if there is a 2 => 4,  
   we never see 4 => 2 listed in the data, for some reason?
   --Wherrera (talk) 08:19, 9 March 2020 (UTC)

That can't be right. "Strongly connected" means between two nodes A and B, there is a path from A to B *and* there is a path from B to A, which only makes sense if edges are directed. If all connections are bidirectional, there is no difference between "connected" and "strongly connected", and the algorithm only needs a depth-first traversal without much of the bookkeeping at all. --Ledrug (talk) 08:37, 9 March 2020 (UTC)

EDIE: Never mind: a node not strongly connected to anything else is considered to form its own component, so the above output is correct. Silly me. --Ledrug (talk) 09:28, 9 March 2020 (UTC)

Ah, you mean that [[0], [1]] and [0, 1] are different answers. I see. I guess that the lack of any reciprocal connections is just the way the examples are written then. I'll correct my response. --Wherrera (talk) 09:36, 9 March 2020 (UTC)

Task description

We should really be putting more effort into readable and complete task descriptions.

I know wikipedia is unlikely to go away, and is fairly stable, but task description by reference is still a bad habit to fall into. --Rdm (talk) 22:35, 15 May 2023 (UTC)