Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

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.

OK.

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

Yes.

>> - 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
>>  instead.
>
> Indeed. I will switch to using that.

OK.

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