From 46b67e7b8d4ce9efbb69965f9bb5c9fc681f5448 Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sun, 14 Dec 2008 03:00:54 -0500
Subject: allow passing in a scorer function to dijkstra in order to find a
 specific tile while searching

---
 lib/Graph/Implicit.pm | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

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;
-- 
cgit v1.2.3-54-g00ecf