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-04 17:36:17

On 03/04/2010 10:14 PM, Jeremiah Willcock wrote:
> 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.
>>
>>> 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.

I must admin that I don't really understand, what you mean. Around what
other visitor shall I wrap it? Or shall I split the current visitor into
more smaller ones which wrap each other somehow?

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

In the case, a monochromatic non-tree edge is found, the exception is
thrown. The paths are from the endpoints to the root-node (of the rooted
tree, DFS already has constructed) in the component in which which both
vertices reside. As there is an edge, they definitely are in one
component and thus share at least the root node.

Matthias Walter