From 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sun, 20 Nov 2016 15:16:41 -0500 Subject: Port of Simon Tatham's Puzzle Collection Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9 MIT Licensed. Some games still crash and others are unplayable due to issues with controls. Still need a "real" polygon filling algorithm. Currently builds one plugin per puzzle (about 40 in total, around 100K each on ARM), but can easily be made to build a single monolithic overlay (800K or so on ARM). The following games are at least partially broken for various reasons, and have been disabled on this commit: Cube: failed assertion with "Icosahedron" setting Keen: input issues Mines: weird stuff happens on target Palisade: input issues Solo: input issues, occasional crash on target Towers: input issues Undead: input issues Unequal: input and drawing issues (concave polys) Untangle: input issues Features left to do: - In-game help system - Figure out the weird bugs Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368 --- apps/plugins/puzzles/maxflow.h | 95 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 95 insertions(+) create mode 100644 apps/plugins/puzzles/maxflow.h (limited to 'apps/plugins/puzzles/maxflow.h') diff --git a/apps/plugins/puzzles/maxflow.h b/apps/plugins/puzzles/maxflow.h new file mode 100644 index 0000000000..d490f45421 --- /dev/null +++ b/apps/plugins/puzzles/maxflow.h @@ -0,0 +1,95 @@ +/* + * Edmonds-Karp algorithm for finding a maximum flow and minimum + * cut in a network. Almost identical to the Ford-Fulkerson + * algorithm, but apparently using breadth-first search to find the + * _shortest_ augmenting path is a good way to guarantee + * termination and ensure the time complexity is not dependent on + * the actual value of the maximum flow. I don't understand why + * that should be, but it's claimed on the Internet that it's been + * proved, and that's good enough for me. I prefer BFS to DFS + * anyway :-) + */ + +#ifndef MAXFLOW_MAXFLOW_H +#define MAXFLOW_MAXFLOW_H + +/* + * The actual algorithm. + * + * Inputs: + * + * - `scratch' is previously allocated scratch space of a size + * previously determined by calling `maxflow_scratch_size'. + * + * - `nv' is the number of vertices. Vertices are assumed to be + * numbered from 0 to nv-1. + * + * - `source' and `sink' are the distinguished source and sink + * vertices. + * + * - `ne' is the number of edges in the graph. + * + * - `edges' is an array of 2*ne integers, giving a (source, dest) + * pair for each network edge. Edge pairs are expected to be + * sorted in lexicographic order. + * + * - `backedges' is an array of `ne' integers, each a distinct + * index into `edges'. The edges in `edges', if permuted as + * specified by this array, should end up sorted in the _other_ + * lexicographic order, i.e. dest taking priority over source. + * + * - `capacity' is an array of `ne' integers, giving a maximum + * flow capacity for each edge. A negative value is taken to + * indicate unlimited capacity on that edge, but note that there + * may not be any unlimited-capacity _path_ from source to sink + * or an assertion will be failed. + * + * Output: + * + * - `flow' must be non-NULL. It is an array of `ne' integers, + * each giving the final flow along each edge. + * + * - `cut' may be NULL. If non-NULL, it is an array of `nv' + * integers, which will be set to zero or one on output, in such + * a way that: + * + the set of zero vertices includes the source + * + the set of one vertices includes the sink + * + the maximum flow capacity between the zero and one vertex + * sets is achieved (i.e. all edges from a zero vertex to a + * one vertex are at full capacity, while all edges from a + * one vertex to a zero vertex have no flow at all). + * + * - the returned value from the function is the total flow + * achieved. + */ +int maxflow_with_scratch(void *scratch, int nv, int source, int sink, + int ne, const int *edges, const int *backedges, + const int *capacity, int *flow, int *cut); + +/* + * The above function expects its `scratch' and `backedges' + * parameters to have already been set up. This allows you to set + * them up once and use them in multiple invocates of the + * algorithm. Now I provide functions to actually do the setting + * up. + */ +int maxflow_scratch_size(int nv); +void maxflow_setup_backedges(int ne, const int *edges, int *backedges); + +/* + * Simplified version of the above function. All parameters are the + * same, except that `scratch' and `backedges' are constructed + * internally. This is the simplest way to call the algorithm as a + * one-off; however, if you need to call it multiple times on the + * same network, it is probably better to call the above version + * directly so that you only construct `scratch' and `backedges' + * once. + * + * Additional return value is now -1, meaning that scratch space + * could not be allocated. + */ +int maxflow(int nv, int source, int sink, + int ne, const int *edges, const int *capacity, + int *flow, int *cut); + +#endif /* MAXFLOW_MAXFLOW_H */ -- cgit v1.2.3