Re: [boost] [BGL] Testing a graph for bipartiteness

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-02-19 08:37:13

> 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_at_[hidden]