From db3904fd6b81e3283bb27d19c182c0926e34a7ce Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sun, 14 Dec 2008 18:19:03 -0500
Subject: return the spanning tree generated by graph traversals

---
 lib/Graph/Implicit.pm | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm
index 49dde40..df3a434 100644
--- a/lib/Graph/Implicit.pm
+++ b/lib/Graph/Implicit.pm
@@ -35,22 +35,25 @@ sub neighbors {
 
 # traversal
 
-# XXX: if we can generalize @bag to allow for a heap, and store edges rather
-# than vertices in the bag, then we can implement prim with this too
+# XXX: if we can generalize @bag to allow for a heap, then we can implement
+# prim with this too
 sub _traversal {
     my $self = shift;
     my ($start, $code, $insert, $remove) = @_;
     my @bag;
     my %marked;
-    $insert->(\@bag, $start);
+    my %pred;
+    $insert->(\@bag, [undef, $start]);
     while (@bag) {
-        my $vertex = $remove->(\@bag);
+        my ($pred, $vertex) = @{ $remove->(\@bag) };
         if (not exists $marked{$vertex}) {
-            $code->($vertex);
+            $code->($pred, $vertex);
+            $pred{$vertex} = $pred;
             $marked{$vertex} = 1;
             $insert->(\@bag, $_) for $self->neighbors($vertex);
         }
     }
+    return \%pred;
 }
 
 sub bfs {
-- 
cgit v1.2.3-54-g00ecf