; Cyclic test for directed graphs represented as a certain kind of association list.
; This example was used in Lecture as an example of mutual recursion.
; The code is provided by Ryan Brewster

(define x1 '((a (c e)) (b (d)) (c ()) (d (c)) (e (b d))))  ;hopefully should return non-cyclic
(define x2 '((a (c e)) (b (d)) (c (e)) (d (c)) (e (b d)))) ;hopefully should return cyclic

(define (cyclic? graph)
	(check-cycle (map first graph) graph ())
)

(define (check-cycle nodes graph seen)
	(if (null? nodes)
		#f
		(if (check-cycle-from (first nodes) graph seen)
			#t ;if there is a cycle from this node, we're done
			(check-cycle (rest nodes) graph seen) ;if not, check the rest of the nodes
		)
	)
)

(define (check-cycle-from node graph seen)
	(if (member node seen)
		#t ;if we've already been at this node before, we have found a cycle
		(check-cycle  ;else, start the process again from THIS node this time
			(second (assoc node graph)) ;branch out to all the nodes this one points to
			graph ;the graph is still the same
			(cons node seen) ;we've now been to this node as well
		)
	)
)

(load "tester.scm")

(test (cyclic? x1) '#f)
(test (cyclic? x2) '#t)