From bd4cb096dea79fbde13f8fa5f18cfcccb8ad1548 Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Mon, 15 Dec 2008 03:32:05 -0500
Subject: refactor _traversal a bit to allow alternative bag data structures

---
 lib/Graph/Implicit.pm | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

(limited to 'lib')

diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm
index 28605bd..095de51 100644
--- a/lib/Graph/Implicit.pm
+++ b/lib/Graph/Implicit.pm
@@ -71,18 +71,18 @@ sub is_bipartite {
 # prim with this too
 sub _traversal {
     my $self = shift;
-    my ($start, $code, $insert, $remove) = @_;
-    my @bag;
+    my ($start, $code, $create, $notempty, $insert, $remove) = @_;
+    my $bag = $create->();
     my %marked;
     my %pred;
-    $insert->(\@bag, [undef, $start]);
-    while (@bag) {
-        my ($pred, $vertex) = @{ $remove->(\@bag) };
+    $insert->($bag, [undef, $start], 0);
+    while ($notempty->($bag)) {
+        my ($pred, $vertex) = @{ $remove->($bag) };
         if (not exists $marked{$vertex}) {
             $code->($pred, $vertex);
             $pred{$vertex} = $pred if defined wantarray;
             $marked{$vertex} = 1;
-            $insert->(\@bag, [$vertex, $_]) for $self->neighbors($vertex);
+            $insert->($bag, [$vertex, $$_[0]], $$_[1]) for $self->($vertex);
         }
     }
     return \%pred;
@@ -92,6 +92,8 @@ sub bfs {
     my $self = shift;
     my ($start, $code) = @_;
     return $self->_traversal($start, $code,
+                             sub { [] },
+                             sub { @{ $_[0] } },
                              sub { push @{ $_[0] }, $_[1] },
                              sub { shift @{ $_[0] } });
 }
@@ -100,6 +102,8 @@ sub dfs {
     my $self = shift;
     my ($start, $code) = @_;
     return $self->_traversal($start, $code,
+                             sub { [] },
+                             sub { @{ $_[0] } },
                              sub { push @{ $_[0] }, $_[1] },
                              sub { pop @{ $_[0] } });
 }
-- 
cgit v1.2.3-54-g00ecf