summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordoy <doy@tozt.net>2008-12-14 19:13:41 -0500
committerdoy <doy@tozt.net>2008-12-14 19:13:41 -0500
commitf4713853edb7783e36df098e950c507855ddb29c (patch)
treea8f118f1c890a425e8848c3ee749ab5c6971f7d2
parent39db27488e0e5157df81c2c9b67c89f184438868 (diff)
downloadgraph-implicit-f4713853edb7783e36df098e950c507855ddb29c.tar.gz
graph-implicit-f4713853edb7783e36df098e950c507855ddb29c.zip
implement is_bipartite
-rw-r--r--lib/Graph/Implicit.pm20
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