Re: [boost] [BGL] Testing a graph for bipartiteness

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-02-17 19:00:06

> > I'm working on a project where I need to determine whether a given graph
> > is bipartite (possible yielding certificates for the two cases). As such
> > a test can be perfectly implemented via BFS and visitor patterns, I
> > wondered why there is no implementation in the BGL. Is there any reason
> > or am I just to blind to find it?
> >
> > If I'm forced to write my own one, how about submitting it to BGL?
> >
> 
> BGL algorithms are largely contributed by people that have found a need for
> them--there's not currently an active development plan. If you've written
> such an algorithm (or will be writing one), feel free to submit it. We can
> review the work and hopefully integrate it into the library.

Okay, I managed to implement the bipartiteness check in the following interface:

bool is_bipartite (const Graph&, IndexMap, ColorMap, OutputIterator)

Graph and IndexMap are obvious, the 3rd parameter will contain the 2-partition
if the graph is bipartite. If not, a vertex sequence describing an odd-cycle
will be written to the output iterator. There also exists a version
without the last parameter, because in that case there's less to do.

1. Are there any design hints for the interface or implementation?
2. What is missing for integration into BGL? Is my code quality acceptable?
3. After (hopefully) getting feedback, whom shall I contact for integration?

If you want to have a look at the code:

http://xammy.xammy.homelinux.net/bipartite.hpp
http://xammy.xammy.homelinux.net/bipartite_test.cpp

best regards
Matthias Walter