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