diff options
author | doy <doy@tozt.net> | 2008-12-15 03:32:05 -0500 |
---|---|---|
committer | doy <doy@tozt.net> | 2008-12-15 03:32:05 -0500 |
commit | bd4cb096dea79fbde13f8fa5f18cfcccb8ad1548 (patch) | |
tree | 441a98c877a15f8b2bb67b146b0a69e9498757fa | |
parent | 8253f8332095128d312759cdf13398dbfa1aadc8 (diff) | |
download | graph-implicit-bd4cb096dea79fbde13f8fa5f18cfcccb8ad1548.tar.gz graph-implicit-bd4cb096dea79fbde13f8fa5f18cfcccb8ad1548.zip |
refactor _traversal a bit to allow alternative bag data structures
-rw-r--r-- | lib/Graph/Implicit.pm | 16 |
1 files changed, 10 insertions, 6 deletions
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] } }); } |