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