On Mon, Sep 3, 2012 at 1:55 PM, Jeremiah Willcock wrote:

On Mon, 3 Sep 2012, David Doria wrote:

...

I am using a d_ary_heap_indirect as a priority queue using a property map to store the priorities. However, I when I change the values in the priority property map and push vertices that are already in the queue into the queue again, it results in kind of an invalid state where the vertex appears in the queue twice at different positions.

If you want to update priorities, change the priority map then call "update" on the d_ary_heap_indirect.

...

Is there a way to replace a vertex in the queue when it is pushed instead of adding a second one? (like an std::set instead of the current behavior which is like std::multiset)?

You pass in an IndexInHeapMap -- you should be able to check that to determine whether to call "push" or "update". You can also look into the kind of logic that is in dijkstra_shortest_paths_no_color_map for whether to do insertions or updates in that context.

-- Jeremiah Willcock

Hi Jeremiah, I found a push_or_update(vertex) function of d_ary_heap_indirect that I thought would do the trick (it looks like it does the determining of whether to call push or update for us). Unfortunately, it does not behave as I would expect (it results in 7 items in the queue, not all of which are sorted). Neither does the update(vertex) function (there are only 4 items in the queue, but it is not sorted), and there does not appear to be a simply update() function like you recommended. I've detailed the outputs with each of these functions here: http://stackoverflow.com/questions/12251655/updating-priorities-in-a-boostd-... I would really appreciate it if you could help clarify these things! As usual, I'll submit a demo once we figure out how to use this, so future users don't have the same problem. Thanks, David

One thing in there that might be an issue is that you change the priorities of multiple vertices without running update() on the queue for each one separately. That may not work because the heap might get too far from satisfying the correct invariants.

I see what you're saying. Unfortunately that doesn't seem to do it either. In this demo: http://ideone.com/gfEMp I update(vertex) the queue after each priority is changed, but the output results in an unsorted (though correctly length 4) queue: There are 0 items in the queue. New priority for 0, 0 784 New priority for 1, 0 676 New priority for 0, 1 350 New priority for 1, 1 8 There are 4 items in the queue. The priority queue is: vertex: 0 0 priority: 784 vertex: 1 0 priority: 676 vertex: 0 1 priority: 350 vertex: 1 1 priority: 8 New priority for 0, 0 231 New priority for 1, 0 547 New priority for 0, 1 653 New priority for 1, 1 314 There are 4 items in the queue. The priority queue is: vertex: 0 0 priority: 231 vertex: 0 1 priority: 653 vertex: 1 0 priority: 547 vertex: 1 1 priority: 314

If that isn't the issue, could you please post or send me the exact, raw contents of the heap data (the internal vector) and the related property maps (IndexInHeap, priorities) before and after push_or_update operations that don't work correctly? The push_or_update function should do exactly what you are looking for, and so I'm surprised it isn't working correctly. Does the test at libs/graph/test/dijkstra_no_color_map_compare.cpp pass for you?

The test appears to pass (or at least the output is as follows): ------ Running dijkstra shortest paths test with 10 vertices and 500 edges **** no errors detected ------ I tried to output the index_in_heap, but it seems to be garbage (I just used get(index_in_heap, u)?): http://ideone.com/uj2lM produces: vertex: 1 1 priority: 234 indexInHeap: 4294967295 vertex: 0 1 priority: 828 indexInHeap: 0 vertex: 0 0 priority: 260 indexInHeap: 0 vertex: 1 0 priority: 46 indexInHeap: 0 The container/vector you mentioned seems to be private - how would I output its contents? Can you reproduce the unsorted result using the demo code? Thanks for your help, David

On Wed, 5 Sep 2012, David Doria wrote:

I think there is something going wrong with the index_in_heap map. I added:

std::cout << "Index added: " << get(index_in_heap, v) << std::endl;

after this line:

put(index_in_heap, v, index);

in d_ary_heap_indirect::push(Value).

I also added

std::cout << "Index added caller: " << get(index_in_heap, v) << std::endl;

