Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

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