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
>> 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:
> 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
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/graph/property_maps/constant_property_map.hpp>) should work
- 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk