Douglas Gregor wrote:
On Apr 11, 2006, at 3:18 AM, David Abrahams wrote:
Doug Gregor <dgregor@cs.indiana.edu> writes:
If I understand the propery maps library correctly, I'll need to create a map, or hash_map, associating each and every possible value with an int, and wrap that into an associative_property_map<> to input into the relaxed_heap DS. Is that right?
That sounds right.
OK.
I don't have the context for this discussion (I'm on a plane right now and can't see back in time), but I'm going to hazard a wild guess that the need to index the nodes is due to the need for a priority queue with an update() operation, and that is due to the fact that what you're doing is based on dijkstra_shortest_paths.
Well, I don't know about Doug, but FWIW I need the update() for something else: I'm implementing the Lindstrom-Turk triangulated surface mesh simplification algorithm. This algorithm keeps the edges of the triangulation in a PQ based on some "collapsing cost" per edge, then it removes the edges as they are poped from the PQ. However, after each edge has been removed from the surface, the cost of the neighboring edges must be updated. Of course this can done using set<> but IIUC the relaxed_heap is much more efficient. Specially since I put in the heap not the edges themselves but explicitely indexed wrappers mapped from the actual edges via a hash map. This way, each edge "actual" update is roughly O(1): get the wrapper from the edge via the hash_map (O(1)) and update the PQ (O(1) from Doug's report) [plues the wrapper is needed anyway to keep other per-edge data used by the agorithm]. Best Fernando Cacciola