puzzles: resync with upstream

This brings the upstream version to b3da238 (though some of my own
changes are included on top of that).

Change-Id: Ida73e8cd86765413147ce891af3cc2b7aeda2b2a

1 files changed, 0 insertions, 95 deletions

diff --git a/apps/plugins/puzzles/src/maxflow.h b/apps/plugins/puzzles/src/maxflow.h
deleted file mode 100644
index d490f45..0000000
--- a/apps/plugins/puzzles/src/maxflow.h
+++ /dev/null
@@ -1,95 +0,0 @@
-/*
- * 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 */