[Lemon-user] Fibonnaci Heap

[Kovács Péter]

Hi Peter,

You have to set all values of the item-index map to -1 before you use a 
heap structure. Otherwise its behavior is undefined (since the content 
of a newly allocated array or vector is undefined in C++).

I admit that this requirement is not emphasized enough in the reference 
manual, but it is clearly written here:
http://lemon.cs.elte.hu/pub/doc/1.2.3/a00138.html#ab3f82678fc257f80edb84d5d9b9383ee
as well as for the constructors of all other heap classes.

I attached a modified version of your code that tests several heap 
implementations.

Regards,
Peter


On 2012.11.29. 19:19, Peter A. Kolski wrote:
> Dear Peter,
>
>> Dear Peter,
>>
>>> Dear LEMON Users,
>>> from what I read, Fibonacci Heaps are faster than Binary Heaps.
>>
>> Theoretically, Fibonacci heaps are faster, but in practice, they are
>> usually slower than the standard binary heaps. Actually, it depends on
>> the use case, which heap implementation is the most efficient.
>>
>>> The latter ones work well in LEMON. The first I just can get to work.
>>> There is always a EXC_BAD_ACCESS.
>>
>> Isn't it caused by pushing the same arc (with id 0) twice to the heap?
>
> I forgot to say, that both cases do not work. Pushing it "by hand" or
> pushing it via the Arc Iterator.
> So after commenting one out, no matter if the first or the second case,
> I can't push anything.
>
> The bad access happens in the LEMON code here (marked with XXX):
>
>
> void push (const Item& item, const Prio& prio) {
> int i=_iim[item];
> if ( i < 0 ) {
> int s=_data.size();
> _iim.set( item, s );
> Store st;
>          st.name=item;
> _data.push_back(st);
>          i=s;
>        } else {
> XXX _data[i].parent=_data[i].child=-1;
> _data[i].degree=0;
> _data[i].in=true;
> _data[i].marked=false;
>        }
>
> Does the code work for you? Or did I do something wrong?
>
>>> Why is this happening?
>>> Is it really worth to use FibHeaps? I have to push many arc into the
>>> heap.
>>>
>>> Thank you very much!
>>
>> As I wrote above, it depends on your use case. You may either perform
>> some benchmarks or simply use binary heaps (they are rather efficient
>> is most cases).
>>
>> Some benchmark results of LEMON's heap implementations applied in
>> Dijkstra's algorithm can be found here:
>> https://lemon.cs.elte.hu/trac/lemon/attachment/ticket/313/heap_benchmark_results.txt
>>
>
> But as I see from your tests, I should anyway rather go for another heap
> structure for testing.
>
>
> Best regards
>
> Peter
>
>
>
>> Best regards,
>> Peter
>>
>>
>>>
>>> int main(){
>>> FullGraph                   f(1000);
>>> FullGraph::ArcMap< int >    cost( f );
>>> FullGraph::ArcMap< int >    fibHeapMap( f );
>>> FibHeap< int, FullGraph::ArcMap<int> >    myFibHeap( fibHeapMap );
>>>
>>>
>>> for (FullGraph::ArcIt a( f ); a!=INVALID; ++a) {
>>>         cost[a] = rnd.integer( 100 );
>>>     }
>>>
>>>
>>> // --- first
>>>     myFibHeap.push( f.arcFromId( 0 ), 3 );
>>>
>>>
>>> // --- second
>>> for (FullGraph::ArcIt a( f ); a!=INVALID; ++a){
>>>         myFibHeap.push( a, cost[ a ]);
>>>     }
>>>   }
>>>
>>>
>>>
>>> _______________________________________________
>>> Lemon-user mailing list
>>> Lemon-user at lemon.cs.elte.hu <mailto:Lemon-user at lemon.cs.elte.hu>
>>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: heap_test.cpp
Type: text/x-c++src
Size: 2266 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20121129/72ca9030/attachment.cpp>