From f940276fd9bc38ae34d4119fd1d983171a627400 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Wed, 15 May 2019 18:16:27 -0400 Subject: puzzles: resync with upstream This brings the puzzles source to upstream commit e2135d5. (I've made my own changes on top of that.) This brings in a couple bugfixes and a new solver for Dominosa. Change-Id: I11d46b43171787832330a5e2e0d2f353f36f727d --- apps/plugins/puzzles/src/puzzles.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'apps/plugins/puzzles/src/puzzles.h') diff --git a/apps/plugins/puzzles/src/puzzles.h b/apps/plugins/puzzles/src/puzzles.h index 48d3d83b6e..1732abe3e9 100644 --- a/apps/plugins/puzzles/src/puzzles.h +++ b/apps/plugins/puzzles/src/puzzles.h @@ -594,6 +594,32 @@ bool findloop_run(struct findloopstate *state, int nvertices, */ bool findloop_is_loop_edge(struct findloopstate *state, int u, int v); +/* + * Alternative query function, which returns true if the u-v edge is a + * _bridge_, i.e. a non-loop edge, i.e. an edge whose removal would + * disconnect a currently connected component of the graph. + * + * If the return value is true, then the numbers of vertices that + * would be in the new components containing u and v are written into + * u_vertices and v_vertices respectively. + */ +bool findloop_is_bridge( + struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices); + +/* + * Helper function to sort an array. Differs from standard qsort in + * that it takes a context parameter that is passed to the compare + * function. + * + * I wrap it in a macro so that you only need to give the element + * count of the array. The element size is determined by sizeof. + */ +typedef int (*arraysort_cmpfn_t)(const void *av, const void *bv, void *ctx); +void arraysort_fn(void *array, size_t nmemb, size_t size, + arraysort_cmpfn_t cmp, void *ctx); +#define arraysort(array, nmemb, cmp, ctx) \ + arraysort_fn(array, nmemb, sizeof(*(array)), cmp, ctx) + /* * Data structure containing the function calls and data specific * to a particular game. This is enclosed in a data structure so -- cgit v1.2.3