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

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-06-23 10:20:07

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?

>
> - 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?

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

>
> - 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?

>
> - As you stated, your code needs a license banner.
>
> - You will eventually need a documentation file, preferably in HTML that
> is styled like the existing BGL documentation.
>
> - I think you can just attach the header file to your emails, since the
> test code is in a separate email anyway.  Also, it would make my life
> easier if you wrote your code/tests as if your header was in boost/graph/,
> since that is where it will end up eventually.  If you do that, I will
> test it in place there as well.
>
> -- Jeremiah Willcock

Daniel