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-08-12 12:55:41

> 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 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`.