[Lemon-user] Fibonnaci Heap

[Kovács Péter]

Hi Peter,

I'm glad to hear that your problem was solved.

The iPad application using LEMON is interesting, thank you for sharing 
it with us.

Regards,
Peter


On 2012.11.30. 1:18, Peter A. Kolski wrote:
> Peter!
> That really was not clear to me - and solved the problem!
>
> Thank you very much, also for the attached code.
>
> Now I even read, that I have to reset the map to -1, if the heap wasn't empty. Might be worth mentioning both informations in the head of the documentation to avoid errors by users. Using the BinHeap (nearly same code) didn't cause any error ever.
>
> BTW. I have written a iPad app using LEMON. It simulates epidemic spead on networks. As soon as it passed the review process I will write to you about the details.
> It will be free as a demo version.
>
> Best regard
>
> Peter
>
>
>
> Am 29.11.2012 um 23:38 schrieb Kovács Péter <kpeter at inf.elte.hu>:
>
>> 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
>>>>>
>>>>
>>>
>> <heap_test.cpp>_______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>