Re: [boost] [BGL] Testing a graph for bipartiteness

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