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-04 16:14:38

On Thu, 4 Mar 2010, Matthias Walter wrote:

> On 03/03/2010 02:42 AM, Jeremiah Willcock wrote:
>> 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.
>
> I updated the archive at boost vault [1]. Most of your comments I
> implemented and thus only comment on the interesting ones.
>
>> boost/graph/bipartite.hpp:
>>
>> 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.
>
> I did it to be sure the root node of each component has some "valid"
> color. By thinking about your commments I realized that this can also be
> handled by a start_vertex method in the visitor, which I implemented now.

OK.

>> 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.
>
> With the start_vertex implemented now, there are three function objects
> necessary to use the EventVisitor interfaces, which sounds like a good
> reason to me to keep it as one visitor struct. This way, the
> functionality belonging together also sticks together.

That makes sense.  Maybe you want your visitor to be a wrapper around an 
arbitrary visitor, though?  I.e., you would call the nested visitor on all 
event points, even those you don't handle.

>> 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).
>
> std::mismatch requires the second sequence be at least as long as the
> first sequence. This implies a possible swap and makes the code somewhat
> less readable, due to reverse iterators (the common-vertices are at the
> end of the sequence). But I still changed the code, as skipping should
> be better than removing.

But would you ever have anything to remove to begin with?  In the logic of 
your code, I do not see a way to have a common tail between the two paths.

>> 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/)?
>
> Done. Nothing broken and docs are W3C conforming :-) Thanks again for
> reviewing!

OK.

-- Jeremiah Willcock