diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/maxflow.h | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/maxflow.h')
-rw-r--r-- | apps/plugins/puzzles/src/maxflow.h | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/maxflow.h b/apps/plugins/puzzles/src/maxflow.h new file mode 100644 index 0000000000..d490f45421 --- /dev/null +++ b/apps/plugins/puzzles/src/maxflow.h | |||
@@ -0,0 +1,95 @@ | |||
1 | /* | ||
2 | * Edmonds-Karp algorithm for finding a maximum flow and minimum | ||
3 | * cut in a network. Almost identical to the Ford-Fulkerson | ||
4 | * algorithm, but apparently using breadth-first search to find the | ||
5 | * _shortest_ augmenting path is a good way to guarantee | ||
6 | * termination and ensure the time complexity is not dependent on | ||
7 | * the actual value of the maximum flow. I don't understand why | ||
8 | * that should be, but it's claimed on the Internet that it's been | ||
9 | * proved, and that's good enough for me. I prefer BFS to DFS | ||
10 | * anyway :-) | ||
11 | */ | ||
12 | |||
13 | #ifndef MAXFLOW_MAXFLOW_H | ||
14 | #define MAXFLOW_MAXFLOW_H | ||
15 | |||
16 | /* | ||
17 | * The actual algorithm. | ||
18 | * | ||
19 | * Inputs: | ||
20 | * | ||
21 | * - `scratch' is previously allocated scratch space of a size | ||
22 | * previously determined by calling `maxflow_scratch_size'. | ||
23 | * | ||
24 | * - `nv' is the number of vertices. Vertices are assumed to be | ||
25 | * numbered from 0 to nv-1. | ||
26 | * | ||
27 | * - `source' and `sink' are the distinguished source and sink | ||
28 | * vertices. | ||
29 | * | ||
30 | * - `ne' is the number of edges in the graph. | ||
31 | * | ||
32 | * - `edges' is an array of 2*ne integers, giving a (source, dest) | ||
33 | * pair for each network edge. Edge pairs are expected to be | ||
34 | * sorted in lexicographic order. | ||
35 | * | ||
36 | * - `backedges' is an array of `ne' integers, each a distinct | ||
37 | * index into `edges'. The edges in `edges', if permuted as | ||
38 | * specified by this array, should end up sorted in the _other_ | ||
39 | * lexicographic order, i.e. dest taking priority over source. | ||
40 | * | ||
41 | * - `capacity' is an array of `ne' integers, giving a maximum | ||
42 | * flow capacity for each edge. A negative value is taken to | ||
43 | * indicate unlimited capacity on that edge, but note that there | ||
44 | * may not be any unlimited-capacity _path_ from source to sink | ||
45 | * or an assertion will be failed. | ||
46 | * | ||
47 | * Output: | ||
48 | * | ||
49 | * - `flow' must be non-NULL. It is an array of `ne' integers, | ||
50 | * each giving the final flow along each edge. | ||
51 | * | ||
52 | * - `cut' may be NULL. If non-NULL, it is an array of `nv' | ||
53 | * integers, which will be set to zero or one on output, in such | ||
54 | * a way that: | ||
55 | * + the set of zero vertices includes the source | ||
56 | * + the set of one vertices includes the sink | ||
57 | * + the maximum flow capacity between the zero and one vertex | ||
58 | * sets is achieved (i.e. all edges from a zero vertex to a | ||
59 | * one vertex are at full capacity, while all edges from a | ||
60 | * one vertex to a zero vertex have no flow at all). | ||
61 | * | ||
62 | * - the returned value from the function is the total flow | ||
63 | * achieved. | ||
64 | */ | ||
65 | int maxflow_with_scratch(void *scratch, int nv, int source, int sink, | ||
66 | int ne, const int *edges, const int *backedges, | ||
67 | const int *capacity, int *flow, int *cut); | ||
68 | |||
69 | /* | ||
70 | * The above function expects its `scratch' and `backedges' | ||
71 | * parameters to have already been set up. This allows you to set | ||
72 | * them up once and use them in multiple invocates of the | ||
73 | * algorithm. Now I provide functions to actually do the setting | ||
74 | * up. | ||
75 | */ | ||
76 | int maxflow_scratch_size(int nv); | ||
77 | void maxflow_setup_backedges(int ne, const int *edges, int *backedges); | ||
78 | |||
79 | /* | ||
80 | * Simplified version of the above function. All parameters are the | ||
81 | * same, except that `scratch' and `backedges' are constructed | ||
82 | * internally. This is the simplest way to call the algorithm as a | ||
83 | * one-off; however, if you need to call it multiple times on the | ||
84 | * same network, it is probably better to call the above version | ||
85 | * directly so that you only construct `scratch' and `backedges' | ||
86 | * once. | ||
87 | * | ||
88 | * Additional return value is now -1, meaning that scratch space | ||
89 | * could not be allocated. | ||
90 | */ | ||
91 | int maxflow(int nv, int source, int sink, | ||
92 | int ne, const int *edges, const int *capacity, | ||
93 | int *flow, int *cut); | ||
94 | |||
95 | #endif /* MAXFLOW_MAXFLOW_H */ | ||