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

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-03-02 08:06:31

> 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.
>>
>
>
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_at_[hidden]