Boost logo

Boost :

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-03-02 08:39:02

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at