diff options
author | doy <doy@tozt.net> | 2008-12-14 03:00:54 -0500 |
---|---|---|
committer | doy <doy@tozt.net> | 2008-12-14 03:00:54 -0500 |
commit | 46b67e7b8d4ce9efbb69965f9bb5c9fc681f5448 (patch) | |
tree | 20298aa67d4132afa4a8f560353c7e00dd2874d0 | |
parent | 06ccaa398e3dc26b3cd93c3639dac48089451ebd (diff) | |
download | graph-implicit-46b67e7b8d4ce9efbb69965f9bb5c9fc681f5448.tar.gz graph-implicit-46b67e7b8d4ce9efbb69965f9bb5c9fc681f5448.zip |
allow passing in a scorer function to dijkstra in order to find a specific tile while searching
-rw-r--r-- | lib/Graph/Implicit.pm | 10 |
1 files changed, 9 insertions, 1 deletions
diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm index 9acf2ce..5f6d535 100644 --- a/lib/Graph/Implicit.pm +++ b/lib/Graph/Implicit.pm @@ -22,15 +22,23 @@ sub new { 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} })) { @@ -43,7 +51,7 @@ sub dijkstra { } } } - return \%pred; + return \%pred, $max_vert; } 1; |