status of fibonnaci_heap and mutable_queue
Does anyone know the satus of these pending libraries? I'm in need of a mutable priority queue. TIA Fernando Cacciola
On Apr 6, 2006, at 8:46 PM, Fernando Cacciola wrote:
Does anyone know the satus of these pending libraries?
They've been pending for a long time and may remain pending forever.
I'm in need of a mutable priority queue.
If it fits what you need, there is the relaxed_heap data structure. However, it has a rather minimal interface that's meant for the graph library. Doug
Douglas Gregor wrote:
On Apr 6, 2006, at 8:46 PM, Fernando Cacciola wrote:
I'm in need of a mutable priority queue.
If it fits what you need, there is the relaxed_heap data structure. However, it has a rather minimal interface that's meant for the graph library.
All I need is a priority queue with an update() operation (which of course can potentially replace the top element), so yes, if I understood the interface correctly, this is exactly what I need!! It's also under pending, but I guess this one is actually used in the BGL so is trustworthy, right? BTW: a related question that it think you can answer: This DS needs an index map from the IndexedType to an integral index in the range [0,n]. But my algorithm will run over non-indexed types which might not even be stored in a radom access container. 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? TIA Fernando Caccio.a
On Apr 6, 2006, at 5:10 PM, Fernando Cacciola wrote:
All I need is a priority queue with an update() operation (which of course can potentially replace the top element), so yes, if I understood the interface correctly, this is exactly what I need!!
It's also under pending, but I guess this one is actually used in the BGL so is trustworthy, right?
We'd done a lot of validation of shortest paths algorithms using the relaxed heap as the priority queue, so it should be trustworthy.
BTW: a related question that it think you can answer:
This DS needs an index map from the IndexedType to an integral index in the range [0,n].
But my algorithm will run over non-indexed types which might not even be stored in a radom access container.
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. Doug
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
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
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
Douglas Gregor <doug.gregor@gmail.com> writes:
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.
Hmm, did you see: http://lists.boost.org/Archives/boost/2002/01/23970.php and the foregoing thread? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Apr 12, 2006, at 5:10 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes:
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.
Hmm, did you see: http://lists.boost.org/Archives/boost/2002/01/23970.php and the foregoing thread?
I've read it now. So I'll be more careful with the complexity measures: With a relaxed heap it's O(|V| lg |V| + |E|) With a binary heap it's O((|V| + |E|) lg |V|) If you insert instead of updating, that, lg |V| becomes a lg |E|. The relaxed heap is admittedly complicated. We have some performance test's we've run, and it's a toss-up. On some graphs, the binary heap does slightly better; on others, the relaxed heap does slightly better. Doug
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost
Douglas Gregor <doug.gregor@gmail.com> writes:
On Apr 12, 2006, at 5:10 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes:
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.
Hmm, did you see: http://lists.boost.org/Archives/boost/2002/01/23970.php and the foregoing thread?
I've read it now. So I'll be more careful with the complexity measures:
With a relaxed heap it's O(|V| lg |V| + |E|) With a binary heap it's O((|V| + |E|) lg |V|)
If you insert instead of updating, that, lg |V| becomes a lg |E|.
The relaxed heap is admittedly complicated.
More importantly to me, it makes usage requirements much more complicated in some cases.
We have some performance test's we've run, and it's a toss-up. On some graphs, the binary heap does slightly better; on others, the relaxed heap does slightly better.
Well, that's great to know. So, I'll ask my original question again: given that it's a toss-up, and it is often inconvenient for users, does it make sense to require a relaxed heap? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Apr 13, 2006, at 12:16 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes: So, I'll ask my original question again: given that it's a toss-up, and it is often inconvenient for users, does it make sense to require a relaxed heap?
Well, the relaxed heap is completely internal to Dijkstra's algorithm. If it were a parameter, the constraint would be for an "Updateable Buffer", e.g., a Buffer (as with BFS) that also has the update() operation. The update() operation is really simple for a binary heap, and important to get the best complexity for Dijkstra algorithm, so we can't remove that requirement. Should we use the relaxed heap at all? I'm not sure. I need to check what's happening on really big graphs to see if the relaxed heap starts to shine there. I was only working with graphs up to about 1M vertices previously. Doug
Doug Gregor <dgregor@cs.indiana.edu> writes:
On Apr 13, 2006, at 12:16 PM, David Abrahams wrote:
Douglas Gregor <doug.gregor@gmail.com> writes: So, I'll ask my original question again: given that it's a toss-up, and it is often inconvenient for users, does it make sense to require a relaxed heap?
Well, the relaxed heap is completely internal to Dijkstra's algorithm. If it were a parameter, the constraint would be for an "Updateable Buffer", e.g., a Buffer (as with BFS) that also has the update() operation.
Okay, I'm obviously misremembering what happened, but IIRC I ended up using my own hand-rolled Dijkstra in libs/python/src/object/inheritance.cpp because the BGL's was imposing several incovenient requirements on me, like tri-state coloring and an update operation for the relaxed heap.
The update() operation is really simple for a binary heap, and important to get the best complexity for Dijkstra algorithm, so we can't remove that requirement.
Doesn't whether it's best depend on the relationship between V and E? -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (4)
-
David Abrahams -
Doug Gregor -
Douglas Gregor -
Fernando Cacciola