/* -*-c-*-
*
- * $Id: graph.c,v 1.1 2003/03/07 00:45:13 mdw Exp $
+ * $Id: graph.c,v 1.3 2003/03/10 23:37:21 mdw Exp $
*
* Graph theory stuff
*
/*----- Revision history --------------------------------------------------*
*
* $Log: graph.c,v $
+ * Revision 1.3 2003/03/10 23:37:21 mdw
+ * Fix single point TSP.
+ *
+ * Revision 1.2 2003/03/08 00:40:32 mdw
+ * Fix unsigned crapness in travelling-salesman solver.
+ *
* Revision 1.1 2003/03/07 00:45:13 mdw
* Graph theory functions.
*
* -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.
*
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;
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]];
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));
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) {
}
}
+#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 &&