(define G '((a b c d e m)
            (b a)
            (c a d f)
            (d a c e f)
            (e a d)
            (f c d)
            (h m)
            (m h a)))

(define H '((a b d e)
            (b a f)
            (c f)
            (d a)
            (e a)
            (f b c)))


;Извлича върховете от граф
(define (get-nodes graph)
  (map car graph))


;Извлича всички наследници на връх
(define (get-sucs graph node)
  (if (null? graph) '()
      (if (equal? (caar graph) node) (cdar graph)
          (get-sucs (cdr graph) node))))

; Дава списък от всички пътища разширения на пътя path в graph
;Не допуска да се върнем в последния връх от който сме дошли
(define (extend path graph)
  (filter (lambda (x) (or (< (length x) 3) (not (equal? (car x) (caddr x)))))
     (map (lambda (x) (cons x path)) (get-sucs graph (car path)))))


; Дава списък от всички пътища, които са ациклични разширения на пътя path в graph
(define (extend-no-cycle path graph)
  (filter (lambda (x) (not (member (car x) (cdr x))))
          (extend path graph)
  )
)


; Проверява дали пътя path съдържа цикъл
(define (is-cycle? path)
  (if (and (> (length path) 3)
           (or (member (car path) (cddr path)) (is-cycle? (cdr path))))
      #t #f
  )
)


; Проверява дали в graph има цикъл
(define (is-cyclic? graph)
  (define (cycle-dfs front)
    (if (null? front) #f
        (let ((path (car front)))
          (or (is-cycle? path)
              (cycle-dfs (append (extend path graph) (cdr front)))
          )
        )
    )
  )
  (cycle-dfs (map list (get-nodes graph)))
)


; Проверява дали в graph има път между a и b
(define (has-path? a b graph)
  (define (dfs front)
    (if (null? front) #f
        (let ((path (car front)))
          (or (equal? (car path) b)
              (dfs (append (extend-no-cycle path graph) (cdr front)))
          )
        )
     )
  )
  (dfs (list(list a)))
)


; Проверява дали в graph има път между всеки два върха
; Предполага се неориентиран граф, така че е достатъчен път между един връх и всички останали
; Ако се изисква силно свързан насочен граф - трябва да се разшири за път от всеки до всеки
(define (is-connected? graph)
  (let ((nodes (get-nodes graph)))
       (foldl (lambda (x y) (and y (has-path? (car nodes) x graph))) #t (cdr nodes))
  )
)

; Проверява дали граф е дърво
(define (is-tree? graph)
  (and (is-connected? graph) (not (is-cyclic? graph))))