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:58:21

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