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-09-11 19:53:33

> A quick update: I made the changes, but the performance improvement
> was slight (around 1 percent). I have identified, however, that the
> `BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph)` loop is even
> worse when it comes to iterating through the entire map; Â toward the
> latter part of the computation, this loop iterates over more and more
> of the input graph's edges until the loop covers close to 100% of the
> edges.
>
> I used that loop because with it, it is possible to run the algorithm
> without modifying or copying the input graph. I am now thinking that I
> really want to copy the input graph and make changes to the copy. So,
> I will be adding a "destructive" version of the `stoer_wagner_min_cut`
> function that will be used on copies. Users could also use the
> destructive version on a graph that they do not care about.

Version 0.5.5 has been uploaded to the Vault:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stoer_wagner_min_cut-0.5.5.zip&directory=Algorithms/graph&

The only substantive difference in this version is that it includes
the code to build up a set of "assigned vertices", leading to the
slight performance improvement that I was talking about on August 18.
As far as producing a "destructive version", I tried out two variants.
One utilized `clear_vertex` and the other utilized a different method
of removing edges that needed to be removed as the algorithm
encountered them. Interestingly, a benchmark program that I have been
using takes 11 times longer to run when `clear_vertex` is used, and I
don't know how much longer on the other version because I Ctrl+C it
each time. These were unexpected results, but I guess that iterating
through more and more of the edges as the computation progresses is a
lot more efficient than removing edges from the input graph.

Anyway, I believe that this new version has addressed all feedback
that I have received so far.