
Boost : 
Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 20100222 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk