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

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.