Subject: Re: [boost] [BGL] StoerâWagner min-cut algorithm
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-08-13 12:43:45
>> 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.
Your version of `read_dimacs.hpp` compiles and succeeds with my tests.
>> 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
>> 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.
Specifically do you not like the `keys` member?
> - 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)?
It's correct. The loop on line 76 runs until the priority queue is
empty. Each iteration causes one value (vertex_descriptor) to be
removed from the priority queue and once a vertex_descriptor is no
longer in the queue, then the algorithm does not need to update its
key. Because the loop on line 84 is iterating over all out-edges, some
target vertices may have already been removed. So, I check.
> - What property map is the default priority queue built from? Â I don't see
> Â that in the code.
In the patch for `named_function_params.hpp` that I submitted in a
message from July 8th
(http://lists.boost.org/Archives/boost/2010/07/168703.php), I adapted
your technique for `map_maker` to create `priority_queue_maker`. After
applying the patch, lines 574 and 575 use `map_maker` to create a
"keys" map and "index in heap" map, respectively.
> - Have you tried using a custom priority queue in
> Â the test case? Â I'm not sure it will work properly.
`test_prgen_20_70_2` uses a custom d-ary heap.
> - 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.
Indeed. I will switch to using that.
> - 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?
That's an excellent idea. If I maintained a map from vertex
descriptors to lists of descriptors of vertices that were assigned to
the vertex, then I would be able to decrease the number of iterations
of not only the loop on line 82, but the loop on line 66 as well.
Would it be alright if I used a `std::map<vertex_descriptor,
std::vector<vertex_descriptor> >` internally or does something like
that need to be another parameter? I am thinking that some users might
want more control over temporary variables that utilize the heap.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk