Boost logo

Boost :

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-02-18 08:25:31

On 02/18/10 02:08, Andrew Sutton wrote:
>> 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).
Yes, a version only with a graph (maybe +index-map) is needed and
I also didn't make any effort in using named parameters, yet. For this I
especially want to get feedback whether my approach for returning
the odd-cycle via one iterator is a good one. My headache with it
is that the user won't get the resulting iterator like in std::copy, because
the return-value is used for bipartiteness-predicate.

> 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.
Thank you for this roadmap - I'll try to put some more effort into testing
and docs. As you said we're stuck on HTML, I assume I can gear on
the HTML source of the other docs and write mine in the same manner.

best regards
Matthias Walter

Boost list run by bdawes at, gregod at, cpdaniel at, john at