From 1add03f7b8a502d4453f53f4ea6930d0e71a6bb0 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Wed, 24 Feb 2016 18:57:03 +0000 Subject: 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. --- puzzles.h | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) (limited to 'puzzles.h') 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 -- cgit v1.1