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
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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel
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@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@common-lisp.nethttp://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel
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@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@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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel
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@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@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@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/cl-heap-devel
participants (2)
-
Malcolm Reynolds -
Rudy Neeser