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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#!/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;
}
# generic information
sub vertices {
}
sub edges {
}
sub neighbors {
my $self = shift;
my ($from) = @_;
return $self->($from);
}
# traversal
sub bfs {
}
sub dfs {
}
sub iddfs {
}
# minimum spanning tree
sub boruvka {
}
sub prim {
}
sub kruskal {
}
# single source shortest path
sub dijkstra {
my $self = shift;
my ($from, $scorer) = @_;
return $self->astar($from, sub { 0 }, $scorer);
}
sub astar {
my $self = shift;
my ($from, $heuristic, $scorer) = @_;
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->neighbors($vertex)]
unless exists $neighbors{$vertex};
for my $neighbor (@{ $neighbors{$vertex} }) {
my ($vert_n, $weight_n) = @{ $neighbor };
my $dist = $cost + $weight_n + $heuristic->($vertex, $vert_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;
}
sub bellman_ford {
}
# all pairs shortest path
sub johnson {
}
sub floyd_warshall {
}
1;
|
