Any simple algo for checking if list has a cyclic connections between
leafs ?
Something like 123->gb->231->ww
^ |
^<-----------
Cyclyc-redundancy-p the test should return t?
Already have dijkstra algo in mind but it looks like an overkill.
jt
·············@gmail.com writes:
> Any simple algo for checking if list has a cyclic connections between
> leafs ?
> Something like 123->gb->231->ww
> ^ |
> ^<-----------
>
> Cyclyc-redundancy-p the test should return t?
> Already have dijkstra algo in mind but it looks like an overkill.
http://www.lispworks.com/documentation/HyperSpec/Body/f_list_l.htm has
some example code that will detect cycles.
Zach
·············@gmail.com writes:
> Any simple algo for checking if list has a cyclic connections between
> leafs ?
> Something like 123->gb->231->ww
> ^ |
> ^<-----------
>
> Cyclyc-redundancy-p the test should return t?
> Already have dijkstra algo in mind but it looks like an overkill.
Otherwise, a classic algorithm is to use a slow and a fast cursor, and
if they meet, you've got a cycle:
(defun cyclicp (list)
(labels ((step (slow fast)
(cond
((null fast) (return-from cyclicp nil))
((eq slow fast) (return-from cyclicp t))
(t (step (cdr slow) (cddr fast))))))
(step list (cdr list))))
(mapcar (function cyclicp)
'(() (a b c) #1=(#1#)
#2=(a . #2#) (a b c . #3=(d . #3#)) (a b c . #4=(d e . #4#)) (a b c . #5=(d e f . #5#))))
--> (NIL NIL NIL T T T T)
--
__Pascal Bourguignon__
http://www.informatimago.com
http://pjb.ogamita.org