New centralised loop-finder, using Tarjan's algorithm.

In the course of another recent project I had occasion to read up on
Tarjan's bridge-finding algorithm. This analyses an arbitrary graph
and finds 'bridges', i.e. edges whose removal would increase the
number of connected components. This is precisely the dual problem to
error-highlighting loops in games like Slant that don't permit them,
because an edge is part of some loop if and only if it is not a
bridge.

Having understood Tarjan's algorithm, it seemed like a good idea to
actually implement it for use in these puzzles, because we've got a
long and dishonourable history of messing up the loop detection in
assorted ways and I thought it would be nice to have an actually
reliable approach without any lurking time bombs. (That history is
chronicled in a long comment at the bottom of the new source file, if
anyone is interested.)

So, findloop.c is a new piece of reusable library code. You run it
over a graph, which you provide in the form of a vertex count and a
callback function to iterate over the neighbours of each vertex, and
it fills in a data structure which you can then query to find out
whether any given edge is part of a loop in the graph or not.

1 files changed, 35 insertions, 0 deletions

diff --git a/puzzles.h b/puzzles.h
index 0d5aeee..1847d9c 100644
--- a/puzzles.h
+++ b/puzzles.h
@@ -468,6 +468,41 @@ void free_combi(combi_ctx *combi);
 int *divvy_rectangle(int w, int h, int k, random_state *rs);
 
 /*
+ * findloop.c
+ */
+struct findloopstate;
+struct findloopstate *findloop_new_state(int nvertices);
+void findloop_free_state(struct findloopstate *);
+/*
+ * Callback provided by the client code to enumerate the graph
+ * vertices joined directly to a given vertex.
+ *
+ * Semantics: if vertex >= 0, return one of its neighbours; if vertex
+ * < 0, return a previously unmentioned neighbour of whatever vertex
+ * was last passed as input. Write to 'ctx' as necessary to store
+ * state. In either case, return < 0 if no such vertex can be found.
+ */
+typedef int (*neighbour_fn_t)(int vertex, void *ctx);
+/*
+ * Actual function to find loops. 'ctx' will be passed unchanged to
+ * the 'neighbour' function to query graph edges. Returns FALSE if no
+ * loop was found, or TRUE if one was.
+ */
+int findloop_run(struct findloopstate *state, int nvertices,
+                 neighbour_fn_t neighbour, void *ctx);
+/*
+ * Query whether an edge is part of a loop, in the output of
+ * find_loops.
+ *
+ * Due to the internal storage format, if you pass u,v which are not
+ * connected at all, the output will be TRUE. (The algorithm actually
+ * stores an exhaustive list of *non*-loop edges, because there are
+ * fewer of those, so really it's querying whether the edge is on that
+ * list.)
+ */
+int findloop_is_loop_edge(struct findloopstate *state, int u, int v);
+
+/*
  * Data structure containing the function calls and data specific
  * to a particular game. This is enclosed in a data structure so
  * that a particular platform can choose, if it wishes, to compile