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);
Okay, I split the two functionalities in the above interface now and wrote some documentation. It can be found here: http://xammy.xammy.homelinux.net/bipartite.hpp http://xammy.xammy.homelinux.net/is_bipartite.html http://xammy.xammy.homelinux.net/find_odd_cycle.html
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.
I chose the latter decision, so the "short" versions expect the graph to have a vertex_index property associated. I will write tests and put some concept checks into the code this week or next. @Andrew Sutton: Shall I post to the list again then or contact you directly when finished with writing the tests? Matthias Walter