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