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-19 05:24:58

>>> Maybe the version taking the out_iterator should be a different function?
>>
>> Taking the suggestion of Andrew, I'd imagine the case where
>> you won't get back a bool from the odd-cycle-version of the
>> bipartiteness test, but the final iterator. Then the graph
>> would be bipartite if and only if nothing was written to
>> that iterator. Testing would then mean to compare both or
>> look at your odd_cycle_vector.
>>
>> Maybe returning both in a std::pair would be another (more
>> elegant?) solution.
>>
> 
> After looking a little more closely at the algorithm, I think there are
> definitey two versions of it. The first is a simple is_bipartite function,
> the other is find_odd_cycle, and the latter should definitely take an output
> iterator.
> 
> I think that breaking this into two will also let you get rid of the helper
> classes and simplify some of implementation a little bit.
> 
> It would be /really/ nice if BFS allowed the visitor to parameterize some of
> the control points so you didn't have to throw an exception :) Of course,
> this is a well known problem.

Hopefully agreeing with that I propose the following interface:

// Simply checks for bipartiteness
bool is_bipartite (const Graph&, IndexMap);

// Same as above, but returns the partition, if bipartite
bool is_bipartite (const Graph&, IndexMap, ColorMap);

// Writes nothing to result if bipartite, i.e. all cycles are even.
OutputIter find_odd_cycle (const Graph&, IndexMap, OutputIter result);

// Same as above, but returns the partition, if bipartite
OutputIter find_odd_cycle (const Graph&, IndexMap, ColorMap, OutputIter
result);

For the 1st and 3rd version I would also add versions without IndexMap,
which use get (vertex_index, g) if the graph has an internal index_map.
If not, one could create an associative one with a map or let the
compilation fail by just _expecting_ get(vertex_index, g) to be valid.

For the 2nd and 4th, this is not possible due to collisions in number of
arguments.

Matthias Walter