;;; graph data

(defstruct simple-graph nodes edges)

(defmethod nodes ((graph simple-graph))
  (loop for (i x y) in (simple-graph-nodes graph)
	collect (1- (the fixnum i))))

(defmethod edges ((graph simple-graph))
  (loop for (from to dist) in (simple-graph-edges graph)
	collect (list (1- (the fixnum from)) (1- (the fixnum to)) dist)
	collect (list (1- (the fixnum to)) (1- (the fixnum from)) dist)))

(defmethod outgoing (graph node)
  (loop for (from to dist) in (edges graph)
	when (eq from node)
	  collect to))

(defmethod incoming (graph node)
  (loop for (from to dist) in (edges graph)
	when (eq from node)
	  collect to))

(defmethod distance (graph a b)
  (loop for (from to dist) in (edges graph)
	when (and (eq from a)
		  (eq to b))
	  return dist))

(defun make-graph (nodes edges)
  (make-simple-graph :nodes nodes :edges edges))

(defvar *ulysseus-16*
  (make-graph
   '((1 38.24 20.42) (2 39.57 26.15) (3 40.56 25.32) (4 36.26 23.12) (5 33.48 10.54)
     (6 37.56 12.19) (7 38.42 13.11) (8 37.52 20.44) (9 41.23 9.10) (10 41.17 13.05)
     (11 36.08 -5.21) (12 38.47 15.13) (13 38.15 15.35) (14 37.51 15.17) (15 35.49 14.32)
     (16 39.36 19.56))
   '((1 2 509) (1 3 501) (1 4 312) (1 5 1019) (1 6 736) (1 7 656) (1 8 60)
     (1 9 1039) (1 10 726) (1 11 2314) (1 12 479) (1 13 448) (1 14 479) (1 15 619)
     (1 16 150) (2 3 126) (2 4 474) (2 5 1526) (2 6 1226) (2 7 1133) (2 8 532)
     (2 9 1449) (2 10 1122) (2 11 2789) (2 12 958) (2 13 941) (2 14 978) (2 15 1127)
     (2 16 542) (3 4 541) (3 5 1516) (3 6 1184) (3 7 1084) (3 8 536) (3 9 1371)
     (3 10 1045) (3 11 2728) (3 12 913) (3 13 904) (3 14 946) (3 15 1115) (3 16 499)
     (4 5 1157) (4 6 980) (4 7 919) (4 8 271) (4 9 1333) (4 10 1029) (4 11 2553)
     (4 12 751) (4 13 704) (4 14 720) (4 15 783) (4 16 455) (5 6 478) (5 7 583)
     (5 8 996) (5 9 858) (5 10 855) (5 11 1504) (5 12 677) (5 13 651) (5 14 600)
     (5 15 401) (5 16 1033) (6 7 115) (6 8 740) (6 9 470) (6 10 379) (6 11 1581)
     (6 12 271) (6 13 289) (6 14 261) (6 15 308) (6 16 687) (7 8 667) (7 9 455)
     (7 10 288) (7 11 1661) (7 12 177) (7 13 216) (7 14 207) (7 15 343) (7 16 592)
     (8 9 1066) (8 10 759) (8 11 2320) (8 12 493) (8 13 454) (8 14 479) (8 15 598)
     (8 16 206) (9 10 328) (9 11 1387) (9 12 591) (9 13 650) (9 14 656) (9 15 776)
     (9 16 933) (10 11 1697) (10 12 333) (10 13 400) (10 14 427) (10 15 622) (10 16 610)
     (11 12 1838) (11 13 1868) (11 14 1841) (11 15 1789) (11 16 2248) (12 13 68) (12 14 105)
     (12 15 336) (12 16 417) (13 14 52) (13 15 287) (13 16 406) (14 15 237) (14 16 449)
     (15 16 636))))

