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-15 22:05:50

>> Specifically do you not like the `keys` member?
>
> Yes.

I don't think that I ever explained my reasoning behind it, but
essentially the idea is to reduce the amount of data that the user
would have to pass to the function while ensuring that they passed in
the correct map. The d-ary heap, or any priority queue, would need
access to the map which I call the "keys" map (in the `d_ary_heap.hpp`
source it is called the "distances" map). If the priority queue did
not have a member to furnish this property map, then in addition to
receiving the priority queue to use, the function would need to
receive the property map. This means that the user would not only have
to pass the priority queue object but the corresponding property map
as well.

Having to pass in the property map might lead to mistakes, such as
accidentally passing in the wrong property map. Also, I think that it
would be more convenient for the user if they do not have to retype
the name of the property map or even keep a copy in a local variable
to be passed to the function later.

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

I am not sure that a property map for what is in the queue would be
helpful. At the start and end of each call to `stoer_wagner_phase`,
the queue must be empty.

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

By default, the priorities are stored in the vertex distances map
because I was following the model of `dijkstra_shortest_paths`.
`dijkstra_shortest_paths` uses the vertex distances map by default to
store "distances", which are temporary values.

One of the first operations of `stoer_wagner_phase` is to set these
"distances" to 0, so it does not matter what the value of "distance"
is for each vertex at the start of `stoer_wagner_phase`. The
"distance" values are temporary data only.

> Is there
> ever a case where the priority queue won't be some kind of indirect priority
> queue on the distance map?

Yes, if a custom priority queue does not use the vertex distances map
for the "keys"/priorities map. For example, the `test_prgen_20_70_2`
test, which passes in a custom d-ary heap object, uses a shared array
property map to store the priorities/"distances".

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

Looking at these property map classes again, I do not see a way to
iterate over the entries in the property map. For each vertex that is
not assigned to another vertex, I would need to know the list of
vertices that are assigned to it.

For now I think that I will just use a `std::map<vertex_descriptor,
std::vector<vertex_descriptor> >` to see if it improves the speed of
the algorithm on a large test instance that I generated.