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

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-02-22 08:14:30

> 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