Subject: Re: [boost] [BGL] StoerâWagner min-cut algorithm
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-08-13 14:51:54
On Fri, 13 Aug 2010, Daniel Trebbien wrote:
>>> 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.
Do you have a property map for what is in the queue? Some kind of color
map? I think it might be better if there was one; that might simplify the
algorithm and allow a wider range of heaps to be used.
>> - 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.
I'm not seeing quickly what property map the actual priorities come from.
Is it the distance map, like it seems from the documentation? I think
that should be passed explicitly into the stoer_wagner_phase() function.
Is there ever a case where the priority queue won't be some kind of
indirect priority queue on the distance map?
>> - 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.
OK -- I didn't see that.
>> - 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
> 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.
I think you can use an iterator_property_map or shared_array_property_map
for this rather than an std::map. I don't think it needs to be
customizable but you can if you want (you might need a new key in
named_function_params.hpp for that). Just be careful that the complexity
of maintaining the map doesn't cancel out the benefit of not iterating
over as many edges.
-- Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk