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-18 18:36:46

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

A quick update: I made the changes, but the performance improvement
was slight (around 1 percent). I have identified, however, that the
`BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph)` loop is even
worse when it comes to iterating through the entire map;  toward the
latter part of the computation, this loop iterates over more and more
of the input graph's edges until the loop covers close to 100% of the
edges.

I used that loop because with it, it is possible to run the algorithm
without modifying or copying the input graph. I am now thinking that I
really want to copy the input graph and make changes to the copy. So,
I will be adding a "destructive" version of the `stoer_wagner_min_cut`
function that will be used on copies. Users could also use the
destructive version on a graph that they do not care about.