blob: 2fc12abac428dba265aed9555f34e2de444c5986 (
plain) (
blame)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#!/usr/bin/perl
use strict;
use warnings;
package Graph::Implicit;
use Heap::Simple;
=for example
sub {
map { [$_, $_->intrinsic_cost] }
shift->grep_adjacent(sub { shift->is_walkable })
}
=cut
sub new {
my $class = shift;
my $edge_calculator = shift;
return bless $edge_calculator, $class;
}
sub dijkstra {
my $self = shift;
my $from = shift;
my $scorer = shift;
my $pq = Heap::Simple->new(elements => "Any");
my %neighbors;
my ($max_vert, $max_score) = (undef, 0);
my %dist = ($from => 0);
my %pred = ($from => undef);
$pq->key_insert(0, $from);
while ($pq->count) {
my $cost = $pq->top_key;
my ($vertex, $path) = @{ $pq->extract_top };
if ($scorer) {
my $score = $scorer->($vertex);
return (\%pred, $vertex) if $score eq 'q';
($max_vert, $max_score) = ($vertex, $score)
if ($score > $max_score);
}
$neighbors{$vertex} = [$self->($vertex)]
unless exists $neighbors{$vertex};
for my $neighbor (@{ $neighbors{$vertex} }) {
my ($vert_n, $weight_n) = @{ $neighbor };
my $dist = $cost + $weight_n;
if (!defined $dist{$vert_n} || $dist < $dist{$vert_n}) {
$dist{$vert_n} = $dist;
$pred{$vert_n} = $vertex;
$pq->key_insert($dist, $vert_n);
}
}
}
return \%pred, $max_vert;
}
1;
|
