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. Andrew Sutton andrew.n.sutton@gmail.com