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