From 844fe2c576b1ba53b0fc88c8a2a1c3c1bf868dc9 Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sun, 14 Dec 2008 17:44:40 -0500
Subject: implement bfs and dfs

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

diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm
index 2fad054..239bf75 100644
--- a/lib/Graph/Implicit.pm
+++ b/lib/Graph/Implicit.pm
@@ -35,10 +35,36 @@ sub neighbors {
 
 # traversal
 
+sub _traversal {
+    my $self = shift;
+    my ($start, $code, $insert, $remove) = @_;
+    my @bag;
+    my %marked;
+    $insert->(\@bag, $start);
+    while (@bag) {
+        my $vertex = $remove->(\@bag);
+        if (not exists $marked{$vertex}) {
+            $code->($vertex);
+            $marked{$vertex} = 1;
+            $insert->(\@bag, $_) for $self->neighbors($vertex);
+        }
+    }
+}
+
 sub bfs {
+    my $self = shift;
+    my ($start, $code) = @_;
+    return $self->_traversal($start, $code,
+                             sub { push @{ $_[0] }, $_[1] },
+                             sub { shift @{ $_[0] } });
 }
 
 sub dfs {
+    my $self = shift;
+    my ($start, $code) = @_;
+    return $self->_traversal($start, $code,
+                             sub { push @{ $_[0] }, $_[1] },
+                             sub { pop @{ $_[0] } });
 }
 
 sub iddfs {
-- 
cgit v1.2.3-54-g00ecf