Boost logo

Boost :

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
>> `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
>> ``.
> 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
(, 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, gregod at, cpdaniel at, john at