
Boost : 
Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 20100219 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 oddcycleversion 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk