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

Subject: Re: [Boost-users] BGL: d_ary_heap_indirect duplicated values
From: David Doria (daviddoria_at_[hidden])
Date: 2012-09-05 11:42:53

Ok, I see a couple of the things I was doing wrong (outputting the
heap map inside a loop where it was changing, and outputting the heap
map values after the queue had been emptied (I understand now that
they are all set to (size_t)(-1)).

Here is a more correct version:

http://ideone.com/cZosV

Unfortunately, it still doesn't work :(

Here is the output:

Initial heap map
Index: 4294967295
Index: 4294967295
Index: 4294967295
Index: 4294967295
There are 0 items in the queue.
Original priority for 0, 0 316
Index added: 0
Original priority for 1, 0 493
Index added: 1
Original priority for 0, 1 488
Index added: 2
Original priority for 1, 1 867
Index added: 3
Heap map after initial pushes:
Index: 1
Index: 3
Index: 2
Index: 0
There are 4 items in the queue.
New priority for 0, 0 724
New priority for 1, 0 753
New priority for 0, 1 577
New priority for 1, 1 127
Heap map after updates:
Index: 1
Index: 3
Index: 2
Index: 0
There are 4 items in the queue.
vertex: 1 1 priority: 127
vertex: 1 0 priority: 753
vertex: 0 0 priority: 724
vertex: 0 1 priority: 577
Heap map at end:
Index: 4294967295
Index: 4294967295
Index: 4294967295
Index: 4294967295

You can see that these priorities that are output in the last loop are
not sorted. They seem to be sorted on most runs, but 1 out of 5 or so
seems to produce these unordered priorities.

What can we try next :) ?

David