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

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-02-17 20:08:02

>
> 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?
>

That actually looks like a really good start -- I haven't had a chance to go
over it in detail, yet. The only thing I would want from the interface is a
one parameter version: is_bipartite(g).

I probably won't be able to close until next week, but either Jeremiah or I
will be responsible for integrating it. To be complete, you should write a
boost test file (I didn't look at the one provided, but if it has some
asserts, its probably also a good start), a page of documentation (we're
still stuck on HTML), and probably an example.

Andrew Sutton
andrew.n.sutton_at_[hidden]