Boost logo

Boost :

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-23 10:55:12


On Wed, 23 Jun 2010, Daniel Trebbien wrote:

> Hi Jeremiah,
>
> Thank you for your feedback. This gives me a lot to work on, which I
> will be implementing soon.
>
> I have addressed some of your points below.
>
>
> On 2010-06-23, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
>> I skimmed through your code, and saw couple of little things to change:
>>
>> - Boost code doesn't use tabs
>> (<URL:http://www.boost.org/community/policy.html#tabs>)
>>
>> - I don't think you need to use BOOST_DEDUCED_TYPENAME; I just use
>> "typename" myself and haven't had any problems. I think it might be a
>> workaround for compilers that are not used anymore.
>>
>> - Your header guard should start with BOOST_GRAPH_ to avoid conflicts with
>> other header files.
>>
>> - You can replace "c.size() > 0" by "!c.empty()"; this is likely to be
>> faster for many containers.
>>
>> - Your non-detail code should be in the "boost" namespace.
>>
>> - From a superficial look, it seems like maxAdjSearchList might be
>> implementable as a heap (or some other priority queue) rather than as a
>> multiset. Am I mistaken on that?
>
> You are correct that I should use a maximum priority queue. The
> algorithm is best implemented with a Fibonacci heap, but I couldn't
> get the C++ implementation that appeared in Dr. Dobb's Journal to
> work. Granted, this was early on and the segmentation fault that I was
> getting could have been caused by my own code.
>
> I also looked at `std::priority_queue`, but it does not implement `increasekey`.
>
> For this algorithm, I need to associate each vertex with a value w(A),
> which is the sum of weights of edges containing the vertex and a point
> in a set A of vertices. Each iteration until the priority queue is
> empty, I need to select and remove the vertex u with the greatest w(A)
> to be added to A, thus requiring an update (increasekey) of the w(A)
> values of vertices v in the priority queue such that {u, v} is in E,
> the set of edges.
>
> How do other BGL algorithms implement priority queues having the
> `increasekey` operation?

We have several heap implementations in BGL that support the increasekey
operation. The one you may want to use is the d-ary heap
(<boost/graph/detail/d_ary_heap.hpp>) since it seems to be the fastest in
practice (although not in theoretical complexity); there are comments in
that file on how to use it. Look at
<boost/graph/dijkstra_shortest_paths.hpp> for example uses of several of
the heaps. Note that the d-ary heap includes an indirect comparison
(comparing values from a weight or distance map) natively, while some of
the other heaps need the indirect_cmp function object (from
<boost/pending/indirect_cmp.hpp>) to implement that. Dijkstra's algorithm
uses all of the things I mentioned so you can look there to see sample
code.

>> - Operations on graphs and property maps (but not on tuples) need to use
>> unqualified names (such as "get" and "target") in order for ADL to work on
>> user-defined graph types that are not in the boost namespace. Calls to
>> "tie", however, must be qualified (I had to fix many of those yesterday
>> because unqualified calls to tie break C++0x compilers).
>
> I am not sure what you mean by "need to use unqualified names". Do you
> mean without the `boost::` namespace qualification?

Yes.

> Also, I do not understand what "calls to 'tie' ... must be qualified" means.

Those must have a namespace qualification.

>> - Is there a reason that you do not handle parallel edges? Is it just a
>> simplification in the code?
>>
>> - It looks like the code handling sOutEdges and tOutEdges is unnecessarily
>> complicated. Are you just intersecting the two lists of out edges? If
>> so, you can use lookup_edge (from <boost/graph/lookup_edge.hpp>) to allow
>> edge lookups in constant time for adjacency matrices (however, unlike the
>> map-based implementation, lookup_edge takes linear time when it must
>> actually do a search).
>>
>> - You may want to use the macros in <boost/graph/iteration_macros.hpp> to
>> simplify your code. Those macros replace explicit declarations of
>> iterators and tie operations when you are doing a simple iteration through
>> vertices, out edges, etc. If you use them, please include
>> <boost/graph/iteration_macros_undef.hpp> at the end of your file.
>>
>> - Property maps are passed by copy; they are intended to be lightweight
>> and using copies allows temporary property maps to be passed in.
>>
>> - Are users always going to pass in all of the parameters you have in your
>> algorithm? If not, overloads or named parameters may be worthwhile to
>> add.
>
> Named parameters would be good. What Boost libraries can I use for
> named parameters?

Although we have wanted to move to Boost.Parameter for a while, BGL
currently uses its own named parameter mechanism. I don't know if it is
documented anywhere; your best hope would probably be to look through
another algorithm in BGL that uses named parameters and see what the calls
look like. Some of the handling of property maps is complicated, though,
so you may want to wait on adding named parameters until the rest of the
algorithm is finished and ready to submit.

-- Jeremiah Willcock


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk