;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;        The Single Source Shortest Paths (SSSP) Problem
;
; Given a directed graph G, in which arcs has a non-negative label, and 
; a single vertex called the source, determine the cost of the shortest 
; paths from the source to every other vertex. 
;
; That is if we have n vertices, and G is connected, find the n-1 paths
; to the remaining vertices, where each path is as short as possible.
;
; An algorithm that solves this problem is Dijkstra's algorithm 
; (named after its discoverer/inventor E.W. Dijkstra)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define *trace* #f)

(define (dijkstra Source G)
  (cond (*trace* (print (list 'dijkstra Source))))
  (let* ((S (list Source))                                          ;(1)
	 (V-S (remove Source (V G)))                                ;(2)
	 (D (copy-vector (array-ref (C G) (list Source)) 0 (n G)))  ;(3)
	 (P (make-vector (+ (n G) 1) Source)))                      ;(4)
    (do ((u (nearest-to-source D V-S) (nearest-to-source D V-S)))   ;(5)
	((or (null? u) (null? V-S)) (list P D))                     ;(6)
      (set! S (cons u S))                                           ;(7)
      (set! V-S (remove u V-S))                                     ;(8)
      (do ((w's V-S (cdr w's)))                                     ;(9)
	  ((null? w's))                                             ;(10)
	(let* ((w (first w's))                                      ;(11)
	       (source->u->w (+ (vector-ref D u)
				(array-ref (C G) (list u w)))))     ;(12)
	  (cond ((< source->u->w (vector-ref D w))                  ;(13)
		 (vector-set! D w source->u->w)                     ;(14)
		 (vector-set! P w u))))))))                         ;(15)
;;;
;;; Given a graph G and a source vertex Source, find all shortest paths
;;; from the Source. Deliver as a result the pair (list P D) where
;;; P is a vector representation of the paths, such that (vector-ref P w)
;;; is the immediate Parent of vector w in the path back to Source
;;; and D is a distance vector such that (vector-ref D w) is the length
;;; of the shortest path from Source to vertex w in G.
;;;
;;;
;;;  (1) S is a set of "special" vertices. By "special" we mean that we 
;;;      have already computed the shortest path from the source to all of
;;;      the vertices in S
;;;  (2) V-S is the set of "non-special" vertices, ie the set of vertices 
;;;      that we have not yet found the shortest path from the Source
;;;      to the vertices in V-S (read it as V minus S)
;;;  (3) D is vector, such that (vector-ref D w) is the distance from the
;;;      Source to w, and this vector is updated conditionally in step (14)
;;;      Initially D is a row in the cost matrix (C G) (read that as C of G)
;;;      in particular the Source row (array-ref (C G) (list Source))
;;;  (4) P is a vector representation of the shortest paths. 
;;;      (vector-ref D w) is the immediate parent of vertex w in that path
;;;  (5) Outer loop of algorithm. Let u be the vertex V-S that is closest 
;;;      to the Source, and ...
;;;  (6) ... terminate outer loop when either there is no vertex in V-S 
;;;      close to Source (ie at a cost less than *max*) or all vertices
;;;      in (V G) are now in S (consequently V-S is the empty set)
;;;  (7) vertex u is the vertex that is closest to the Source, so add u
;;;      to the set of special vertices S and ...
;;;  (8) ... remove u from the set of non-special vertices V-S
;;;  (9) Inner loop, now update the distance vector D, such that we ask
;;;      "Is there a shorter path from the source to w via u 
;;;       (ie. source->u->w) than going direct from source to w?"
;;;      We start the loop by looking at each vertex w in V-S, so initialise
;;;      the set of vertices w's to be V-S and every time round the loop
;;;      make the set w's be the rest of the set of w's and ...
;;; (10) ... terminate the loop when we have exhausted the set of w's
;;; (11) w is the first edge in the (ever reducing) set w's and ...
;;; (12) source->u->w is the cost of going from the Source to u and then
;;;      from u to w. That cost is then (vector-ref D u) plus 
;;;      (array-ref (C G) (list u w))
;;; (13) If the cost of going source->u->w is less than the cost of going
;;;      from source->w then we update the cost vector ...
;;; (14) ... such that the cost of the path from Source to w is the cost 
;;;      of the path that goes from source->u->w and ...
;;; (15) ... the parent of w is then u
;;;
				 

(define (nearest-to-source D V)
  (cond (*trace* (print (list 'nearest-to-source D V))))
  (let ((u nil) (nearest-u '())
	(nearest *max*) (distance-to-u 0))
    (do ((u's V (cdr u's)))
	((null? u's) nearest-u)
      (set! u (first u's))
      (set! distance-to-u (vector-ref D u))
      (cond ((< distance-to-u nearest)
	     (set! nearest-u u)
	     (set! nearest distance-to-u))))))
;;;
;;; D is a vector of distances from a source vertex,
;;; such that the distance of vertex u from the source is
;;; (vector-ref D u)
;;;
;;; V is a set of vertices (none of which is the source)
;;;
;;; The function delivers a vertex u in V that is nearest 
;;; to the source (ie. nearest-u), using the distances in D.
;;;
;;; NOTE: if all vertices in V are not reachable from the source
;;; vertex, then for all u in V, (= *max* (vector-ref D u)), and
;;; the function delivers '() as a result ie. the closest vertex in V
;;; to the source is none!
;;;


;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
;
;                     Shortest Path Demo
;
;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(define (get-path-from i k P)
  (cond (*trace* (print (list 'get-path-from i k P))))
  (define (get-path' i k vertices edges)
    (cond ((= i k) (list vertices edges))
	  (else (let ((j (vector-ref P k)))
		  (get-path' i j (cons j vertices) (cons (list j k) edges))))))
  (get-path' i k (list k) '()))
;;;
;;; Given a vector P where (vector-ref P k) is the immediate
;;; predecessor of vertex k in the path from i to k, deliver 
;;; the path from i to k as a sequence of vertices and a set of edges
;;; 


(define (shortest-path u w G)
  (let* ((pair (dijkstra u G))
	 (P (first pair))
	 (D (second pair))
	 (V&E (get-path-from u w P))
	 (cost (vector-ref D w)))
    (list (first V&E) (second V&E) cost)))
;;;
;;; Given graph G get the shortest path from vertex u to vertex w
;;; This uses Dijkstra's algorithm, and consequently computes single source
;;; shortest paths, giving in total n-1 paths. Of these we are interested
;;; in only the one where u is source and w is destination
;;;
;;; Delivers as a result a triple (list vertices edges cost)
;;; where vertices is the list of vertices on the path u to w
;;;       edges is the set of edges in the path u to w
;;;       cost is the cost of the shortest path u to w in G
;;;


(define (draw-shortest-path u w G)
  (draw-graph G)
  (for-each (draw-vertex G) (V G))
  (let ((triple (shortest-path u w G)))
    (for-each (draw-special-vertex G) (first triple))
    (for-each (draw-special-edge G) (second triple))
    triple))


(define (demo n p)
  (let ((G (make-random-graph n p)))
    (do ((source 1 (+ source 1)))
	((= source n))
      (let* ((pair (dijkstra source G))
	     (P (first pair))
	     (D (second pair)))
	(draw-graph G)
	(read-char)
	(do ((u (+ source 1) (+ u 1)))
	    ((> u n))
	  (let* ((pair (get-path-from source u P))
		 (vertices (first pair))
		 (edges (second pair)))
	    (for-each (draw-special-vertex G) vertices)
	    (for-each (draw-special-edge G) edges)
	    (display (format nil
			     "From ~S to ~S, path ~S,  cost = ~S"
			     source u vertices (vector-ref D u)))
	    (read-char)
	    (for-each (undraw-special-vertex G) vertices)
	    (for-each (undraw-special-edge G) edges)))))))
	    
;;;
;;; Make a random graph G with n vertices, probability of edge (i j) is p
;;; Compute shortest path from i to j in G, for all i and all j where i<j
;;; Hit carriage return to get next i and j
;;;   

(print
 "

************************************************************************
  You can run a wee demo using function (demo n p). This
  will create a graph with n vertices, and the probability of an
  edge existing between i and j (for all i and j) is p. So if p = 1
  we have the clique (complete graph) and if p = 0 we have the null graph 
  (with no edges). The demo will then call dijkstra's algorithm
  on the graph, computing the shortest paths from the source, and
  these will in turn be displayed and printed out
************************************************************************


")