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.
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. A couple years ago Jeremy and I had an argument because I couldn't understand the need for this update operation (and its concommitant inconveniences), whereas Jeremy, apparently, had never seen a Dijkstra that didn't use it. While I understand (or at least I eventually understood at the time) how the update could save some computation, not doing the update doesn't change the big-O performance of the algorithm. So I'm wondering if the library shouldn't have a version of dijkstra that doesn't use the update... or, maybe better yet, if update were a free function, maybe the library could provide a default one that does nothing. -- Dave Abrahams Boost Consulting www.boost-consulting.com