[Chicken-hackers] [PATCH] Reimplement topological-sort with cycle detection

[Moritz Heidkamp]

Fellow Chickeneers,

I recently noticed that Chicken's topological-sort function does not
detect cycles in the passed graph. Initially I ventured into patching
this functionality into the existing implementation which originates
from SLIB. This turned out to be tricky as it is a heavily imperative
implemenatation. By the time I had figured out how it works I had
already opened the relevant chapter of Introduction to
Algorithms. According to the header comment of the SLIB implementation
(see
http://cvs.savannah.gnu.org/viewvc/slib/slib/tsort.scm?revision=1.2) it
is also based on that algorithm, but apparently without the cycle
detection (or maybe it wasn't in the 1st edition which is what the
author used, while I used the 3rd edition). Eventually I found it easier
to reimplement the algorithm in a functinal style to add the cycle
detection bit.

One thing I'm not sure about is how I raise the condition in case a
cycle is detected. Comments on that are very welcome!

Have a nice Sunday
Moritz

0001-Reimplement-topological-sort-with-cycle-detection.patch
Description: Text Data