Hi Rudy<br><br>Thanks for your quick reply. I see your point about the setf'able place, it would be good if that were solvable but the library is quite usable as it is.<br><br>I've been running some tests on my implementation of Prim's and I have a bug I can't quite figure out, I'm not sure whether it's in my code or cl-heap. The exact error that occurs is always in a call to #'cl-heap:pop-heep, with a fibonacci heap if that makes any difference. #'cl-heap:peep-at-heap never has any problems telling me what the next item on the heap is, but actually popping it causes a crash like the following:<br>
<br><br>invalid array index 3 for #(NIL NIL NIL) (should be nonnegative and <3)<br> [Condition of type SIMPLE-TYPE-ERROR]<br><br>Restarts:<br> 0: [RETRY] Retry SLIME REPL evaluation request.<br> 1: [ABORT] Return to SLIME's top level.<br>
2: [ABORT] Exit debugger, returning to top level.<br><br>Backtrace:<br> 0: ((LABELS CL-HEAP::SORT-NODE) #<CL-HEAP::NODE Item: #S(MST-NODE :GID C :MIN-DIST 4 :PARENT F) {11FAEA91}>)<br> Locals:<br> SB-DEBUG::ARG-0 = #<CL-HEAP::NODE Item: #S(MST-NODE :GID C :MIN-DIST 4 :PARENT F) {11FAEA91}><br>
1: ((SB-PCL::FAST-METHOD CL-HEAP:POP-HEAP (CL-HEAP:FIBONACCI-HEAP)) #(2 NIL 3 NIL) #<unavailable argument> #<CL-HEAP:FIBONACCI-HEAP Size: 8 {11FADE29}>)<br> Locals:<br> SB-DEBUG::ARG-0 = #(2 NIL 3 NIL)<br>
SB-DEBUG::ARG-1 = :<NOT-AVAILABLE><br> SB-DEBUG::ARG-2 = #<CL-HEAP:FIBONACCI-HEAP Size: 8 {11FADE29}><br> 2: ((SB-PCL::FAST-METHOD PRIMS-MIN-ST (GRAPH)) #<unavailable argument> #<unavailable argument> #<GRAPH {11FAD441}>)[:EXTERNAL]<br>
Locals:<br> SB-DEBUG::ARG-0 = 5<br> SB-DEBUG::ARG-1 = :<NOT-AVAILABLE><br> SB-DEBUG::ARG-2 = :<NOT-AVAILABLE><br> SB-DEBUG::ARG-3 = #<GRAPH {11FAD441}><br> 3: (SB-INT:SIMPLE-EVAL-IN-LEXENV (RUN-WITH-MST-TEST-GRAPH (PRIMS-MIN-ST GRAPH :ROOT-ID-OVERRIDE 'F)) #<NULL-LEXENV>)<br>
--more--<br><br><br>Sometimes the array that an invalid index is used on isn't full of nil, at other times the array has one (I've never seen it with more than one, but not to say it never happens) element which contains a cl-heap::node wrapping my mst-node data structure, as in the following:<br>
<br>invalid array index 4 for #(NIL NIL<br> #<CL-HEAP::NODE Item: #S(MST-NODE<br> :GID N2<br> :MIN-DIST 5<br>
:PARENT N17) {1250F6B9}><br> NIL) (should be nonnegative and <4)<br> [Condition of type SIMPLE-TYPE-ERROR]<br><br>Restarts:<br> 0: [RETRY] Retry SLIME REPL evaluation request.<br>
1: [ABORT] Return to SLIME's top level.<br> 2: [ABORT] Exit debugger, returning to top level.<br><br>In all the cases I've seen the index being used seems to be just one too big for the array, but that might be a coincidence I guess.<br>
<br>The really odd thing about this bug is the way I can reproduce it - basically I have some test graph structures which I'm running Prim's MST on. Depending on which node I select to be the root (which obviously controls the order that all the other nodes come out of the priority queue) the algorithm either runs to completion (giving what appears, on the cases I've examined, to be the correct minimum spanning tree) or errors out half way through with an error like the above. Which roots cause the bug and which don't is completely constant, but I haven't been able to figure out the pattern yet.<br>
<br>I only post this here because the error is triggered in cl-heap code, I would fully expect the error to be on my side, but I just thought you might be able to point me in the direction of how I'm using the heap wrong. Currently all I do with the heap for the whole algorithm is fill it full of my mst-node structures (these only contain some id marker, an id of their parent node, and a distance field), save what #'cl-heap:add-to-heap returns in a hash-table (to be able to access them for decreasing of keys), then I repeatedly pop the heap, relax all the neighbours of the node I've just popped, and call #'cl-heap:decrease-key on any that end up with a new smaller distance. I'm getting the right result some (most!) of the time so I figure I can't be too far off...<br>
<br>If you would like my code to reproduce the crash I can probably package it up for you, it's a monolith of bits and pieces at the moment (master's thesis research code => not very user friendly) but we could work something out if you need it.<br>
<br>Best wishes, and many thanks for your work on this library!<br><br>Malcolm<br><br><br><br><br><div class="gmail_quote">On Thu, Jun 11, 2009 at 11:02 PM, Rudy Neeser <span dir="ltr"><<a href="mailto:rudy.neeser@gmail.com">rudy.neeser@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>
Hi Malcolm,<br>
<br>
I'm glad to see you using the library ;)<br>
<br>
You're right about the :key argument: if you're going to use a function that needs to update the priorities of nodes in the heap, then :key will have to be a function that accepts a second argument. The example code that you've given looks good, and is exactly how it's intended to be done. <br>
<br>
Unfortunately I haven't been able to think of a much better way of doing this. I'd thought of using a setf'able place, but SETF operates by performing macro expansions at compile time, while the value sent to :key is a function that's going to be evaluated at runtime. I might try to get around this using EQL specialisers in the next version. <br>
<br>
Good luck with your project.<br>
Rudy<div><div></div><div class="h5"><br>
<table cellpadding="0" cellspacing="0" width="100%">
<tbody><tr>
<td>
<br>
</td>
</tr>
</tbody></table>
<br>
On Thu, 2009-06-11 at 15:04 +0100, Malcolm Reynolds wrote:
</div></div><blockquote type="CITE">
<pre>Hi
I'm currently implementing Prim's MST algorithm using CL-heap. The
structure which I'm keeping in the fibonacci heap is called an
mst-node and it has a field min-dist which is the key that the heap
should be a min-queue according to. I thought I'd be able to pass
#'mst-node-min-dist as the :key argument in the heap instantiation but
that gave me errors complaining that the function used as heap key
needs to accept two arguments. After a bit of playing around it
appears the key function needs to take an optional second argument,
which if used should update the key in the item? Is this correct? I'm
currently using this and I'm wondering if there is a better way (since
mst-node-min-dist is setf'able)...
(make-instance 'cl-heap:fibonacci-heap
:key #'(lambda (x &optional y)
(if y
(setf (mst-node-min-dist x) y)
(mst-node-min-dist x))))))
Many thanks,
Malcolm
_______________________________________________
cl-heap-devel mailing list
<a href="mailto:cl-heap-devel@common-lisp.net" target="_blank">cl-heap-devel@common-lisp.net</a>
<a href="http://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel" target="_blank">http://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel</a>
</pre>
</blockquote>
</div>
</blockquote></div><br>