From f6e75f5852fb8a7cecee8e3a313ea0a5d39700fd Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sat, 7 Feb 2009 13:01:29 -0500
Subject: huh, didn't i add this before?

---
 t/002-traversal.t | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)
 create mode 100644 t/002-traversal.t

diff --git a/t/002-traversal.t b/t/002-traversal.t
new file mode 100644
index 0000000..3bb5d19
--- /dev/null
+++ b/t/002-traversal.t
@@ -0,0 +1,71 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Test::More tests => 48;
+use Test::Deep;
+use Graph::Implicit;
+
+sub is_tree {
+    my ($graph, $start) = @_;
+    # a tree is an acyclic graph with E=V-1
+    my $v = keys %$graph;
+    my $e = (grep { defined } values %$graph);
+
+    VERTEX: for my $vertex (keys %$graph) {
+        next unless defined $graph->{$vertex};
+        my %visited;
+        $visited{$vertex} = 1;
+        my $iter = $vertex;
+        while (1) {
+            $iter = $graph->{$iter};
+            next VERTEX if !defined $iter;
+            return 0 if $visited{$iter};
+            $visited{$iter} = 1;
+        }
+    }
+
+    return $e == $v - 1;
+}
+
+my %graph = (
+    a => [qw/  b c          /],
+    b => [qw/      d   f   h/],
+    c => [qw/a       e     h/],
+    d => [qw/a b c d e f g h/],
+    e => [qw/    c d        /],
+    f => [qw/               /],
+    g => [qw/            g  /],
+    h => [qw/          f g  /],
+);
+my %reachable = (
+    a => [qw/a b c d e f g h/],
+    b => [qw/a b c d e f g h/],
+    c => [qw/a b c d e f g h/],
+    d => [qw/a b c d e f g h/],
+    e => [qw/a b c d e f g h/],
+    f => [qw/          f    /],
+    g => [qw/            g  /],
+    h => [qw/          f g h/],
+);
+my $edge_calculator = sub {
+    my $vertex = shift;
+    return map { [$_, 1] } @{ $graph{$vertex} };
+};
+
+my $graph = Graph::Implicit->new($edge_calculator);
+for my $traversal (qw/bfs dfs/) {
+    for my $vertex (qw/a b c d e f g h/) {
+        my @visited;
+        my $tree = $graph->$traversal($vertex, sub { push @visited, $_[1] });
+        cmp_bag(\@visited, $reachable{$vertex},
+                "$traversal visits each node exactly once from $vertex");
+        ok(is_tree($tree),
+           "$traversal creates a tree from $vertex");
+        SKIP: {
+            skip "don't know a good algorithm for this", 1;
+            no strict 'refs';
+            ok(&{ "check_$traversal" }($tree),
+            "$traversal is in the correct order from $vertex");
+        }
+    }
+}
-- 
cgit v1.2.3-54-g00ecf