Tarjan: Difference between revisions

Line 273:

=={{header|Perl}}==

<lang perl>use ~~feature 'state'~~;

<lang perl>use 5.016;

use feature 'state';

use List::Util qw(min);

use experimental qw(lexical_subs);

sub tarjan {

~~our~~(%k) = @_;

my (%k) = @_;

~~our~~(%onstack, %index, %lowlink, @stack);

my (%onstack, %index, %lowlink, @stack, @connected);

our @connected = ();

sub strong_connect {

my sub strong_connect {

my($vertex) = @_;

my ($vertex, $i) = @_;

~~state~~ $index = 0;

$index{$vertex} = $i;

$~~index~~{$vertex} = ~~$index~~;

$lowlink{$vertex} = $i + 1;

$~~lowlink~~{$vertex} = ~~$index++~~;

$onstack{$vertex} = 1;

push @stack, $vertex;

$~~onstack~~{$vertex} ~~= 1;~~

for my $connection (@{$k{$vertex}}) {

~~for~~ my ~~$connection~~ (@{$k{$~~vertex}~~}) {

if (not defined $index{$connection}) {

if ~~(not~~ ~~$index{~~$connection}) {

__SUB__->($connection, $i + 1);

~~strong_connect~~($connection);

$lowlink{$vertex} = min($lowlink{$connection}, $lowlink{$vertex});

}

$lowlink{$vertex} = min($lowlink{$connection},$lowlink{$vertex});

} elsif ($onstack{$connection}) {

elsif ($onstack{$connection}) {

$lowlink{$vertex} = min($~~lowlink~~{$connection},$lowlink{$vertex});

$lowlink{$vertex} = min($index{$connection}, $lowlink{$vertex});

}

if ($lowlink{$vertex} eq $index{$vertex}) {

Line 307:

Line 308:

for (sort keys %k) {

strong_connect($_) unless $index{$_}

strong_connect($_, 0) unless $index{$_};

}

@connected

@connected;

}

my %test1 = (

0 => [1],

1 => [2],

2 => [0],

3 => [1, 2, 4],

4 => [3, 5],

5 => [2, 6],

6 => [5],

7 => [4, 6, 7]

);

my %test2 = (

'Andy' => ['Bart'],

'Bart' => ['Carl'],

'Carl' => ['Andy'],

'Dave' => [qw<Bart Carl Earl>],

'Earl' => [qw<Dave Fred>],

'Fred' => [qw<Carl Gary>],

'Gary' => ['Fred'],

'Hank' => [qw<Earl Gary Hank>]

);

print "Strongly connected components:\n";