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-03-02 17:51:43

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

Fixed

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

The implementation now uses DFS instead of BFS, has no internal color
map anymore and no loop for iterating through the graph's components.
Furthermore it uses the one-bit-colormap if none is given.

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

Switched the test-code to lookup_edge. The example code also contained
the certificate-verifying functions, but never used them. I just forgot
to remove them.

> There are much simpler ways to create constant graphs than the one you
> are using;

Fixed to a really small version.

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

Done :-)

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

I think it's good to let the example show find_odd_cycle and
is_bipartite functions. Thus I kept both graphs. But due to your
previous hints, the code is really clean now, so that it shouldn't be
too much for a new user.

Here's the link again:

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=bipartite.zip&directory=Algorithms/graph&

Thanks for the nice hints and actually for reviewing, too!
Matthias Walter