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-02 13:16:55

On Tue, 2 Mar 2010, Matthias Walter wrote:

> On 03/01/10 19:47, Jeremiah Willcock wrote:
>> On Mon, 1 Mar 2010, Matthias Walter wrote:
>>> 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.
>>
>> 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).
> Okay, will fix this issue on the next try.
>
>>
>> Did you want bipartite_visitor_error to inherit from std::exception?
>> It should have methods like what() in that case as well.
> Is it recommended or necessary to inherit from std::exception? I will
> dig into the other implementations and adopt from that behavior.

The Boost guidelines recommend it: 
http://www.boost.org/community/error_handling.htmlB

>> 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.
> Ah, didn't recognize that DFS searches in the whole graph while BFS only
> in the component. Thought, they'd behave the same. Sounds like a good
> reason to use DFS and simplify the code this way. Thanks!
>>
>> 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?
> The partition map only uses white() and black() from color_traits, so a
> one-bit color map would be a nice thing to have.

OK.  It should not be too hard to write.

>> 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.

Are you thinking of using one of these options?  Actually, looking at BGL 
some more, there is lookup_edge (in boost/graph/lookup_edge.hpp) that is a 
wrapper that uses edge() when possible and an out edge scan otherwise. 
That will work on more graph types.

>> 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).
> Okay, I will dig into your suggested improvements and see what I can do.
>>
>> 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.
> Well, the example code only uses the three (from my point of view) most
> important interfaces:
> - simple test without certificates
> - test yielding partition map
> - test yielding odd-cycle
> The test code tests _all_ interfaces. But the graphs are the same in
> both cases.

I think the example should only use one graph type, and possibly only one 
graph.  It can just print out the result as well; remember that its 
purpose is to show a small example of how to use your functions in a way 
that is clear and easy to read, not to be complete.

-- Jeremiah Willcock