;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;       Prim's algorithm for finding the minimum spanning tree (MST)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(defvar *cost-mst* 0)

(define (prim G)
  (clear-graphics!)
  (for-each (draw-vertex G) (V G))
  (mst! G '())
  (let* ((i (nth (+ 1 (random (n G))) (V G)))          ; select a random vertex
	 (U (list i))(V-U (remove i (V G)))
	 (v' nil))
    (do ((edge (get-lowest-cost-edge G U V-U) (get-lowest-cost-edge G U V-U)))
	((or (null? edge) (null? V-U)))
      ((draw-edge G) edge)
      (set! v' (second edge))
      (mst! G (cons edge (mst G)))
      (set! U (cons v' U))
      (set! V-U (remove v' V-U)))))
;;;
;;; G is the graph with n vertices, 
;;; Prim's algorithm delivers the minimum spanning tree MST in G.
;;;
;;; NOTE: remember that we may see a mst on an INCOMPLETE graph
;;;       and its drawing will look a bit odd! To get a mst that you
;;;       can draw and is pleasing/meaningful make sure graph is complete
;;;


(define (get-lowest-cost-edge G U' V')
  (let ((closest -1) (closest-d *max*)
	(u nil) (v nil) (edge '()) (d nil))
    (do ((lu U' (cdr lu)))
	((null? lu) edge)
      (do ((lv V' (cdr lv)))
	  ((null? lv))
	(set! u (car lu))
	(set! v (car lv))
	(set! d (array-ref (C G) (list u v)))
	(cond ((< d closest-d)
	       (set! closest-d d)
	       (set! edge (list u v))))))))
;;;
;;; Get the lowest cost edge (u,v) in G such
;;; that u is in U' and v is in V', and (array-ref (C G) (list u v))
;;; is minimum, where (C G) is an n x n cost matrix
;;;

(define (prim-demo n)
  (prim (make-random-graph n 1.0)))

(print "

*****************************************************************
For a demo of Prim's algorithm call function (prim-demo n)
Where n is the number of vertices in a graph. The demo
will produce a random graph with n vertices, edge probability 1
(ie. a complete graph). The algorithm will then compute the
minimum spanning tree (MST) of G using Prim's algorithm.
The progress of the algorithm will be displayed graphically, 
you will see the MST growing. Try n equal to about 30 initially,
and don't go over n equal to 100 (life is too short). 
Note that a large amount of the time is associated with 
creating the graph, so be patient.
*****************************************************************

")