;;; -*- Mode: Lisp; Syntax: Common-Lisp; -*- File: search/domains/route-finding

;;;; Find a Route Between Cities on a Map usinf a A* search algorithm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(load "my-route-finding.lsp")


(defun busqueda_profundidad_prior (prob_name)
  
(setq list-of-paths   NIL)  ; Initialise the list of paths   
(setq camino      (list   (problem-initial-state prob_name) )) ; Initialise the best path with the initial city 
(setq city        (problem-goal   prob_name))  ; Initialise the goal
(setq n 0)         ; Initailise the number of iterations

(loop 
(progn 
   ; Stop the loop if the node of the FIRST path is equal to the goal 
   (if  (string-equal (first camino) city)  (return  (list n camino)  ) )
   (setq llista  (successors prob_name    (first camino)) )  ; Get the successors of the last node 
   (setq novel-paths  (inserta_sucesores  llista   camino))  ; Build the novel paths
   (setq novel-paths-without-loops (eliminate-loops novel-paths ))    ; Eliminate loops from current list
   (setq list-of-paths (append novel-paths-without-loops list-of-paths ))  ; Insert the novel paths into the list
   (setq camino (first list-of-paths)) ; update the list of paths
   (setq list-of-paths (rest list-of-paths) )
   (setq n (+ n 1))
)
) 
)


;*********************************************************
;		EJEMPLO DE EJECUCIÓN
;*********************************************************

; Definición de la estructura
(setq p (make-route-finding-problem))


; El estado inicial (ciudad origen) y final (ciudad destino)
; se pueden cambiar de la siguiente manera
; (setq p (make-route-finding-problem :initial-state 'NOMBRE_DE_LA_CIUDAD_ORIGEN :goal 'NOMBRE_DE_LA_CIUDAD_DESTINO :map *ROMANIA-MAP*))

(busqueda_profundidad_prior p)