From f4713853edb7783e36df098e950c507855ddb29c Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sun, 14 Dec 2008 19:13:41 -0500
Subject: implement is_bipartite

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

diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm
index 50f7207..effe18d 100644
--- a/lib/Graph/Implicit.pm
+++ b/lib/Graph/Implicit.pm
@@ -3,6 +3,7 @@ use strict;
 use warnings;
 package Graph::Implicit;
 use Heap::Simple;
+use List::MoreUtils qw/apply/;
 
 =for example
 
@@ -43,6 +44,25 @@ sub neighbors {
     return $self->($from);
 }
 
+sub is_bipartite {
+    my $self = shift;
+    my ($from) = @_;
+    my $ret = 1;
+    BIPARTITE: {
+        my %colors = ($from => 0);
+        no warnings 'exiting';
+        $self->bfs($from, sub {
+            my $vertex = $_[1];
+            apply {
+                last BIPARTITE if $colors{$vertex} == $colors{$_};
+                $colors{$_} = not $colors{$vertex};
+            } $self->neighbors($vertex)
+        });
+        return 1;
+    }
+    return 0;
+}
+
 # traversal
 
 # XXX: if we can generalize @bag to allow for a heap, then we can implement
-- 
cgit v1.2.3