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