;;;
;;; Test Of Search Tools
;;; Based Roughly On The Descriptions In Russell & Norvig (1995)
;;;
;;; This code requires the previous loading of the "SEARCH" utilities.
;;;
;;; DAVID NOELLE  Thu Apr 18 09:44:26 1996
;;;


;;;
;;; Package
;;;

(cl::defpackage "COMMON-LISP-USER" 
  (:use "SEARCH"))

(cl::in-package "COMMON-LISP-USER")


;;;
;;; State Description & Operators
;;;

(defvar *city-adjacency-list*
  '((arad . (sibiu timisoara zerind))
    (bucharest . (fagaras giurgiu pitesti urziceni))
    (craiova . (dobreta pitesti rimnicu-vilcea))
    (dobreta . (craiova mehadia))
    (eforie . (hirsova))
    (fagaras . (bucharest sibiu))
    (giurgiu . (bucharest))
    (hirsova . (eforie urziceni))
    (iasi . (neamt vaslui))
    (lugoj . (mehadia timisoara))
    (mehadia . (dobreta lugoj))
    (neamt . (iasi))
    (oradea . (sibiu zerind))
    (pitesti . (bucharest craiova rimnicu-vilcea))
    (rimnicu-vilcea . (craiova pitesti sibiu))
    (sibiu . (arad fagaras oradea rimnicu-vilcea))
    (timisoara . (arad lugoj))
    (urziceni . (bucharest hirsova vaslui))
    (vaslui . (iasi urziceni))
    (zerind . (arad oradea))))

(defun print-city (city &optional (stream t))
  (prin1 city stream))

;;; all-adjacent-cities-operator  --  Return a fresh list of all
;;; cities adjacent to the given city.      
(defun all-adjacent-cities-operator (city)
  (copy-list (cdr (assoc city *city-adjacency-list*))))


;;;
;;; Find Route Between Cities
;;;

;;; find-route  --  Use breadth-first search to find the shortest
;;; route from the "source" city to the "destination" city.  Routes
;;; are measured in number of cities visited.  Note that this
;;; function is pretty dumb.  It uses the "all-adjacent-cities-operator"
;;; and doesn't even check for cycles in the route.  Much more
;;; efficient searches would be possible if the operator used was
;;; smarter.
(defun find-route (source destination)
  (let ((problem 
	 (make-problem :initial-state source
		       :operators '(all-adjacent-cities-operator)
		       :goal-test (function
				   (lambda (city)
				     (eq city destination)))))
	(goal-node nil))
    (clear-expand-count)
    (setq goal-node (breadth-first-search 
		     problem :depth-limit (list-length *city-adjacency-list*)))
    (if goal-node
      (print-path goal-node t #'print-city)
      (format t "~&No path found between ~A and ~A!~&" source destination))
    (format t "~&Number of nodes expanded:  ~D.~&" (current-expand-count))))