[cl-heap-devel] Number of arguments heap key function should accept?
Rudy Neeser
rudy.neeser at gmail.com
Fri Jun 19 10:54:02 UTC 2009
Hi Malcolm,
I believe that you've found a bug in the library, rather than been using
it wrong. And the fix that you've given is good.
The RANKS array should be an array whose last index is the maximum rank
that a tree could have - clearly I was setting it to 1- that.
I've updated both the SVN repository and the ASDF install with a newer
version.
Thanks for catching that! Have your MSTs all been calculated correctly
after you patched the library?
Best,
Rudy
On Wed, 2009-06-17 at 17:39 +0100, Malcolm Reynolds wrote:
> Hi
>
> (apologies to anyone reading this who hasn't received my previous
> message, I think it might be in a moderation queue as I apparently
> hadn't finished my signup. It's quoted below regardless)
>
> I've found a fix for this crash, not sure how technically correct it
> is.. but I can now run Prim's MST on the graph I was having trouble
> with before, with any node as the root. I'm going to go through and
> check that what is being returned is a correct MST in any case, which
> will be a bit laborious, but the first couple that I've checked are
> correct.
>
> The fix is in #'pop-heap in fibonacci-heap.lisp, in the (labels
> ((sort-node) ...)) specifically. The crash is caused by (aref ranks
> position) after initialising position to (node-rank node). I hacked in
> some print statements because I thought it might be a simple
> off-by-one where the index was always one too big, but I saw lots of
> instances of trying to access the zero'th element of a 4 element
> array, followed by trying to access the fourth place which causes the
> crash. Just to see if it improved things I increased the size of ranks
> by changing
>
> (ranks (make-array (ceiling (log count 2)) :initial-element nil))
>
> to
>
> (ranks (make-array (1+ (ceiling (log count 2))) :initial-element nil))
>
> and the crashes all stopped. I hesitate to claim this is a real bug
> fix because I'm not familiar with the details of how a fib heap works,
> and what this specific bit of code is actually doing, but it seems to
> work as far as I can see.
>
> I'm going to finish checking all the MSTs for correctness, it would be
> great to know if the fix I've used is okay.
>
> Thanks
>
> Malcolm
>
> On Wed, Jun 17, 2009 at 5:03 PM, Malcolm
> Reynolds<malcolm.reynolds at gmail.com> wrote:
> > 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 list
> >> cl-heap-devel at common-lisp.net
> >> http://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/20090619/77ae4943/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
URL: <https://mailman.common-lisp.net/pipermail/cl-heap-devel/attachments/20090619/77ae4943/attachment.sig>
More information about the Cl-heap-devel
mailing list