Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-09-05 10:31:23

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