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.
I like it :) Andrew Sutton andrew.n.sutton@gmail.com