Grafuri in Scheme - ciclicitate

; a si b sunt grafuri

(define a '((0 1 2 3)((0 1 1 0) (1 0 0 1) (1 0 0 1) (0 1 1 0))))

(define b '((0 1 2 3)((0 0 1 0) (0 0 0 1) (1 0 0 1) (0 1 1 0))))

; reprezentarea grafului e (noduri matDeAdiac)

; o lista care are 2 liste

; prima lista e cea cu nodurile (0 1 2 3)

; e folosita pt parcurgerea grafului din toate nodurile

; a 2-a lista e o lista de liste cu 0 si 1

(define pos

(lambda(l n)

(if(= n 0) (car l)

(pos (cdr l) (- n 1)))))

(define ap1

(lambda(a n)

(if(null? a) '()

(if(= 1 (car a))

(cons n (ap1 (cdr a) (+ n 1)))

(ap1 (cdr a) (+ n 1))))))

(define vecini

(lambda(a n)

(ap1 (pos a n) 0)))

(define in

(lambda(l x)

(if(null? l) #f

(if(= x (car l)) #t

(in (cdr l) x)))))

(define fct

(lambda (a l)

(lambda(x)

(parc a x l))))

(define map2

(lambda(l f)

(if(null? l) '()

(cons (f (car l)) (map2 (cdr l) f)))))

; cut scoate un element dintr-o lista

; (cut '(1 2 3 4) 1) retureaza (2 3 4)

; e folosita de functia pt parcurgere

; daca ajung in nodul u din nodul v (v e vecin cu u) si il scot din lista de vecin

(define cut

(lambda(l x)

(if(null? l) '()

(if(= x (car l)) (cut (cdr l) x)

(cons (car l) (cut (cdr l) x))))))

; functia parc parcurge graful dintr-un nod si mentine o lista despre originea grafului (cum a aparut)

; apoi isi ia vecinii si il ignora pe cel din care am venit eu, si reapeleaza functia pt ce a ramas

; daca nodul e in lista din care a venit inseamna ca e ciclu

; daca nu mai sunt vecini, nu e ciclu pe ramura asta a dfs-ului

(define parc

(lambda(a n l)

(if(in l n) #t

(if(null? (cut (vecini a n) (car l))) #f

(map2 (cut (vecini a n) (car l)) (fct a (cons n l)))))))

(define ciclu

(lambda(a)

(map2 (car a) (fct (cadr a) '(-1)))))

(ciclu a)

(ciclu b)