4 Mar
2010
4 Mar
'10
9:02 p.m.
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. > > 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 reviewing! Matthias Walter [1] http://www.boostpro.com/vault/index.php?action=downloadfile&filename=bipartite.zip&directory=Algorithms/graph&