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.
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.
The mapping from values to integers is needed so that the relaxed heap can associate extra data with each value.
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.
Back when you had that argument with Jeremy, the BGL implementation of Dijkstra's algorithm was using a binary heap, which has O(lg n) for both update and delete. I've since replaced the binary heap with the relaxed heap, which provides O(1) update but O(lg n) delete.
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.
This would change the complexity of Dijkstra's algorithm from O(|V| lg |V|) to O(|V| lg |E|), where |V| is the number of vertices in the graph and |E| is the number of edges in the graph. Doug