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.

2 files changed, 45 insertions, 92 deletions

diff --git a/Recipe b/Recipe
index 822afb9..fc9bc1b 100644
--- a/Recipe
+++ b/Recipe
@@ -31,7 +31,7 @@ STANDALONE = nullfe random misc malloc
 
 ALL      = list
 
-LATIN_DEPS   = maxflow tree234
+LATIN_DEPS   = matching tree234
 LATIN        = latin LATIN_DEPS
 LATIN_SOLVER = latin[STANDALONE_SOLVER] LATIN_DEPS
 
diff --git a/latin.c b/latin.c
index 716064c..710be2c 100644
--- 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 @@ void latin_debug(digit *sq, int o)
 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 @@ digit *latin_generate(int o, random_state *rs)
      * 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;
-
-	/*
-	 * Set up the capacities for the maxflow run, by examining
-	 * the existing latin square.
-	 */
-	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;
-	    }
+        /*
+         * 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;
+        }
 
 	/*
-	 * Run maxflow.
+	 * Run the matching algorithm.
 	 */
-	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);
 
     /*