Algoritmos de grafos

(define grafo '( (i (a b))    ;;        a ---- c ---- x
                 (a (i c d))  ;;      /   \  /
                 (b (i c d))  ;;     /     \/
                 (c (a b x))  ;;   i       X
                 (d (a b f))  ;;     \    / \
                 (f (d))      ;;      \  /   \
                 (x (c))      ;;        b ---- d ---- f
                 ))           ;;

; Recorre una lista aplanada de elementos
; Comprueba la existencia de un elemento en la lista
(define (miembro? ele lista)
  (cond
     ((null? lista)#f)
     ((equal? ele (car lista))#t)
     (else
         (miembro? ele (cdr lista))
     )
  )
)

; Recibe una función booleana y una lista
; Si la lista es nula, retorna la lista
; Si el car de la lista es una función, quita el car y continua el algoritmo con la cola (cdr)
; Por el contrario, si el car de la lista no es una función, mete el car en una nueva lista que
; empieza a construir
(define (remove-if fun? lista)
  (cond
        ((null? lista) lista)
        ((fun? (car lista)) (remove-if fun? (cdr lista)))
        (else
            (cons (car lista) (remove-if fun? (cdr lista)))
        )
   )
)

; Car   -> (i (a b))
; Cadr  ->   ((a b))
; Cadar ->     (a b)
(define (vecinos nodo grafo)
  (cond
    ((null? grafo)#f)
    ; caar del grafo: Es el nodo evaluado
    ; car del cdr; Es la lista de vecinos del nodo
    ; cadar ; es el primer vecino
    ((equal? (car (car grafo)) nodo) (car (cdr (car grafo)))) ;) ;(cadar grafo)
    (else
      (vecinos nodo (cdr grafo)))
    )
  )

; Este algoritmo no es recursivo
; Recibe una ruta, por ejemplo (a)
; los vecinos de a son (i c d)
; Toma el car de la ruta, en este caso el car de la ruta es el car d (a), y el car sería a
; Busca los vecinos del car de la ruta, o sea de a
; A cada uno de esos vecinos le aplica una función
; Si el vecino ya es miembro de la ruta, lo convierte en una lista vacía
; Si el vecino no es miembro de la ruta, mete el vecino a la ruta
; Agarra esa lista y elimina todas las listas vacías de los vecinos que ya eran miembros
(define (extender ruta grafo)
  (remove-if null?
     (map (lambda(vecino)
            (cond
               ( (miembro? vecino ruta) '())
               ( else
                  (cons vecino ruta)
                )
             )
           )
          (vecinos (car ruta) grafo)
      )
   )
)

;; Metodo de busqueda en profundidad primero
;; Retorna una ruta desde ini hasta fin (Pero no es la ruta más corta, solo una posible ruta)
;; (prof a i grafo)
;; > (prof i ((a)) grafo)
(define (prof ini fin grafo)
  (prof-aux (list (list ini)) fin grafo)
)

; Recibe dos nodos, el nodo inicial y el nodo final, y un puntero al grafo
; El propósito es mostrar una ruta entre esos dos nodos
(define (prof-aux rutas fin grafo)
  (display "Rutas: ")
  (display rutas)
  (newline)
  (cond
    ((null? rutas)'())
    ((equal? fin (car (car rutas))) (reverse (car rutas)))
    (else
       (prof-aux
          (append (extender (car rutas) grafo) (cdr rutas)) ; parametro 1
          fin                                               ; parametro 2
          grafo                                             ; parametro 3
       )
    )
  )
)

; Métodos Alternativos

; (define (miembro? ele lista)
;   (ormap (lambda(x) (equal? x ele))
;          lista))


; (define (remove-if fun? lista)
;   (apply append
;          (map (lambda(x) (cond ((fun? x) '())
;                                (else (list x))))
;               lista)))
;


; (define (vecinos nodo grafo)
;   (let ( (resultado (assoc nodo grafo))
;          )
;     (cond ( (equal? resultado #f)
;             #f)
;           ( else
;             (cadr resultado)))))