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