ref: 000ebc50785c5c066465fc17668ae64975188d04
parent: 4408476b7584b9a316466fe1bd10867103cddf57
author: Simon Tatham <anakin@pobox.com>
date: Sun Apr 22 09:48:07 EDT 2018
Use the new matching() for latin.c. The new client code is a lot smaller and nicer, because we can throw away the col[] and num[] permutations entirely. Of course, this also means that every puzzle that incorporated latin.c now has to link against matching.c instead of maxflow.c - but since I centralised that secondary dependency into Recipe a few commits ago, it's trivial to switch them all over at once.
--- a/Recipe
+++ b/Recipe
@@ -31,7 +31,7 @@
ALL = list
-LATIN_DEPS = maxflow tree234
+LATIN_DEPS = matching tree234
LATIN = latin LATIN_DEPS
LATIN_SOLVER = latin[STANDALONE_SOLVER] LATIN_DEPS
--- a/latin.c
+++ b/latin.c
@@ -4,7 +4,7 @@
#include "puzzles.h"
#include "tree234.h"
-#include "maxflow.h"
+#include "matching.h"
#ifdef STANDALONE_LATIN_TEST
#define STANDALONE_SOLVER
@@ -1111,11 +1111,11 @@
digit *latin_generate(int o, random_state *rs)
{digit *sq;
- int *edges, *backedges, *capacity, *flow;
+ int *adjdata, *adjsizes, *matching;
+ int **adjlists;
void *scratch;
- int ne, scratchsize;
int i, j, k;
- digit *row, *col, *numinv, *num;
+ digit *row;
/*
* To efficiently generate a latin square in such a way that
@@ -1128,123 +1128,76 @@
* the theorem guarantees that we will never have to backtrack.
*
* To find a viable row at each stage, we can make use of the
- * support functions in maxflow.c.
+ * support functions in matching.c.
*/
sq = snewn(o*o, digit);
/*
- * In case this method of generation introduces a really subtle
- * top-to-bottom directional bias, we'll generate the rows in
- * random order.
+ * matching.c will take care of randomising the generation of each
+ * row of the square, but in case this entire method of generation
+ * introduces a really subtle top-to-bottom directional bias,
+ * we'll also generate the rows themselves in random order.
*/
row = snewn(o, digit);
- col = snewn(o, digit);
- numinv = snewn(o, digit);
- num = snewn(o, digit);
for (i = 0; i < o; i++)
row[i] = i;
shuffle(row, i, sizeof(*row), rs);
/*
- * Set up the infrastructure for the maxflow algorithm.
+ * Set up the infrastructure for the matching subroutine.
*/
- scratchsize = maxflow_scratch_size(o * 2 + 2);
- scratch = smalloc(scratchsize);
- backedges = snewn(o*o + 2*o, int);
- edges = snewn((o*o + 2*o) * 2, int);
- capacity = snewn(o*o + 2*o, int);
- flow = snewn(o*o + 2*o, int);
- /* Set up the edge array, and the initial capacities. */
- ne = 0;
- for (i = 0; i < o; i++) {- /* Each LHS vertex is connected to all RHS vertices. */
- for (j = 0; j < o; j++) {- edges[ne*2] = i;
- edges[ne*2+1] = j+o;
- /* capacity for this edge is set later on */
- ne++;
- }
- }
- for (i = 0; i < o; i++) {- /* Each RHS vertex is connected to the distinguished sink vertex. */
- edges[ne*2] = i+o;
- edges[ne*2+1] = o*2+1;
- capacity[ne] = 1;
- ne++;
- }
- for (i = 0; i < o; i++) {- /* And the distinguished source vertex connects to each LHS vertex. */
- edges[ne*2] = o*2;
- edges[ne*2+1] = i;
- capacity[ne] = 1;
- ne++;
- }
- assert(ne == o*o + 2*o);
- /* Now set up backedges. */
- maxflow_setup_backedges(ne, edges, backedges);
-
+ scratch = smalloc(matching_scratch_size(o, o));
+ adjdata = snewn(o*o, int);
+ adjlists = snewn(o, int *);
+ adjsizes = snewn(o, int);
+ matching = snewn(o, int);
+
/*
* Now generate each row of the latin square.
*/
for (i = 0; i < o; i++) {- /*
- * To prevent maxflow from behaving deterministically, we
- * separately permute the columns and the digits for the
- * purposes of the algorithm, differently for every row.
- */
- for (j = 0; j < o; j++)
- col[j] = num[j] = j;
- shuffle(col, j, sizeof(*col), rs);
- shuffle(num, j, sizeof(*num), rs);
- /* We need the num permutation in both forward and inverse forms. */
- for (j = 0; j < o; j++)
- numinv[num[j]] = j;
+ /*
+ * Make adjacency lists for a bipartite graph joining each
+ * column to all the numbers not yet placed in that column.
+ */
+ for (j = 0; j < o; j++) {+ int *p, *adj = adjdata + j*o;
+ for (k = 0; k < o; k++)
+ adj[k] = 1;
+ for (k = 0; k < i; k++)
+ adj[sq[row[k]*o + j] - 1] = 0;
+ adjlists[j] = p = adj;
+ for (k = 0; k < o; k++)
+ if (adj[k])
+ *p++ = k;
+ adjsizes[j] = p - adjlists[j];
+ *p = -1;
+ }
/*
- * Set up the capacities for the maxflow run, by examining
- * the existing latin square.
+ * Run the matching algorithm.
*/
- for (j = 0; j < o*o; j++)
- capacity[j] = 1;
- for (j = 0; j < i; j++)
- for (k = 0; k < o; k++) {- int n = num[sq[row[j]*o + col[k]] - 1];
- capacity[k*o+n] = 0;
- }
-
- /*
- * Run maxflow.
- */
- j = maxflow_with_scratch(scratch, o*2+2, 2*o, 2*o+1, ne,
- edges, backedges, capacity, flow, NULL);
+ j = matching_with_scratch(scratch, o, o, adjlists, adjsizes,
+ rs, matching, NULL);
assert(j == o); /* by the above theorem, this must have succeeded */
/*
- * And examine the flow array to pick out the new row of
- * the latin square.
+ * And use the output to set up the new row of the latin
+ * square.
*/
- for (j = 0; j < o; j++) {- for (k = 0; k < o; k++) {- if (flow[j*o+k])
- break;
- }
- assert(k < o);
- sq[row[i]*o + col[j]] = numinv[k] + 1;
- }
+ for (j = 0; j < o; j++)
+ sq[row[i]*o + j] = matching[j] + 1;
}
/*
* Done. Free our internal workspaces...
*/
- sfree(flow);
- sfree(capacity);
- sfree(edges);
- sfree(backedges);
+ sfree(matching);
+ sfree(adjlists);
+ sfree(adjsizes);
+ sfree(adjdata);
sfree(scratch);
- sfree(numinv);
- sfree(num);
- sfree(col);
sfree(row);
/*