Add elite-tantalus. Add a developer guide.

[rocl] / graph.c

diff --git a/graph.c b/graph.c
index 0f9fa8435e399c666a2010644a8584bdfc5f26b8..23c1a326710975da5dc9d625fd9f1bf06daddb7b 100644 (file)
--- a/graph.c
+++ b/graph.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: graph.c,v 1.1 2003/03/07 00:45:13 mdw Exp $
+ * $Id$
  *
  * Graph theory stuff
  *
@@ -24,14 +24,6 @@
  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: graph.c,v $
- * Revision 1.1  2003/03/07 00:45:13  mdw
- * Graph theory functions.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include <assert.h>
@@ -252,7 +244,7 @@ static size_t rrange(size_t max)
  * -inner COUNT                Perform COUNT loops each cooling cycle.  Default is
  *                     10000.
  *
- * -init TEMP          Set the initial temperature to TEMP.  Default is not
+ * -temp TEMP          Set the initial temperature to TEMP.  Default is not
  *                     very helpful.  Initial setting should be well above
  *                     the maximum cost increase from a cycle.
  *
@@ -301,7 +293,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
        err(ti, "cooling factor must be > 1");
        goto done;
       }
-    } else if (strcmp(p, "-init") == 0) {
+    } else if (strcmp(p, "-temp") == 0) {
       i++; if (i >= objc) goto args;
       if (Tcl_GetDoubleFromObj(ti, objv[i], &temp) != TCL_OK)
        goto done;
@@ -372,7 +364,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
 
   if (nn <= 2) {
     memcpy(r_best, r, nn * sizeof(*r));
-    if (n == 1)
+    if (nn == 1)
       c_best = a[r[0] * n + r[0]];
     else
       c_best = a[r[0] * n + r[1]];
@@ -406,7 +398,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
     i--;
   }
 
-/*   printf("*** initial cost = %lu\n", c_best); */
+/*   printf("*** initial cost = %lu; n = %u; nn = %u\n", c, n, nn); */
   c_curr = c_best = c;
   memcpy(r_best, r, nn * sizeof(*r));
 
@@ -443,8 +435,8 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
       if (i == j)
        continue; /* No change */
       if (j < i) { t = i; i = j; j = t; }
-      ilo = (i - 1) % nn; ihi = (i + 1) % nn;
-      jlo = (j - 1) % nn; jhi = (j + 1) % nn;
+      ilo = (i + nn - 1) % nn; ihi = (i + 1) % nn;
+      jlo = (j + nn - 1) % nn; jhi = (j + 1) % nn;
 
       c = c_curr;
       if (j == nn - 1) {
@@ -506,6 +498,29 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
        }
       }
 
+#ifdef PARANOID_CHECKING /* Turn this on to check the shortcut */
+      {
+       unsigned long cc;
+       size_t ii, jj;
+       if (cycle) { jj = 0; ii = nn - 1; }
+       else { jj = nn - 1; ii = jj - 1; }
+       cc = 0;
+       t = r[i]; r[i] = r[j]; r[j] = t;
+       for (;;) {
+         cc += a[r[ii] * n + r[jj]];
+         if (!ii)
+           break;
+         jj = ii;
+         ii--;
+       }
+       t = r[i]; r[i] = r[j]; r[j] = t;
+       if (c != cc) {
+         printf("i = %u; j = %u; c = %lu; cc = %lu\n", i, j, c, cc);
+         abort();
+       }
+      }
+#endif
+
       /* --- Decide what to do --- */
 
       if (c > c_curr &&