after the first round of adding values to the queue (after this line: mutableQueue.push(*vertexIterator);

The output is:

Original priority for 0, 0 641 Index added: 0 Index added caller: 0 Original priority for 1, 0 40 Index added: 1 Index added caller: 1 Original priority for 0, 1 400 Index added: 2 Index added caller: 2 Original priority for 1, 1 664 Index added: 3 Index added caller: 0

I don't understand why this last index is 3 inside the push() function, but 0 when I query it from the caller?

When I look at the same things inside the update() function, the index_in_heap just seems to return garbage. That is, I look at the value of size_type index = get(index_in_heap, v); in update(), and when it is called with vertex (0,0), the value of 'index' is 4294967295 (when I would expect it to be in the range [0,3]).

I looked over and tried your code; there are two issues that I see: 1. The index_in_heap_map is initialized to 0, rather than (size_t)(-1) (the 4294967295 you are seeing after vertices are popped). It looks like that isn't a problem when an unconditional push is used to add to the queue, but push_or_update does check whether the element is already in the queue. 2. It looks like copying d_ary_heap_indirect objects doesn't work correctly (it should probably be a shallow copy, while here it is trying to do a mix of both). Thus, your output routine is removing elements from a copy of the heap data (since the heap structure itself is deep-copied) while marking them "not present" in the original index_in_heap_map (since that is shallow-copied). I'll just make it noncopyable for now, and it will likely stay that way unless someone has a compelling need for something else. -- Jeremiah Willcock

On Wed, 5 Sep 2012, David Doria wrote:

...

I looked over and tried your code; there are two issues that I see:

1. The index_in_heap_map is initialized to 0, rather than (size_t)(-1) (the 4294967295 you are seeing after vertices are popped). It looks like that isn't a problem when an unconditional push is used to add to the queue, but push_or_update does check whether the element is already in the queue.

Where do you see this being initialized to zero? (i.e. where should I changed it to be initialized to -1?). I thought that this map was being set explicitly in the push() function anyway (so why does the initialization matter)?

std::vector elements are normally initialized to zero when they are created. push() does ignore the values; push_or_update() needs them to be correct.

...

2. It looks like copying d_ary_heap_indirect objects doesn't work correctly (it should probably be a shallow copy, while here it is trying to do a mix of both). Thus, your output routine is removing elements from a copy of the heap data (since the heap structure itself is deep-copied) while marking them "not present" in the original index_in_heap_map (since that is shallow-copied). I'll just make it noncopyable for now, and it will likely stay that way unless someone has a compelling need for something else.

Ah, I see that now. How else would I inspect the current ordering? I guess just pop them all off into another container and then push them all back in?

I'm not sure -- for debugging, you can just print the raw data (or use index_in_heap_map to determine which vertices are in the heap, assuming that is initialized to -1). -- Jeremiah Willcock

On Wed, 5 Sep 2012, David Doria wrote:

...

std::vector elements are normally initialized to zero when they are created. push() does ignore the values; push_or_update() needs them to be correct.

But I am calling push() on every vertex first, right (so the automatic initialization shouldn't ever be seen by the update() )? And you are saying the queue expects them to be initialized to (size_t)(-1)? I tried initializing it explicitly:

Initialization is required only if you use push_or_update(), not push().

http://ideone.com/OgWF6

but the output is still really wacky:

There are 0 items in the queue. Original priority for 0, 0 744 Index added: 0 Index added caller: 0 Original priority for 1, 0 562 Index added: 1 Index added caller: 1 Original priority for 0, 1 824 Index added: 2 Index added caller: 0 (THIS 0 SEEMS WRONG) Original priority for 1, 1 156 Index added: 3 Index added caller: 3 There are 4 items in the queue. New priority for 0, 0 890 New priority for 1, 0 851 New priority for 0, 1 55 New priority for 1, 1 284 There are 4 items in the queue. vertex: 0 0 priority: 890 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 1 0 priority: 851 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 1 1 priority: 284 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 0 1 priority: 55 indexInHeap: 0 (THIS 0 SEEMS WRONG)

Elements being removed from the heap always have index 0 (see the definition of top() in d_ary_heap_indirect). Remember that elements are moved around in the heap as insertions and deletions occur to maintain the heap invariants. If you dump the raw index_in_heap_map data at any single point during program execution (without mutating the heap in the middle of printing), you should get consistent values.

Sorry to be a pain, but I've stepped though all of this and can't figure out why the index_in_heap map isn't returning the same values inside and outside the loop, and zero for every vertex at the end of the program?

That's a side effect of elements moving around within the heap. -- Jeremiah Willcock

On 05/09/2012 16:14, David Doria wrote:

but the output is still really wacky

I am not sure, but it appears that when you update the priority of a vertex, it might just as well be an increased or a decreased priority. The algorithm on the other hand appears to expect that priorities only increase. update() as well as push_or_update() only call preserve_heap_property_up(index) and not preserve_heap_property_down(index). Again, I am not sure... do check. I would like the heap to remain copyable! Alex

On Wed, 5 Sep 2012, David Doria wrote:

On Wed, Sep 5, 2012 at 11:59 AM, Alex Hagen-Zanker wrote:

...

On 05/09/2012 16:14, David Doria wrote:

...

but the output is still really wacky

I am not sure, but it appears that when you update the priority of a vertex, it might just as well be an increased or a decreased priority.

The algorithm on the other hand appears to expect that priorities only increase.

update() as well as push_or_update() only call preserve_heap_property_up(index) and not preserve_heap_property_down(index).

Again, I am not sure... do check.

I would like the heap to remain copyable!

Alex

Ah, you got it! This code produces the problem repeatably: http://codepad.org/H2Mnqt8j

(no randomness, the values that were producing an incorrect result are hard-coded). The output with the existing algorithm is:

The priority queue is: vertex: 1 1 priority: 514 vertex: 0 1 priority: 793 vertex: 0 0 priority: 355 vertex: 1 0 priority: 12

Then I changed the update function from:

preserve_heap_property_up(index);

to preserve_heap_property_up(index); preserve_heap_property_down();

and ran it again. The output is now correct!:

The priority queue is: vertex: 0 1 priority: 793 vertex: 1 1 priority: 514 vertex: 0 0 priority: 355 vertex: 1 0 priority: 12

Can we add a function that does this? In fact, the update() function seems like it could be renamed to increase_priority() or something, while the new function (with update up and down) would be just "update()". Thoughts?

The heap's intention is to be used for Dijkstra's algorithm, where the distances only decrease. You might want to look at Boost.Heap as well, since d_ary_heap_indirect is meant mostly for internal BGL use. If that doesn't work, I can try putting in the update function you want as long as it always correctly preserves the heap invariants. -- Jeremiah Willcock

On Wed, 5 Sep 2012, David Doria wrote:

...

The heap's intention is to be used for Dijkstra's algorithm, where the distances only decrease. You might want to look at Boost.Heap as well, since d_ary_heap_indirect is meant mostly for internal BGL use.

The reason I was using d_ary_heap_indirect was for the "indirect" part. I want to store objects (vertices) in the priority queue, but prioritize them based on values in an external map (the PriorityMapType in my examples). From the documentation it doesn't look like Boost.Heap can do that (http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concep...) - am I missing it?

(Also, Boost.Heap seems to have exactly the interface I was suggesting of an increase(), decrease(), and update() if you're not sure which of the two former functions to use.)

There is an indirect_cmp in the graph library; that might be usable with Boost.Heap.

...

If that doesn't work, I can try putting in the update function you want as long as it always correctly preserves the heap invariants.

I don't know how we would prove that it always maintains the invariants, but it seems to make sense, right? It just (currently) goes up the queue, swapping if it is out of order, then goes down the queue (new addition), swapping if it is out of order. If the first pass (_up() ) does find a reason to swap, then the down() pass would just do nothing (as the swapped item is guaranteed to be larger than any of the ones below the position of the item to update). If the up() pass does nothing, then the down() pass would work as normal.

I'll need to look into that issue further. -- Jeremiah Willcock