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 18:05:17

>> 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.
> 
> Could you take the output iterator by reference, and change it in-place
> into the new version?

In theory yes, but in practice there are calls like

is_bipartite (..., std::back_inserter (odd_cycle_vector));

which won't allow references for the iterator due to the temporary
back_inserter. From my experience, those calls are much more often than
the case where you really need the final iterator.

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

Matthias Walter