(defvar *ulysseus-22*
  (make-graph
   '((1 38.24 20.42) (2 39.57 26.15) (3 40.56 25.32) (4 36.26 23.12) (5 33.48 10.54)
     (6 37.56 12.19) (7 38.42 13.11) (8 37.52 20.44) (9 41.23 9.10) (10 41.17 13.05)
     (11 36.08 -5.21) (12 38.47 15.13) (13 38.15 15.35) (14 37.51 15.17) (15 35.49 14.32)
     (16 39.36 19.56) (17 38.09 24.36) (18 36.09 23.00) (19 40.44 13.57) (20 40.33 14.15)
     (21 40.37 14.23) (22 37.57 22.56))
   '((1 2 509) (1 3 501) (1 4 312) (1 5 1019) (1 6 736) (1 7 656) (1 8 60)
     (1 9 1039) (1 10 726) (1 11 2314) (1 12 479) (1 13 448) (1 14 479) (1 15 619)
     (1 16 150) (1 17 342) (1 18 323) (1 19 635) (1 20 604) (1 21 596) (1 22 202)
     (2 3 126) (2 4 474) (2 5 1526) (2 6 1226) (2 7 1133) (2 8 532) (2 9 1449)
     (2 10 1122) (2 11 2789) (2 12 958) (2 13 941) (2 14 978) (2 15 1127) (2 16 542)
     (2 17 246) (2 18 510) (2 19 1047) (2 20 1021) (2 21 1010) (2 22 364) (3 4 541)
     (3 5 1516) (3 6 1184) (3 7 1084) (3 8 536) (3 9 1371) (3 10 1045) (3 11 2728)
     (3 12 913) (3 13 904) (3 14 946) (3 15 1115) (3 16 499) (3 17 321) (3 18 577)
     (3 19 976) (3 20 952) (3 21 941) (3 22 401) (4 5 1157) (4 6 980) (4 7 919)
     (4 8 271) (4 9 1333) (4 10 1029) (4 11 2553) (4 12 751) (4 13 704) (4 14 720)
     (4 15 783) (4 16 455) (4 17 228) (4 18 37) (4 19 936) (4 20 904) (4 21 898)
     (4 22 171) (5 6 478) (5 7 583) (5 8 996) (5 9 858) (5 10 855) (5 11 1504)
     (5 12 677) (5 13 651) (5 14 600) (5 15 401) (5 16 1033) (5 17 1325) (5 18 1134)
     (5 19 818) (5 20 808) (5 21 820) (5 22 1179) (6 7 115) (6 8 740) (6 9 470)
     (6 10 379) (6 11 1581) (6 12 271) (6 13 289) (6 14 261) (6 15 308) (6 16 687)
     (6 17 1077) (6 18 970) (6 19 342) (6 20 336) (6 21 348) (6 22 932) (7 8 667)
     (7 9 455) (7 10 288) (7 11 1661) (7 12 177) (7 13 216) (7 14 207) (7 15 343)
     (7 16 592) (7 17 997) (7 18 913) (7 19 236) (7 20 226) (7 21 237) (7 22 856)
     (8 9 1066) (8 10 759) (8 11 2320) (8 12 493) (8 13 454) (8 14 479) (8 15 598)
     (8 16 206) (8 17 341) (8 18 278) (8 19 666) (8 20 634) (8 21 628) (8 22 194)
     (9 10 328) (9 11 1387) (9 12 591) (9 13 650) (9 14 656) (9 15 776) (9 16 933)
     (9 17 1367) (9 18 1333) (9 19 408) (9 20 438) (9 21 447) (9 22 1239) (10 11 1697)
     (10 12 333) (10 13 400) (10 14 427) (10 15 622) (10 16 610) (10 17 1046) (10 18 1033)
     (10 19 96) (10 20 128) (10 21 133) (10 22 922) (11 12 1838) (11 13 1868) (11 14 1841)
     (11 15 1789) (11 16 2248) (11 17 2656) (11 18 2540) (11 19 1755) (11 20 1777) (11 21 1789)
     (11 22 2512) (12 13 68) (12 14 105) (12 15 336) (12 16 417) (12 17 821) (12 18 748)
     (12 19 243) (12 20 214) (12 21 217) (12 22 680) (13 14 52) (13 15 287) (13 16 406)
     (13 17 789) (13 18 698) (13 19 311) (13 20 281) (13 21 283) (13 22 645) (14 15 237)
     (14 16 449) (14 17 818) (14 18 712) (14 19 341) (14 20 314) (14 21 318) (14 22 672)
     (15 16 636) (15 17 932) (15 18 764) (15 19 550) (15 20 528) (15 21 535) (15 22 785)
     (16 17 436) (16 18 470) (16 19 525) (16 20 496) (16 21 486) (16 22 319) (17 18 265)
     (17 19 959) (17 20 930) (17 21 921) (17 22 148) (18 19 939) (18 20 907) (18 21 901)
     (18 22 201) (19 20 33) (19 21 39) (19 22 833) (20 21 14) (20 22 803) (21 22 794))))

(defun counter (n &optional logger)
  (lambda (&rest args)
    (when logger
      (apply logger args))
    (>= 0 (decf n))))

(defun path-length (graph)
  (lambda (path)
    (+ (loop for (i j) on (reverse path)
	     when (and i j)
	       sum (distance graph i j))
       (distance graph (first path) (first (last path))))))