1 files changed, 20 insertions, 0 deletions
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