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