(require :cl-graph)
(in-package :cl-graph)
(load "Graph.lisp")

(defun traveling-salesman-problem (graph)
  (let ((V '()))
    (iterate-vertexes graph #'(lambda (x)
				(push x V)))
;    (dotimes (i 500)
 ;     (rotatef (elt V (random 128)) (elt V (random 128))))
    (let ((min-tour (copy-list V)) (cur nil))
      (print (calculate-tour-cost graph min-tour))
      (while (< (calculate-tour-cost graph (setf cur (find-min-in-neigh graph min-tour)))
		(calculate-tour-cost graph min-tour))
	(print "test")
	(setf min-tour cur))
      (format t "Tour~a~%Cost:~a~%" min-tour (calculate-tour-cost graph min-tour)))))

(defun find-min-in-neigh (graph cur-best)
  (let ((min-tour-2 cur-best)
	(min-cost (calculate-tour-cost graph cur-best)))
    (loop for i from 0 to (- (length cur-best) 2) do
	  (loop for j from (1+ i) to (1- (length cur-best)) do
		(rotatef (elt min-tour-2 i) (elt min-tour-2 j))
		(if (< (calculate-tour-cost graph min-tour-2) min-cost)
		    (setf min-cost (calculate-tour-cost graph cur-best))
		    (rotatef (elt min-tour-2 i) (elt min-tour-2 j)))))
    (print (calculate-tour-cost graph min-tour-2))
    min-tour-2))