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 20:42:36

On Tue, 2 Mar 2010, Matthias Walter wrote:

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

The code is much simpler now.  Here are a few more comments:

boost/graph/bipartite.hpp:

You might want to use the EventVisitor interfaces for defining your DFS 
visitor.  You would need to write two function objects, one for each event 
point, but you could then just chain in a predecessor recorder (or not if 
you didn't want one) without needing to store it or call it yourself; 
boost::dfs_visitor would take care of the dispatching.  Doing it this way 
would get rid of empty_recorder as well.  You might want to consider that, 
but it isn't a requirement.

I think you might need <exception> to get std::exception, but I am not 
sure.

You can take the partition_map by value in bipartite_visitor; property 
maps are intended to be cheap to copy.

In tree_edge, you might want a typedef for the partition map's value type 
and the instance of color_traits for it.  That would simplify several of 
the lines.

In is_bipartite, is there a reason to initialize the partition map?  It 
should be filled in by DFS and DFS never reads entries that were not 
written earlier by DFS if I understand the code correctly.

In the second overload of is_bipartite, color_t does not appear to be 
used.  Also, did you want to rename color_map to partition_map?  That 
would differentiate it from DFS's color map.

In find_odd_cycle, I do not believe that you need to initialize the 
partition map; you might also want to use put() on the predecessor map, 
especially as the vertex index numbering does not need to be the same as 
the order the vertices are produced by the vertex iterators.

Could you ever get a common tail in the two paths in an odd cycle?  Each 
vertex can only have one predecessor, and the DFS should stop immediately 
when a cycle is found.  If you are going to remove elements that way, 
std::mismatch might be a cleaner way to find how many to remove; at least 
remove the side effect in the test of the while loop (possibly move all of 
the stuff in the test after the last && into the loop body and use a 
break).

You might want to use std::reverse_copy rather than copy on a 
reverse_iterator, but I am not sure exactly what the difference is, so you 
might also want to keep it the way it is.

In the second overload of find_odd_cycle, color_t appears to be unused and 
you might want to change color_map to partition_map.

libs/graph/doc/find_odd_cycle.html: no comments

libs/graph/doc/is_bipartite.html:

BFS needs to be changed to DFS.

HTML quotes should be either normal text quotes or the character entities 
for smart quotes; LaTeX quotes don't look right.

The partition map just be readable as well as writable; this probably 
applies to find_odd_cycle as well.

Did you want the titles of the documentation pages to both be 
"Bipartiteness"?  You might want to change them to the names of the 
individual functions.

libs/graph/example/bipartite_example.cpp:

You should not use the index maps in the example; use the default ones to 
simplify the code.

The include for "bipartite.hpp" should be <boost/graph/bipartite.hpp>; 
this might apply to your tests as well.

"odd-cycle" should be just "odd cycle" or "odd-length cycle".

When printing out the partition, use a loop over the vertices rather than 
looping over the indices.

I think the example is fairly clean now, and shows the essential parts of 
your functions clearly.

libs/graph/test/bipartite_test.cpp: no comments

I think there are largely cosmetic things left to do now, so your code is 
almost ready to put in.  Does it pass the Boost inspect tool (run from the 
top of your extracted tarball, outside boost/ and libs/)?

-- Jeremiah Willcock