;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                Random TSP loader ... and other goodies!!
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define *x-coord* nil)  ; x coordinates  (see read-random-tsp)
(define *y-coord* nil)  ; y coordinates
(define *n* 0)          ; number of cities
(define *cost* nil)     ; the cost matrix (see make-cost-matrix)

(define (read-random-tsp n fname)
  (let ((fin (open-input-file fname))
	(y nil) (city nil))
    (set! *x-coord* (make-vector (+ n 1) 0))
    (set! *y-coord* (make-vector (+ n 1) 0))
    (set! *n* n)
    (do ((x (read fin) (read fin)))
	((eof-object? x) (close-input-port fin))
      (set! y (read fin))
      (set! city (read fin))
      (vector-set! *x-coord* city x)
      (vector-set! *y-coord* city y))))
;;;
;;; Given the number of cities and the file name read in a randomly generated tsp
;;; Deliver as a result the two global vectors *x-coord* and *y-coord*
;;;
;;; for example

;(read-random-tsp 100 "/home/s7/pat/scheme/tsp/100.4")


(define (manhattan-distance x1 y1 x2 y2)
  (+ (abs (- x1 x2)) (abs (- y1 y2))))
;;;
;;; Manhattan distance between two points
;;; (x1,y1) and (x2,y2) is as above. That is we assume
;;; we are travelling in a grid, similar to the city
;;; of Manhattan. We can only move up/down and left/right.
;;; No diagonal movement is allowed
;;;

(define (make-cost-matrix)
  (let ((cost 0))
    (set! *cost* (make-matrix (+ 1 *n*) (+ 1 *n*) 0))
    (do ((i 1 (+ i 1))) ((= i *n*))
      (do ((j (+ i 1) (+ j 1))) ((> j *n*))
	(set! cost (manhattan-distance (vector-ref *x-coord* i)
				       (vector-ref *y-coord* i)
				       (vector-ref *x-coord* j)
				       (vector-ref *y-coord* j)))
	(matrix-set! *cost* i j cost)
	(matrix-set! *cost* j i cost)))))
;;;
;;; Set up the cost matrix *cost*
;;; After this function we can get the cost of going
;;; from city_i to city_j as follows
;;;
;;;               (matrix-ref *cost* i j)
;;;
;;;

(define (get-cost i j)
  (matrix-ref *cost* i j))
;;;
;;; get me the cost of going from city i to city j
;;;


(define (randomise l)
  (cond ((null? l) l)
	(#t (let ((e (list-ref l (random (length l)))))
	      (cons e (randomise (remove e l)))))))


(define (tour->gnufile tour fname)
  (let ((n (length tour))
	(start (car tour))
	(fout (open-output-file fname)))
    (do ((i 0 (+ i 1))) ((= i n))
      (let* ((j (list-ref tour i))
	     (x (vector-ref *x-coord* j))
	     (y (vector-ref *y-coord* j)))
	(display (format nil "~S ~S" x y) fout)
	(newline fout)))
    (display (format nil "~S ~S" 
		     (vector-ref *x-coord* start)
		     (vector-ref *y-coord* start)) fout)
    (newline fout)
    (close-output-port fout)))
;;;
;;; Given a tour as a sequence of cities, such as '(1 2 5 6 9 3 ...)
;;; output this as a file of x/y-coordinates such that we can then
;;; use gnuplot to view it. For example, given a tour ...
;;; (define l '(1 6 4 2 9 3 8 ...))
;;; (tour->gnufile l "tour.gnu")
;;;
;;; Then go into gnuplot an do the following
;;; > plot "tour.gnu" with linespoints
;;;

(define (one2n n)
  (cond ((= 0 n) '())
	(#t (cons n (one2n (- n 1))))))
;;;
;;; Suck it and see
;;;


(define (mantour->gnufile tour fname)
  (let ((n (length tour))
	(start (car tour))
	(fout (open-output-file fname)))
    (do ((i 0 (+ i 1))) ((= i (- n 1)))
      (let* ((j (list-ref tour i))
	     (x-j (vector-ref *x-coord* j))
	     (y-j (vector-ref *y-coord* j))
	     (k (list-ref tour (+ i 1)))
	     (x-k (vector-ref *x-coord* k))
	     (y-k (vector-ref *y-coord* k)))
	(display (format nil "~S ~S" x-j y-j) fout)
	(newline fout)
	(display (format nil "~S ~S" x-j y-k) fout)
	(newline fout)
	(display (format nil "~S ~S" x-k y-k) fout)
	(newline fout)))	
    (display (format nil "~S ~S" 
		     (vector-ref *x-coord* start)
		     (vector-ref *y-coord* start)) fout)
    (newline fout)
    (close-output-port fout)))
;;;
;;; Like tour->gnufile but result is a manhattan tour
;;; when you gnuplot it
;;;

;; Graphics Graphics Graphics Graphics Graphics Graphics Graphics Graphics Graphics   

(define (draw-city i)
  (draw-box 2 
	    (quotient (vector-ref *x-coord* i) 2)
	    (quotient (vector-ref *y-coord* i) 2)
	    2))


(define (draw-city-edge edge)
  (let* ((u (first edge))
	 (v (second edge))
	 (xu (quotient (vector-ref *x-coord* u) 2))
	 (yu (quotient (vector-ref *y-coord* u) 2))
	 (xv (quotient (vector-ref *x-coord* v) 2))
	 (yv (quotient (vector-ref *y-coord* v) 2)))
    (draw-line xu yu xv yv 6)))


(define (draw-tour tour)
  (graphics-mode!)
  (clear-graphics!)
  (map draw-city tour)
  (do ((l tour (cdr l))) ((= 1 (length l)))
    (draw-city-edge (list (car l) (car (cdr l))))))
;;;
;;; You can call (draw-tour l) as you are constructing the tour
;;; to see how your technique progresses.
;;;

;;  Graphics Graphics Graphics Graphics Graphics Graphics Graphics Graphics Graphics