secret
Created

hic sunt leones

  • Download Gist
findMinCycles.pl
Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
sub findMinCycles {
# hic sunt leones
# sorry for the terse code, I promise it works, no need to touch it :)
my ($self, $v, $g, $i, $s) = @_;
 
if (exists $i->{$v}) {
my @c = @{$s}[$i->{$v}..$#$s];
my $k = (sort { @{$g->{$c[$b]}}<=> @{$g->{$c[$a]}} } (0 .. $#c))[0];
push @c, $v;
local $" = ' -> ';
$self->error("Dependency cycle detected: @c");
$self->verbose("DEBUG: removing $c[$k] -> $c[$k+1]");
my $e = $g->{$c[$k]};
my $w = $c[$k+1];
for my $j (0 .. $#$e) {
if ($w eq $e->[$j]) {
splice @$e, $j, 1;
last;
}
}
} elsif (defined $g->{$v}) {
push @$s, $v;
$i->{$v} = $#$s;
my @e = @{$g->{$v}};
foreach my $w (@e) {
$self->findMinCycles($w, $g, $i, $s);
}
delete $i->{$v};
pop @$s;
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.