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.