This little program finds the shortest path through a network from one node to another. For example, when the network represents a map, this program finds the shortest route from one city to another.
This example is based on pps. 51 -- 53 in Paul Graham, ANSI COMMON LISP, Prentice-Hall 1996. The following explanation is paraphrased from Graham.
A network is represented by an association list, where the first element of each sublist is a node and the rest of each sublist is the list of nodes which are adjacent to the first node.
Path-demo is the driver that prompts for the file name
that contains the network, the starting node, and the ending node.
Shortest-path takes a start node, a destination node,
and a network, and returns the shortest path, if there is one.
The program works by searching the network breadth-first. You have to maintain a queue of unexplored nodes. Each time you get to a node, you check to see if it is the one you want. If not, you append each of its neighbors to the end of the queue, then take a node from the front of the queue and continue the search there.
The code represents a slight complication of this idea. We don't just want to find the destination, but to keep a record of how we got there. So instead of maintaining a queue of nodes, we maintain a queue of the paths we've followed.
The function bfs does the searching. Initially
shortest-path calls bfs with one element in
the queue, a path representing the start node with no history.
If the queue is empty, bfs returns the empty list to
indicate that no path could be found. If there are still nodes to
search, bfs looks at the element on the front of the
queue. If the car is the node we're looking for, we've
found a path and we just return it, reversing it for readability.
If we haven't found the node we're looking for, we add each of the
current node's neighbors to the end of the queue. Then we call
bfs recursively to continue searching the rest of the queue.
By always putting deeper nodes at the end of the queue, we ensure that the network gets searched one layer at a time. Because we search breadth-first, the first path we find will be the shortest, or one of the shortest.
This is not the fastest way to search a network, but it does demonstrate the versatility of lists. We use a list of nodes to represent a path, a list of paths to represent the queue used in the search, and an association list to represent the network itself.
Here is the code. A network follows.
(define (path-demo)
(display "File name: ")
(let ((fname (read-string)))
(let ((infile (open-input-file fname)))
(let ((routes (read infile)))
(display "Start: ")
(let ((start (read-string)))
(display "Finish: ")
(let ((finish (read-string)))
(for-each (lambda (x) (display x) (display " "))
(cons "Route:" (shortest-path start finish routes)))))))))
(define (shortest-path start end net)
(bfs end (list (list start)) net))
;; Breadth-first search
(define (bfs end queue net)
(print queue) (newline) (newline) ; entertainment
(if (null? queue)
'()
(let ((path (car queue)))
(let ((node (car path)))
(if (equal? node end) ;; Graham used CL eql
(reverse path)
(bfs end
(append (cdr queue)
(new-paths path node net))
net))))))
(define (new-paths path node net)
(map (lambda (n) (cons n path)) (cdr (assoc node net))))
Here is a sample network that represents a map of cities around Puget Sound. On my
system it is stored in C:\scheme\puget-cities.txt. Nodes
are represented by quoted strings to handle cities like Gig Harbor
whose names include more than one word.
(("Bremerton" "Seattle" "Gig Harbor")
("Gig Harbor" "Bremerton" "Tacoma" "Olympia")
("Olympia" "Gig Harbor" "Tacoma")
("Tacoma" "Olympia" "Gig Harbor" "Seattle")
("Seattle" "Bremerton" "Tacoma"))
To run the demo execute (path-demo) then answer the
prompts asking for the map file name, the starting node and the ending
node.
Here is a sample program run.
(path-demo) File name: C:\scheme\puget-cities.txt Start: Seattle Finish: Olympia ... intermediate results print out ... Route: Seattle Tacoma Olympia