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-08-12 13:50:14

On Thu, 12 Aug 2010, Daniel Trebbien wrote:

>> I'll change the shell script to output PNG files, though, and re-run it (or you can).
>
> You might want to keep the GIFs. If I recall correctly, the GIF images
> were smaller files. Plus, none of the HTML files would need to be
> modified.
>
>> BTW, I added a read_dimacs_min_cut() function to read_dimacs.hpp; see if that works for your test cases. Â I haven't tested it, but it should use the same code as read_dimacs_max_flow() but with the source and sink features turned off (and so removing the "n" line requirements).
>>
>> I've been kind of busy recently, so I'll look through your files in more detail soon. Â You might want to update your test code and upload a new version, though, to use the new reading function.
>
> The changes to `read_dimacs.hpp` basically worked. I just needed to
> modify it so that the parsing would not fail at the 'p' line because
> the problem type is "cut" rather than "max". Attached is a patch for
> these changes.

I believe I fixed that, but using a different approach; please check.

> I have uploaded a new version, 0.5.4, to the Vault:
> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stoer_wagner_min_cut-0.5.4.zip&directory=Algorithms/graph&
>
> Changes include:
> 1. Switched to using `boost::read_dimacs_min_cut` instead of `parse_noigen`.
>
> 2. Removed `parse_noigen.hpp`
>
> 3. Added comments to the example program.
>
> 4. Created a new graphic of the min-cut in the example program.
> Appropriately modified `make_min_cut_images.bat` and
> `make_min_cut_images.sh`.

Here are my comments:

- I still don't like the KeyedUpdatablePriorityQueue concept in there, and
   would prefer if you used whichever map directly.

- Is the code on line 87 (only update the key if the entry is already in
   the queue) right, or should it be to always update (based on a default
   of 0 or whatever)?

- What property map is the default priority queue built from?  I don't see
   that in the code.

- Have you tried using a custom priority queue in
   the test case?  I'm not sure it will work properly.

- Your test case does not need to define its own constant property map;
   boost::constant_property_map (from
   <boost/graph/property_maps/constant_property_map.hpp>) should work
   instead.

- Should line 82 be iterating through the entire graph, or would it be
   faster if all vertices with a given assignment are kept in a data
   structure for faster access?

-- Jeremiah Willcock