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