[cl-heap-devel] Number of arguments heap key function should accept?

[Malcolm Reynolds]

Hi Rudy

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.

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:


invalid array index 3 for #(NIL NIL NIL) (should be nonnegative and <3)
   [Condition of type SIMPLE-TYPE-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [ABORT] Return to SLIME's top level.
 2: [ABORT] Exit debugger, returning to top level.

Backtrace:
  0: ((LABELS CL-HEAP::SORT-NODE) #<CL-HEAP::NODE Item: #S(MST-NODE :GID C
:MIN-DIST 4 :PARENT F) {11FAEA91}>)
      Locals:
        SB-DEBUG::ARG-0 = #<CL-HEAP::NODE Item: #S(MST-NODE :GID C :MIN-DIST
4 :PARENT F) {11FAEA91}>
  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}>)
      Locals:
        SB-DEBUG::ARG-0 = #(2 NIL 3 NIL)
        SB-DEBUG::ARG-1 = :<NOT-AVAILABLE>
        SB-DEBUG::ARG-2 = #<CL-HEAP:FIBONACCI-HEAP Size: 8 {11FADE29}>
  2: ((SB-PCL::FAST-METHOD PRIMS-MIN-ST (GRAPH)) #<unavailable argument>
#<unavailable argument> #<GRAPH {11FAD441}>)[:EXTERNAL]
      Locals:
        SB-DEBUG::ARG-0 = 5
        SB-DEBUG::ARG-1 = :<NOT-AVAILABLE>
        SB-DEBUG::ARG-2 = :<NOT-AVAILABLE>
        SB-DEBUG::ARG-3 = #<GRAPH {11FAD441}>
  3: (SB-INT:SIMPLE-EVAL-IN-LEXENV (RUN-WITH-MST-TEST-GRAPH (PRIMS-MIN-ST
GRAPH :ROOT-ID-OVERRIDE 'F)) #<NULL-LEXENV>)
 --more--


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:

invalid array index 4 for #(NIL NIL
                            #<CL-HEAP::NODE Item: #S(MST-NODE
                                                     :GID N2
                                                     :MIN-DIST 5
                                                     :PARENT N17)
{1250F6B9}>
                            NIL) (should be nonnegative and <4)
   [Condition of type SIMPLE-TYPE-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [ABORT] Return to SLIME's top level.
 2: [ABORT] Exit debugger, returning to top level.

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.

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.

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...

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.

Best wishes, and many thanks for your work on this library!

Malcolm




On Thu, Jun 11, 2009 at 11:02 PM, Rudy Neeser <rudy.neeser at gmail.com> wrote:

>  Hi Malcolm,
>
> I'm glad to see you using the library ;)
>
> 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.
>
> 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.
>
> Good luck with your project.
> Rudy
>
>
>
> On Thu, 2009-06-11 at 15:04 +0100, Malcolm Reynolds wrote:
>
> 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 listcl-heap-devel at common-lisp.nethttp://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-heap-devel/attachments/20090617/9e9ea441/attachment.html>