[BGL] Testing a graph for bipartiteness
Hi, I'm working on a project where I need to determine whether a given graph is bipartite (possible yielding certificates for the two cases). As such a test can be perfectly implemented via BFS and visitor patterns, I wondered why there is no implementation in the BGL. Is there any reason or am I just to blind to find it? If I'm forced to write my own one, how about submitting it to BGL? best regards Matthias Walter
I'm working on a project where I need to determine whether a given graph is bipartite (possible yielding certificates for the two cases). As such a test can be perfectly implemented via BFS and visitor patterns, I wondered why there is no implementation in the BGL. Is there any reason or am I just to blind to find it?
If I'm forced to write my own one, how about submitting it to BGL?
BGL algorithms are largely contributed by people that have found a need for them--there's not currently an active development plan. If you've written such an algorithm (or will be writing one), feel free to submit it. We can review the work and hopefully integrate it into the library. Andrew Sutton andrew.n.sutton@gmail.com
I'm working on a project where I need to determine whether a given graph is bipartite (possible yielding certificates for the two cases). As such a test can be perfectly implemented via BFS and visitor patterns, I wondered why there is no implementation in the BGL. Is there any reason or am I just to blind to find it?
If I'm forced to write my own one, how about submitting it to BGL?
BGL algorithms are largely contributed by people that have found a need for them--there's not currently an active development plan. If you've written such an algorithm (or will be writing one), feel free to submit it. We can review the work and hopefully integrate it into the library.
Okay, I managed to implement the bipartiteness check in the following interface: bool is_bipartite (const Graph&, IndexMap, ColorMap, OutputIterator) Graph and IndexMap are obvious, the 3rd parameter will contain the 2-partition if the graph is bipartite. If not, a vertex sequence describing an odd-cycle will be written to the output iterator. There also exists a version without the last parameter, because in that case there's less to do. 1. Are there any design hints for the interface or implementation? 2. What is missing for integration into BGL? Is my code quality acceptable? 3. After (hopefully) getting feedback, whom shall I contact for integration? If you want to have a look at the code: http://xammy.xammy.homelinux.net/bipartite.hpp http://xammy.xammy.homelinux.net/bipartite_test.cpp best regards Matthias Walter
Okay, I managed to implement the bipartiteness check in the following interface:
bool is_bipartite (const Graph&, IndexMap, ColorMap, OutputIterator)
Graph and IndexMap are obvious, the 3rd parameter will contain the 2-partition if the graph is bipartite. If not, a vertex sequence describing an odd-cycle will be written to the output iterator. There also exists a version without the last parameter, because in that case there's less to do.
1. Are there any design hints for the interface or implementation? 2. What is missing for integration into BGL? Is my code quality acceptable? 3. After (hopefully) getting feedback, whom shall I contact for integration?
That actually looks like a really good start -- I haven't had a chance to go over it in detail, yet. The only thing I would want from the interface is a one parameter version: is_bipartite(g). I probably won't be able to close until next week, but either Jeremiah or I will be responsible for integrating it. To be complete, you should write a boost test file (I didn't look at the one provided, but if it has some asserts, its probably also a good start), a page of documentation (we're still stuck on HTML), and probably an example. Andrew Sutton andrew.n.sutton@gmail.com
On 02/18/10 02:08, Andrew Sutton wrote:
Okay, I managed to implement the bipartiteness check in the following interface:
bool is_bipartite (const Graph&, IndexMap, ColorMap, OutputIterator)
Graph and IndexMap are obvious, the 3rd parameter will contain the 2-partition if the graph is bipartite. If not, a vertex sequence describing an odd-cycle will be written to the output iterator. There also exists a version without the last parameter, because in that case there's less to do.
1. Are there any design hints for the interface or implementation? 2. What is missing for integration into BGL? Is my code quality acceptable? 3. After (hopefully) getting feedback, whom shall I contact for integration?
That actually looks like a really good start -- I haven't had a chance to go over it in detail, yet. The only thing I would want from the interface is a one parameter version: is_bipartite(g).
Yes, a version only with a graph (maybe +index-map) is needed and I also didn't make any effort in using named parameters, yet. For this I especially want to get feedback whether my approach for returning the odd-cycle via one iterator is a good one. My headache with it is that the user won't get the resulting iterator like in std::copy, because the return-value is used for bipartiteness-predicate.
I probably won't be able to close until next week, but either Jeremiah or I will be responsible for integrating it. To be complete, you should write a boost test file (I didn't look at the one provided, but if it has some asserts, its probably also a good start), a page of documentation (we're still stuck on HTML), and probably an example.
Thank you for this roadmap - I'll try to put some more effort into testing and docs. As you said we're stuck on HTML, I assume I can gear on the HTML source of the other docs and write mine in the same manner. best regards Matthias Walter
Yes, a version only with a graph (maybe +index-map) is needed and
I also didn't make any effort in using named parameters, yet. For this I especially want to get feedback whether my approach for returning the odd-cycle via one iterator is a good one. My headache with it is that the user won't get the resulting iterator like in std::copy, because the return-value is used for bipartiteness-predicate.
Having a version that takes only a graph is a good thing. I tend to avoid named params also, so you shouldn't feel that building such an implementation is necessary. Maybe the version taking the out_iterator should be a different function? Andrew Sutton andrew.n.sutton@gmail.com
Matthias Walter wrote:
For this I especially want to get feedback whether my approach for returning the odd-cycle via one iterator is a good one. My headache with it is that the user won't get the resulting iterator like in std::copy, because the return-value is used for bipartiteness-predicate.
Could you take the output iterator by reference, and change it in-place into the new version? John Bytheway
For this I especially want to get feedback whether my approach for returning the odd-cycle via one iterator is a good one. My headache with it is that the user won't get the resulting iterator like in std::copy, because the return-value is used for bipartiteness-predicate.
Could you take the output iterator by reference, and change it in-place into the new version?
In theory yes, but in practice there are calls like is_bipartite (..., std::back_inserter (odd_cycle_vector)); which won't allow references for the iterator due to the temporary back_inserter. From my experience, those calls are much more often than the case where you really need the final iterator.
Maybe the version taking the out_iterator should be a different function?
Taking the suggestion of Andrew, I'd imagine the case where you won't get back a bool from the odd-cycle-version of the bipartiteness test, but the final iterator. Then the graph would be bipartite if and only if nothing was written to that iterator. Testing would then mean to compare both or look at your odd_cycle_vector. Maybe returning both in a std::pair would be another (more elegant?) solution. Matthias Walter
Maybe the version taking the out_iterator should be a different function?
Taking the suggestion of Andrew, I'd imagine the case where you won't get back a bool from the odd-cycle-version of the bipartiteness test, but the final iterator. Then the graph would be bipartite if and only if nothing was written to that iterator. Testing would then mean to compare both or look at your odd_cycle_vector.
Maybe returning both in a std::pair would be another (more elegant?) solution.
After looking a little more closely at the algorithm, I think there are definitey two versions of it. The first is a simple is_bipartite function, the other is find_odd_cycle, and the latter should definitely take an output iterator. I think that breaking this into two will also let you get rid of the helper classes and simplify some of implementation a little bit. It would be /really/ nice if BFS allowed the visitor to parameterize some of the control points so you didn't have to throw an exception :) Of course, this is a well known problem. Andrew Sutton andrew.n.sutton@gmail.com
Maybe the version taking the out_iterator should be a different function?
Taking the suggestion of Andrew, I'd imagine the case where you won't get back a bool from the odd-cycle-version of the bipartiteness test, but the final iterator. Then the graph would be bipartite if and only if nothing was written to that iterator. Testing would then mean to compare both or look at your odd_cycle_vector.
Maybe returning both in a std::pair would be another (more elegant?) solution.
After looking a little more closely at the algorithm, I think there are definitey two versions of it. The first is a simple is_bipartite function, the other is find_odd_cycle, and the latter should definitely take an output iterator.
I think that breaking this into two will also let you get rid of the helper classes and simplify some of implementation a little bit.
It would be /really/ nice if BFS allowed the visitor to parameterize some of the control points so you didn't have to throw an exception :) Of course, this is a well known problem.
Hopefully agreeing with that I propose the following interface: // Simply checks for bipartiteness bool is_bipartite (const Graph&, IndexMap); // Same as above, but returns the partition, if bipartite bool is_bipartite (const Graph&, IndexMap, ColorMap); // Writes nothing to result if bipartite, i.e. all cycles are even. OutputIter find_odd_cycle (const Graph&, IndexMap, OutputIter result); // Same as above, but returns the partition, if bipartite OutputIter find_odd_cycle (const Graph&, IndexMap, ColorMap, OutputIter result); For the 1st and 3rd version I would also add versions without IndexMap, which use get (vertex_index, g) if the graph has an internal index_map. If not, one could create an associative one with a map or let the compilation fail by just _expecting_ get(vertex_index, g) to be valid. For the 2nd and 4th, this is not possible due to collisions in number of arguments. Matthias Walter
Hopefully agreeing with that I propose the following interface:
// Simply checks for bipartiteness bool is_bipartite (const Graph&, IndexMap);
// Same as above, but returns the partition, if bipartite bool is_bipartite (const Graph&, IndexMap, ColorMap);
// Writes nothing to result if bipartite, i.e. all cycles are even. OutputIter find_odd_cycle (const Graph&, IndexMap, OutputIter result);
// Same as above, but returns the partition, if bipartite OutputIter find_odd_cycle (const Graph&, IndexMap, ColorMap, OutputIter result);
For the 1st and 3rd version I would also add versions without IndexMap, which use get (vertex_index, g) if the graph has an internal index_map. If not, one could create an associative one with a map or let the compilation fail by just _expecting_ get(vertex_index, g) to be valid.
For the 2nd and 4th, this is not possible due to collisions in number of arguments.
I like it :) Andrew Sutton andrew.n.sutton@gmail.com
Hopefully agreeing with that I propose the following interface:
// Simply checks for bipartiteness bool is_bipartite (const Graph&, IndexMap);
// Same as above, but returns the partition, if bipartite bool is_bipartite (const Graph&, IndexMap, ColorMap);
// Writes nothing to result if bipartite, i.e. all cycles are even. OutputIter find_odd_cycle (const Graph&, IndexMap, OutputIter result);
// Same as above, but returns the partition, if bipartite OutputIter find_odd_cycle (const Graph&, IndexMap, ColorMap, OutputIter result);
Okay, I split the two functionalities in the above interface now and wrote some documentation. It can be found here: http://xammy.xammy.homelinux.net/bipartite.hpp http://xammy.xammy.homelinux.net/is_bipartite.html http://xammy.xammy.homelinux.net/find_odd_cycle.html
For the 1st and 3rd version I would also add versions without IndexMap, which use get (vertex_index, g) if the graph has an internal index_map. If not, one could create an associative one with a map or let the compilation fail by just _expecting_ get(vertex_index, g) to be valid.
I chose the latter decision, so the "short" versions expect the graph to have a vertex_index property associated. I will write tests and put some concept checks into the code this week or next. @Andrew Sutton: Shall I post to the list again then or contact you directly when finished with writing the tests? Matthias Walter
@Andrew Sutton: Shall I post to the list again then or contact you directly when finished with writing the tests?
I'll look over these changes this morning. If possible, I would tar or zip the submission and then send a link to the mailing list. If you don't have a convenient place to put it online, then you upload it to the Boost Vault. I'd put it the Algorithms/graph directory. After posting that, I'll review it and the documentation and then merge it into the trunk. It will probably take a couple of days once you have everything together. Andrew Sutton andrew.n.sutton@gmail.com
If possible, I would tar or zip the submission and then send a link to the mailing list. If you don't have a convenient place to put it online, then you upload it to the Boost Vault. I'd put it the Algorithms/graph directory.
After posting that, I'll review it and the documentation and then merge it into the trunk. It will probably take a couple of days once you have everything together.
I've uploaded the bipartiteness stuff onto boost vault, as you recommended: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=biparti... The documentation is in the same manner as the other algorithms, the example creates two graphs, tests them and prints the partitition (1st graph) and the odd-cycle (2nd graph), while the test code calls all implemented interfaces and verifies the certificates. The test code uses boost/test/minimal.hpp structure. Matthias Walter
On Mon, 1 Mar 2010, Matthias Walter wrote:
If possible, I would tar or zip the submission and then send a link to the mailing list. If you don't have a convenient place to put it online, then you upload it to the Boost Vault. I'd put it the Algorithms/graph directory.
After posting that, I'll review it and the documentation and then merge it into the trunk. It will probably take a couple of days once you have everything together.
I've uploaded the bipartiteness stuff onto boost vault, as you recommended:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=biparti...
The documentation is in the same manner as the other algorithms, the example creates two graphs, tests them and prints the partitition (1st graph) and the odd-cycle (2nd graph), while the test code calls all implemented interfaces and verifies the certificates. The test code uses boost/test/minimal.hpp structure.
Since I did not look over the code previously, here are my comments: libs/ is not a subdirectory of boost/ -- those are two separate top-level directories. The subdirectories under those appear to be correct (don't worry about fixing up the jamfiles). Did you want bipartite_visitor_error to inherit from std::exception? It should have methods like what() in that case as well. DFS (setting each vertex to the opposite of its parent's color) would take care of iterating through all of the source vertices for you (in the undirected case). You could get rid of internal_color_map in that case as well -- DFS would handle that internally. Would you benefit from a one-bit color map for the partition map? I know that BFS and DFS require three colors (but two-color versions could be written); do you require that in your partition map as well? In your example, are_adjacent_vertices() could just iterate over the out edges (or adjacent vertices) of u; there is also an edge() function which does what you want and is more efficient for some graphs. There are much simpler ways to create constant graphs than the one you are using; this constructor might help you: template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, edges_size_type m = 0, const GraphProperty& p = GraphProperty()) There is an example of how to use it in libs/graph/example/csr-example.cpp (for a different graph type, but the constructor is similar). You can use "using namespace boost;" in examples; it might make the code less verbose. 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. I like your code and documentation overall. -- Jeremiah Willcock
I've uploaded the bipartiteness stuff onto boost vault, as you recommended:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=biparti...
The documentation is in the same manner as the other algorithms, the example creates two graphs, tests them and prints the partitition (1st graph) and the odd-cycle (2nd graph), while the test code calls all implemented interfaces and verifies the certificates. The test code uses boost/test/minimal.hpp structure.
I haven't had a chance to look over your resubmission, but I agree with all of Jeremiah's comments. I just wanted to add some responses to your comments that you sent last week. The memory leaks were detected with valgrind on a Linux system, running against the test file that you provided (and I modified). The memory leaks are trivially solved if you can remove the dynamic allocations and use a container to control the allocations (list, stack, etc.). This also removes the need for a label allocator. With respect to list.size() issue, I there there are only a couple of places where this is still being called, and you're only looking to see if size() > 2. Why not write a function that tries to iterate 3 elements? It's still a O(1) function :) What about the name constrained_shortest_paths? Is that too general? I will try to go over the code in more detail later this week. If you want to address some of Jeremiah's comments before I look at it, let me know. Andrew Sutton andrew.n.sutton@gmail.com
I haven't had a chance to look over your resubmission, but I agree with all of Jeremiah's comments. I just wanted to add some responses to your comments that you sent last week.
Oops. Wrong response. Please disregard.
I will try to go over the code in more detail later this week. If you want to address some of Jeremiah's comments before I look at it, let me know.
This part still holds :) Andrew Sutton andrew.n.sutton@gmail.com
On 03/01/10 19:47, Jeremiah Willcock wrote:
On Mon, 1 Mar 2010, Matthias Walter wrote:
I've uploaded the bipartiteness stuff onto boost vault, as you recommended:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=biparti...
The documentation is in the same manner as the other algorithms, the example creates two graphs, tests them and prints the partitition (1st graph) and the odd-cycle (2nd graph), while the test code calls all implemented interfaces and verifies the certificates. The test code uses boost/test/minimal.hpp structure.
libs/ is not a subdirectory of boost/ -- those are two separate top-level directories. The subdirectories under those appear to be correct (don't worry about fixing up the jamfiles). Okay, will fix this issue on the next try.
Did you want bipartite_visitor_error to inherit from std::exception? It should have methods like what() in that case as well.
Is it recommended or necessary to inherit from std::exception? I will dig into the other implementations and adopt from that behavior.
DFS (setting each vertex to the opposite of its parent's color) would take care of iterating through all of the source vertices for you (in the undirected case). You could get rid of internal_color_map in that case as well -- DFS would handle that internally.
Ah, didn't recognize that DFS searches in the whole graph while BFS only in the component. Thought, they'd behave the same. Sounds like a good reason to use DFS and simplify the code this way. Thanks!
Would you benefit from a one-bit color map for the partition map? I know that BFS and DFS require three colors (but two-color versions could be written); do you require that in your partition map as well?
The partition map only uses white() and black() from color_traits, so a one-bit color map would be a nice thing to have.
In your example, are_adjacent_vertices() could just iterate over the out edges (or adjacent vertices) of u; there is also an edge() function which does what you want and is more efficient for some graphs.
There are much simpler ways to create constant graphs than the one you are using; this constructor might help you:
template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, edges_size_type m = 0, const GraphProperty& p = GraphProperty())
There is an example of how to use it in libs/graph/example/csr-example.cpp (for a different graph type, but the constructor is similar).
Okay, I will dig into your suggested improvements and see what I can do.
You can use "using namespace boost;" in examples; it might make the code less verbose.
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. Matthias Walter
On Tue, 2 Mar 2010, Matthias Walter wrote: > On 03/01/10 19:47, Jeremiah Willcock wrote: >> On Mon, 1 Mar 2010, Matthias Walter wrote: >>> I've uploaded the bipartiteness stuff onto boost vault, as you >>> recommended: >>> >>> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=bipartite.zip&directory=Algorithms/graph& >>> >>> >>> The documentation is in the same manner as the other algorithms, >>> the example creates two graphs, tests them and prints the partitition >>> (1st graph) and the odd-cycle (2nd graph), while the test code calls all >>> implemented interfaces and verifies the certificates. The test code uses >>> boost/test/minimal.hpp structure. >> >> libs/ is not a subdirectory of boost/ -- those are two separate >> top-level directories. The subdirectories under those appear to be >> correct (don't worry about fixing up the jamfiles). > Okay, will fix this issue on the next try. > >> >> Did you want bipartite_visitor_error to inherit from std::exception? >> It should have methods like what() in that case as well. > Is it recommended or necessary to inherit from std::exception? I will > dig into the other implementations and adopt from that behavior. The Boost guidelines recommend it: http://www.boost.org/community/error_handling.htmlB >> DFS (setting each vertex to the opposite of its parent's color) would >> take care of iterating through all of the source vertices for you (in >> the undirected case). You could get rid of internal_color_map in that >> case as well -- DFS would handle that internally. > Ah, didn't recognize that DFS searches in the whole graph while BFS only > in the component. Thought, they'd behave the same. Sounds like a good > reason to use DFS and simplify the code this way. Thanks! >> >> Would you benefit from a one-bit color map for the partition map? I >> know that BFS and DFS require three colors (but two-color versions >> could be written); do you require that in your partition map as well? > The partition map only uses white() and black() from color_traits, so a > one-bit color map would be a nice thing to have. OK. It should not be too hard to write. >> In your example, are_adjacent_vertices() could just iterate over the >> out edges (or adjacent vertices) of u; there is also an edge() >> function which does what you want and is more efficient for some graphs. Are you thinking of using one of these options? Actually, looking at BGL some more, there is lookup_edge (in boost/graph/lookup_edge.hpp) that is a wrapper that uses edge() when possible and an out edge scan otherwise. That will work on more graph types. >> There are much simpler ways to create constant graphs than the one you >> are using; this constructor might help you: >> >> template <class EdgeIterator> >> adjacency_list(EdgeIterator first, EdgeIterator last, >> vertices_size_type n, >> edges_size_type m = 0, >> const GraphProperty& p = GraphProperty()) >> >> There is an example of how to use it in >> libs/graph/example/csr-example.cpp (for a different graph type, but >> the constructor is similar). > Okay, I will dig into your suggested improvements and see what I can do. >> >> You can use "using namespace boost;" in examples; it might make the >> code less verbose. >> >> 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. -- Jeremiah Willcock
Did you want bipartite_visitor_error to inherit from std::exception? It should have methods like what() in that case as well. Is it recommended or necessary to inherit from std::exception? I will dig into the other implementations and adopt from that behavior.
The Boost guidelines recommend it: http://www.boost.org/community/error_handling.htmlB
Fixed
DFS (setting each vertex to the opposite of its parent's color) would take care of iterating through all of the source vertices for you (in the undirected case). You could get rid of internal_color_map in that case as well -- DFS would handle that internally. Ah, didn't recognize that DFS searches in the whole graph while BFS only in the component. Thought, they'd behave the same. Sounds like a good reason to use DFS and simplify the code this way. Thanks!
Would you benefit from a one-bit color map for the partition map? I know that BFS and DFS require three colors (but two-color versions could be written); do you require that in your partition map as well? The partition map only uses white() and black() from color_traits, so a one-bit color map would be a nice thing to have.
OK. It should not be too hard to write.
The implementation now uses DFS instead of BFS, has no internal color map anymore and no loop for iterating through the graph's components. Furthermore it uses the one-bit-colormap if none is given.
Are you thinking of using one of these options? Actually, looking at BGL some more, there is lookup_edge (in boost/graph/lookup_edge.hpp) that is a wrapper that uses edge() when possible and an out edge scan otherwise. That will work on more graph types.
Switched the test-code to lookup_edge. The example code also contained the certificate-verifying functions, but never used them. I just forgot to remove them.
There are much simpler ways to create constant graphs than the one you are using;
Fixed to a really small version.
You can use "using namespace boost;" in examples; it might make the code less verbose.
Done :-)
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. Here's the link again: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=biparti... Thanks for the nice hints and actually for reviewing, too! Matthias Walter
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
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&
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
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
On Thu, 4 Mar 2010, Matthias Walter wrote:
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?
I mean that your visitor takes another arbitrary visitor as a template parameter, stores it, and then invokes its methods after you run your hooks. Basically, it's a generalization of what you do now with predecessor recorders but working with any visitor.
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.
OK. I thought you were pulling from the end of the path closest to where the coloring failure occured, not the other end. Now I understand why you need to do it. -- Jeremiah Willcock
On 03/04/10 23:40, Jeremiah Willcock wrote:
On Thu, 4 Mar 2010, Matthias Walter wrote:
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?
I mean that your visitor takes another arbitrary visitor as a template parameter, stores it, and then invokes its methods after you run your hooks. Basically, it's a generalization of what you do now with predecessor recorders but working with any visitor. I experimented with some solutions and don't really like the hook-calling by hand. As you seem to like something really generic, I finally decided to go with the VisitorEventList, i.e. I split the functionality into bipartition_colorize, bipartiton_check and property_put functors which are then thrown together in the DFS call.
The latter might be worth including into visitors.hpp, I think: It takes a property map plus a value of it and just sets the value when called. I use this to initialize the start vertex to be white, but it doesn't require the property map to be a color map and can work on vertices and edges and thus all possible visitors. But this is up to you to move it to visitors.hpp if you like it. I updated the archive at Boost Vault. best regards Matthias Walter
On Fri, 5 Mar 2010, Matthias Walter wrote:
On 03/04/10 23:40, Jeremiah Willcock wrote:
On Thu, 4 Mar 2010, Matthias Walter wrote:
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?
I mean that your visitor takes another arbitrary visitor as a template parameter, stores it, and then invokes its methods after you run your hooks. Basically, it's a generalization of what you do now with predecessor recorders but working with any visitor.
I experimented with some solutions and don't really like the hook-calling by hand. As you seem to like something really generic, I finally decided to go with the VisitorEventList, i.e. I split the functionality into bipartition_colorize, bipartiton_check and property_put functors which are then thrown together in the DFS call.
The latter might be worth including into visitors.hpp, I think: It takes a property map plus a value of it and just sets the value when called. I use this to initialize the start vertex to be white, but it doesn't require the property map to be a color map and can work on vertices and edges and thus all possible visitors. But this is up to you to move it to visitors.hpp if you like it.
I put it in visitors.hpp and added documentation in libs/graph/doc/property_put.html; please see what you think of it. -- Jeremiah Willcock
I experimented with some solutions and don't really like the hook-calling by hand. As you seem to like something really generic, I finally decided to go with the VisitorEventList, i.e. I split the functionality into bipartition_colorize, bipartiton_check and property_put functors which are then thrown together in the DFS call.
The latter might be worth including into visitors.hpp, I think: It takes a property map plus a value of it and just sets the value when called. I use this to initialize the start vertex to be white, but it doesn't require the property map to be a color map and can work on vertices and edges and thus all possible visitors. But this is up to you to move it to visitors.hpp if you like it.
I put it in visitors.hpp and added documentation in libs/graph/doc/property_put.html; please see what you think of it.
Looks good! Modified the version on Boost Vault to use it from there. Matthias Walter
On Sat, 6 Mar 2010, Matthias Walter wrote:
I experimented with some solutions and don't really like the hook-calling by hand. As you seem to like something really generic, I finally decided to go with the VisitorEventList, i.e. I split the functionality into bipartition_colorize, bipartiton_check and property_put functors which are then thrown together in the DFS call.
The latter might be worth including into visitors.hpp, I think: It takes a property map plus a value of it and just sets the value when called. I use this to initialize the start vertex to be white, but it doesn't require the property map to be a color map and can work on vertices and edges and thus all possible visitors. But this is up to you to move it to visitors.hpp if you like it.
I put it in visitors.hpp and added documentation in libs/graph/doc/property_put.html; please see what you think of it.
Looks good! Modified the version on Boost Vault to use it from there.
OK. I'm looking at the mismatch version of common ancestor removal and it's starting to look overly complicated. I think it would be better if you put back the first version (that does iterated pop_back()s); maybe change it so it keeps two iterators that walk backwards and then you do a single erase() to the end of each container (or only copy up to each iterator). Here is the sort of thing I'm thinking of (not tested): template <typename SeqA, typename SeqB> void remove_common_suffix(SeqA& a, SeqB& b) { if (a.empty() || b.empty()) return; typename SeqA::iterator ai = a.end(); typename SeqB::iterator bi = b.end(); while (true) { // Invariant: a.end() - ai == b.end() - bi --ai; --bi; if (*ai != *bi) {++ai; ++bi; break;} if (ai == a.begin()) break; // a is a suffix of or equal to b if (bi == b.begin()) break; // b is a suffix of a } // Possible cases when we get here: // a == b: ai == a.begin() && bi == b.begin() // a is a suffix of b: ai == a.begin() && bi == b.end() - a.size() // b is a suffix of a: ai == a.end() - b.size() && bi == b.begin() // Otherwise: ai and bi point to the first element of the common // suffix a.erase(ai, a.end()); b.erase(bi, b.end()); } -- Jeremiah Willcock
Would you benefit from a one-bit color map for the partition map? I know that BFS and DFS require three colors (but two-color versions could be written); do you require that in your partition map as well? The partition map only uses white() and black() from color_traits, so a one-bit color map would be a nice thing to have.
I went ahead and added a one-bit color map; it is in boost/graph/one_bit_color_map.hpp in the trunk. -- Jeremiah Willcock
participants (4)
-
Andrew Sutton -
Jeremiah Willcock -
John Bytheway -
Matthias Walter