diff options
author | doy <doy@tozt.net> | 2008-12-14 19:13:41 -0500 |
---|---|---|
committer | doy <doy@tozt.net> | 2008-12-14 19:13:41 -0500 |
commit | f4713853edb7783e36df098e950c507855ddb29c (patch) | |
tree | a8f118f1c890a425e8848c3ee749ab5c6971f7d2 | |
parent | 39db27488e0e5157df81c2c9b67c89f184438868 (diff) | |
download | graph-implicit-f4713853edb7783e36df098e950c507855ddb29c.tar.gz graph-implicit-f4713853edb7783e36df098e950c507855ddb29c.zip |
implement is_bipartite
-rw-r--r-- | lib/Graph/Implicit.pm | 20 |
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 |