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

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-01 13:47:19

On Mon, 1 Mar 2010, Matthias Walter wrote:

>> If possible, I would tar or zip the submission and then send a link to the
>> mailing list. If you don't have a convenient place to put it online, then
>> you upload it to the Boost Vault. I'd put it the Algorithms/graph directory.
>>
>> After posting that, I'll review it and the documentation and then merge it
>> into the trunk. It will probably take a couple of days once you have
>> everything together.
>
> I've uploaded the bipartiteness stuff onto boost vault, as you recommended:
>
> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=bipartite.zip&directory=Algorithms/graph&
>
> The documentation is in the same manner as the other algorithms,
> the example creates two graphs, tests them and prints the partitition
> (1st graph) and the odd-cycle (2nd graph), while the test code calls all
> implemented interfaces and verifies the certificates. The test code uses
> boost/test/minimal.hpp structure.

Since I did not look over the code previously, here are my comments:

libs/ is not a subdirectory of boost/ -- those are two separate top-level 
directories.  The subdirectories under those appear to be correct (don't 
worry about fixing up the jamfiles).

Did you want bipartite_visitor_error to inherit from std::exception?  It 
should have methods like what() in that case as well.

DFS (setting each vertex to the opposite of its parent's color) would take 
care of iterating through all of the source vertices for you (in the 
undirected case).  You could get rid of internal_color_map in that case as 
well -- DFS would handle that internally.

Would you benefit from a one-bit color map for the partition map?  I know 
that BFS and DFS require three colors (but two-color versions could be 
written); do you require that in your partition map as well?

In your example, are_adjacent_vertices() could just iterate over the out 
edges (or adjacent vertices) of u; there is also an edge() function which 
does what you want and is more efficient for some graphs.

There are much simpler ways to create constant graphs than the one you are 
using; this constructor might help you:

template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
                vertices_size_type n,
                edges_size_type m = 0,
                const GraphProperty& p = GraphProperty())

There is an example of how to use it in libs/graph/example/csr-example.cpp 
(for a different graph type, but the constructor is similar).

You can use "using namespace boost;" in examples; it might make the code 
less verbose.

How do your test and example files differ?  It looks like they are roughly 
the same.  The example should only show one use of each of your functions, 
while the test should use the different versions (I do like that you try 
vecS and listS by the way).  For extra credit, you can write a 
bipartite-cc.cpp test modeled on the ones for BFS and DFS.

I like your code and documentation overall.

-- Jeremiah Willcock