Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-03-04 16:02:16
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 . Most of your comments I
implemented and thus only comment on the interesting ones.
> 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.
> 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.
> 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.
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk