From 99569dff4791bb5492eddf5fbb6b960f1bf859db Mon Sep 17 00:00:00 2001 From: Jakob Cornell Date: Sun, 8 Sep 2019 19:49:59 -0500 Subject: [PATCH] Add missing impl tests and automated testing from makefile --- .gitignore | 3 +- algorithms/dijkstra/impl/java/Main.java | 35 ----------- algorithms/dijkstra/impl/python3/usage.py | 16 ----- algorithms/dijkstra/topic.tex | 10 ++-- algorithms/hull-2d/impl/java/Main.java | 14 ----- algorithms/hull-2d/topic.tex | 12 ++-- algorithms/network-flows/topic.tex | 11 +++- config.py | 6 +- contributors | 2 +- doc.tex | 2 +- .../impl => impl/dijkstra}/java/Graph.java | 0 impl/dijkstra/java/Test.java | 58 +++++++++++++++++++ impl/dijkstra/java/Usage.java | 29 ++++++++++ impl/dijkstra/java/makefile | 10 ++++ .../dijkstra}/python3/dijkstra.py | 0 impl/dijkstra/python3/makefile | 6 ++ impl/dijkstra/python3/test.py | 35 +++++++++++ impl/dijkstra/python3/usage.py | 15 +++++ .../impl => impl/hull-2d}/java/Hull.java | 18 +++--- impl/hull-2d/java/Test.java | 16 +++++ impl/hull-2d/java/Usage.java | 21 +++++++ impl/hull-2d/java/makefile | 10 ++++ .../impl => impl/hull-2d}/python3/hull.py | 0 impl/hull-2d/python3/makefile | 6 ++ impl/hull-2d/python3/test.py | 6 ++ .../impl => impl/hull-2d}/python3/usage.py | 0 .../network-flows}/java-junk/FlowNet.java | 0 .../network-flows}/java-junk/Main.java | 0 .../network-flows}/java-junk/usage | 0 .../network-flows}/python3/flows.py | 3 +- impl/network-flows/python3/makefile | 6 ++ impl/network-flows/python3/test.py | 21 +++++++ impl/network-flows/python3/usage.py | 15 +++++ makefile | 10 +++- readme => readme.md | 20 +++++-- util/run_all_tests.py | 9 +++ 36 files changed, 321 insertions(+), 104 deletions(-) delete mode 100644 algorithms/dijkstra/impl/java/Main.java delete mode 100644 algorithms/dijkstra/impl/python3/usage.py delete mode 100644 algorithms/hull-2d/impl/java/Main.java rename {algorithms/dijkstra/impl => impl/dijkstra}/java/Graph.java (100%) create mode 100644 impl/dijkstra/java/Test.java create mode 100644 impl/dijkstra/java/Usage.java create mode 100644 impl/dijkstra/java/makefile rename {algorithms/dijkstra/impl => impl/dijkstra}/python3/dijkstra.py (100%) create mode 100644 impl/dijkstra/python3/makefile create mode 100644 impl/dijkstra/python3/test.py create mode 100644 impl/dijkstra/python3/usage.py rename {algorithms/hull-2d/impl => impl/hull-2d}/java/Hull.java (91%) create mode 100644 impl/hull-2d/java/Test.java create mode 100644 impl/hull-2d/java/Usage.java create mode 100644 impl/hull-2d/java/makefile rename {algorithms/hull-2d/impl => impl/hull-2d}/python3/hull.py (100%) create mode 100644 impl/hull-2d/python3/makefile create mode 100644 impl/hull-2d/python3/test.py rename {algorithms/hull-2d/impl => impl/hull-2d}/python3/usage.py (100%) rename {algorithms/network-flows/impl => impl/network-flows}/java-junk/FlowNet.java (100%) rename {algorithms/network-flows/impl => impl/network-flows}/java-junk/Main.java (100%) rename {algorithms/network-flows/impl => impl/network-flows}/java-junk/usage (100%) rename {algorithms/network-flows/impl => impl/network-flows}/python3/flows.py (96%) create mode 100644 impl/network-flows/python3/makefile create mode 100644 impl/network-flows/python3/test.py create mode 100644 impl/network-flows/python3/usage.py rename readme => readme.md (51%) create mode 100644 util/run_all_tests.py diff --git a/.gitignore b/.gitignore index 16be8f2..fd6aad7 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,2 @@ -/output/ +output/ +__pycache__/ diff --git a/algorithms/dijkstra/impl/java/Main.java b/algorithms/dijkstra/impl/java/Main.java deleted file mode 100644 index 8ca56a7..0000000 --- a/algorithms/dijkstra/impl/java/Main.java +++ /dev/null @@ -1,35 +0,0 @@ -import java.util.Collections; - -public class Main { - public static void main(String[] args) { - Graph graph = new Graph(); - Node a = new Node(); - Node b = new Node(); - Node c = new Node(); - Node d = new Node(); - Node e = new Node(); - Node f = new Node(); - - // add each node to `graph.nodes' - Collections.addAll(graph.nodes, new Node[] {a,b,c,d,e,f}); - - // make edges between nodes - a.adj.put(c, 6l); - b.adj.put(a, 9l); - c.adj.put(a, 6l); - d.adj.put(b, 2l); - d.adj.put(c, 11l); - e.adj.put(b, 14l); - e.adj.put(d, 9l); - e.adj.put(f, 7l); - f.adj.put(c, 15l); - f.adj.put(d, 10l); - - // search the whole graph, starting at node `e' - graph.search(e); - System.out.println(a.dist); - System.out.println(a.prev == b); - // be sure to reset the graph before performing another search - graph.reset(); - } -} diff --git a/algorithms/dijkstra/impl/python3/usage.py b/algorithms/dijkstra/impl/python3/usage.py deleted file mode 100644 index 6000afd..0000000 --- a/algorithms/dijkstra/impl/python3/usage.py +++ /dev/null @@ -1,16 +0,0 @@ -a = Node() -b = Node('foo bar') -c = Node() -d = Node([1, 2, 3]) -e = Node() - -# each node has an adjacency `dict'; each key is the destination of an outward edge, and the corresponding value is the edge cost -a.adj[b] = 5 -b.adj[c] = 5 -c.adj[d] = 5 -a.adj[d] = 30 - -(dists, prev) = a.search() -assert e not in dists -assert dists[d] == 15 -assert prev[c] == b diff --git a/algorithms/dijkstra/topic.tex b/algorithms/dijkstra/topic.tex index 28e4d35..35d4d8e 100644 --- a/algorithms/dijkstra/topic.tex +++ b/algorithms/dijkstra/topic.tex @@ -1,5 +1,5 @@ { -\newcommand{\BasePath}{\ProjRootPrefix/algorithms/dijkstra} +\newcommand{\ImplPath}{\ProjRootPrefix/impl/dijkstra} \TopicHeader{Weighted Shortest Path: Dijkstra's Agorithm} @@ -18,13 +18,13 @@ \TopicSubHeader{Python 3} - \inputminted{python}{\BasePath/impl/python3/dijkstra.py} + \inputminted{python}{\ImplPath/python3/dijkstra.py} The \texttt{Node} constructor accepts a \texttt{data} parameter. Any value can be passed in, and it will be stored in the node to facilitate associating the nodes with data specific to the problem. Here's a usage example: - \inputminted{python}{\BasePath/impl/python3/usage.py} + \inputminted{python}{\ImplPath/python3/usage.py} In this implementation, two dictionaries are returned which provide the distance and previous-node information. To see if a node is reachable, simply check whether the node is a key in the first (distance) dictionary. @@ -32,12 +32,12 @@ \TopicSubHeader{Java} \centerline{\texttt{Graph.java}} - \inputminted{java}{\BasePath/impl/java/Graph.java} + \inputminted{java}{\ImplPath/java/Graph.java} The code may be used as follows. If you need to attach some data to the nodes, you could add a field to the \texttt{Node} class or use a \texttt{Map} to keep track of the association. - \inputminted{java}{\BasePath/impl/java/Main.java} + \inputminted{java}{\ImplPath/java/Usage.java} The visited flag, previous-node links, and distances are accessible as fields on the \texttt{Node} objects after the search. } diff --git a/algorithms/hull-2d/impl/java/Main.java b/algorithms/hull-2d/impl/java/Main.java deleted file mode 100644 index b7b61cc..0000000 --- a/algorithms/hull-2d/impl/java/Main.java +++ /dev/null @@ -1,14 +0,0 @@ -import java.util.*; - -public class Main { - public static void main(String[] args) { - Point a = new Point(0, 0); - Point b = new Point(-2, 2); - Point c = new Point(0, 4); - Point d = new Point(2, 2); - Point e = new Point(0, 2); - - List hull = Hull.hull(new HashSet<>(Arrays.asList(new Point[] {a, b, c, d, e}))); - assert hull.equals(Arrays.asList(new Point[] {a, d, c, b})); - } -} diff --git a/algorithms/hull-2d/topic.tex b/algorithms/hull-2d/topic.tex index ca7efc8..4eb9cc2 100644 --- a/algorithms/hull-2d/topic.tex +++ b/algorithms/hull-2d/topic.tex @@ -1,10 +1,10 @@ { -\newcommand{\BasePath}{\ProjRootPrefix/algorithms/hull-2d} +\newcommand{\ImplPath}{\ProjRootPrefix/impl/hull-2d} \TopicHeader{Convex Hull (2D)} Convex hull algorithms are given a collection of points and output a subset of just the outermost points. - Formally, the output is the points of a polygon within which lie all points in the input. + Formally, the output is the points of a convex polygon within which lie all points in the input. The implementations here use a technique called Graham scan to compute the convex hull with time complexity $O(n \log n)$, where $n$ is the number of input points. The output points are ordered: the bottom-most (and then leftmost) point appears first, then the remaining hull points in counterclockwise order. @@ -12,19 +12,19 @@ \TopicSubHeader{Java} \centerline{\texttt{Hull.java}} - \inputminted{java}{\BasePath/impl/java/Hull.java} + \inputminted{java}{\ImplPath/java/Hull.java} This may be used as follows: - \inputminted{java}{\BasePath/impl/java/Main.java} + \inputminted{java}{\ImplPath/java/Usage.java} \TopicSubHeader{Python 3} - \inputminted{python}{\BasePath/impl/python3/hull.py} + \inputminted{python}{\ImplPath/python3/hull.py} To run the algorithm, pass a set of $(x, y)$ pairs (\texttt{tuple}s) to \texttt{hull}. A sample usage: - \inputminted{python}{\BasePath/impl/python3/usage.py} + \inputminted{python}{\ImplPath/python3/usage.py} } diff --git a/algorithms/network-flows/topic.tex b/algorithms/network-flows/topic.tex index ed9685f..1dd1a68 100644 --- a/algorithms/network-flows/topic.tex +++ b/algorithms/network-flows/topic.tex @@ -1,5 +1,5 @@ { -\newcommand{\BasePath}{\ProjRootPrefix/algorithms/network-flows} +\newcommand{\ImplPath}{\ProjRootPrefix/impl/network-flows} \TopicHeader{Network Flows: Edmonds--Karp} @@ -15,5 +15,12 @@ \TopicSubHeader{Python 3} - \inputminted{python}{\BasePath/impl/python3/flows.py} + \inputminted{python}{\ImplPath/python3/flows.py} + + To use the code: + + \inputminted{python}{\ImplPath/python3/usage.py} + + The \texttt{cut\_src} variable here is a set of node objects representing the source side of the minimum cut. + If the set \texttt{n} contains all nodes in the network, the sink side is computed by \texttt{n - cut\_src}. } diff --git a/config.py b/config.py index 928f34d..67eb52e 100644 --- a/config.py +++ b/config.py @@ -1,16 +1,12 @@ r''' This file is responsible for configuring the document build. Some/all parameters are passed to LaTeX as generated code, which is probably a bad idea, but oh well. - -The keys in the `config' dictionary are the command names to assign in LaTeX. -So if I use `FooBar' in the dictionary, then the command `\FooBar' is available to the LaTeX code. -Note that an error will be raised if one of these names matches an existing LaTeX command. ''' config = { # whether to insert page breaks before reference items to ease lookup 'RefPageBrk': False, - # languages for which to exclude implementations (java, python3) + # languages for which to exclude implementations (java, python3) (to be implemented) 'exclude_langs': [], } diff --git a/contributors b/contributors index 1d362a4..ba95e4b 100644 --- a/contributors +++ b/contributors @@ -1,5 +1,5 @@ Contributors - - Jakob Cornell (creator): LaTeX code, build system, Python/Java algorithm implementations + - Jakob Cornell, creator: LaTeX code, build system, Python/Java algorithm implementations Attribution - Dijkstra's Algorithm implementations and complexity analysis based on content here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (reused under CC-BY-SA) diff --git a/doc.tex b/doc.tex index 17a16e4..231c016 100644 --- a/doc.tex +++ b/doc.tex @@ -4,7 +4,7 @@ \usepackage[margin=1in]{geometry} % for margin adjustment \usepackage{parskip} % replaces paragraph indentation with vertical space \usepackage{float} % used for captions on code listings -\usepackage{ifthen} % for conditional inclusion (page breaks) +\usepackage{ifthen} % for conditional compilation \newcommand{\ProjRootPrefix}{..} diff --git a/algorithms/dijkstra/impl/java/Graph.java b/impl/dijkstra/java/Graph.java similarity index 100% rename from algorithms/dijkstra/impl/java/Graph.java rename to impl/dijkstra/java/Graph.java diff --git a/impl/dijkstra/java/Test.java b/impl/dijkstra/java/Test.java new file mode 100644 index 0000000..69a1a40 --- /dev/null +++ b/impl/dijkstra/java/Test.java @@ -0,0 +1,58 @@ +import java.util.Map; +import java.util.HashMap; +import java.util.Collections; + +public class Test { + public static void main(String[] args) { + Graph graph = new Graph(); + Node a = new Node(); + Node b = new Node(); + Node c = new Node(); + Node d = new Node(); + Node e = new Node(); + Node f = new Node(); + + Collections.addAll(graph.nodes, new Node[] {a,b,c,d,e,f}); + + a.adj.put(c, 6l); + b.adj.put(a, 9l); + c.adj.put(a, 6l); + d.adj.put(b, 2l); + d.adj.put(c, 11l); + e.adj.put(b, 14l); + e.adj.put(d, 9l); + e.adj.put(f, 7l); + f.adj.put(c, 15l); + f.adj.put(d, 10l); + + graph.search(e); + + Map actDists = new HashMap<>(); + for (Node n : graph.nodes) { + actDists.put(n, n.dist); + } + Map expDists = new HashMap<>(); + expDists.put(a, 20l); + expDists.put(b, 11l); + expDists.put(c, 20l); + expDists.put(d, 9l); + expDists.put(e, 0l); + expDists.put(f, 7l); + assert actDists.equals(expDists); + + Map actPrevs = new HashMap<>(); + for (Node n : graph.nodes) { + actPrevs.put(n, n.prev); + } + Map expPrevs = new HashMap<>(); + expPrevs.put(a, b); + expPrevs.put(b, d); + expPrevs.put(c, d); + expPrevs.put(d, e); + expPrevs.put(e, null); + expPrevs.put(f, e); + assert actPrevs.equals(expPrevs); + + System.out.println("Pass"); + } +} diff --git a/impl/dijkstra/java/Usage.java b/impl/dijkstra/java/Usage.java new file mode 100644 index 0000000..ebf88bb --- /dev/null +++ b/impl/dijkstra/java/Usage.java @@ -0,0 +1,29 @@ +import java.util.Collections; + +public class Usage { + public static void main(String[] args) { + Graph graph = new Graph(); + Node a = new Node(); + Node b = new Node(); + Node c = new Node(); + + // add nodes to graph + graph.nodes.add(a); + graph.nodes.add(b); + graph.nodes.add(c); + + a.adj.put(b, 5l); // make an edge from `a' to `b' of weight 5 + b.adj.put(c, 3l); + c.adj.put(a, 10l); + c.adj.put(b, 0l); + + // search the whole graph, starting at node `a' + graph.search(a); + + System.out.println(b.dist); + System.out.println(c.prev == b); + + // be sure to reset the graph before performing another search + graph.reset(); + } +} diff --git a/impl/dijkstra/java/makefile b/impl/dijkstra/java/makefile new file mode 100644 index 0000000..9ab38df --- /dev/null +++ b/impl/dijkstra/java/makefile @@ -0,0 +1,10 @@ +.PHONY: test + +SOURCES := Graph.java Test.java Usage.java + +test: output/Test.class + @java -enableassertions -cp output Test + +output/Test.class: $(SOURCES) + @mkdir -p output + javac -d output Test.java Usage.java diff --git a/algorithms/dijkstra/impl/python3/dijkstra.py b/impl/dijkstra/python3/dijkstra.py similarity index 100% rename from algorithms/dijkstra/impl/python3/dijkstra.py rename to impl/dijkstra/python3/dijkstra.py diff --git a/impl/dijkstra/python3/makefile b/impl/dijkstra/python3/makefile new file mode 100644 index 0000000..9827325 --- /dev/null +++ b/impl/dijkstra/python3/makefile @@ -0,0 +1,6 @@ +.PHONY: test + +SOURCES := dijkstra.py test.py + +test: $(SOURCES) + @python3 test.py diff --git a/impl/dijkstra/python3/test.py b/impl/dijkstra/python3/test.py new file mode 100644 index 0000000..444637f --- /dev/null +++ b/impl/dijkstra/python3/test.py @@ -0,0 +1,35 @@ +from dijkstra import * + +a, b, c, d, e, f = [Node() for _ in range(6)] + +a.adj[c] = 6 +b.adj[a] = 9 +c.adj[a] = 6 +d.adj[b] = 2 +d.adj[c] = 11 +e.adj[b] = 14 +e.adj[d] = 9 +e.adj[f] = 7 +f.adj[c] = 15 +f.adj[d] = 10 + +(dists, prev) = e.search() + +assert dists == { + a: 20, + b: 11, + c: 20, + d: 9, + e: 0, + f: 7, +} + +assert prev == { + a: b, + b: d, + c: d, + d: e, + f: e, +} + +print("Pass") diff --git a/impl/dijkstra/python3/usage.py b/impl/dijkstra/python3/usage.py new file mode 100644 index 0000000..1556caf --- /dev/null +++ b/impl/dijkstra/python3/usage.py @@ -0,0 +1,15 @@ +a = Node() +b = Node('foo bar') +c = Node() +d = Node([1, 2, 3]) +e = Node() + +a.adj[b] = 5 # make an edge from `a' to `b' with weight 5 +b.adj[c] = 5 +c.adj[d] = 5 +a.adj[d] = 30 + +(dists, prev) = a.search() # search the graph outward from `a' + +assert dists[d] == 15 +assert prev[c] == b diff --git a/algorithms/hull-2d/impl/java/Hull.java b/impl/hull-2d/java/Hull.java similarity index 91% rename from algorithms/hull-2d/impl/java/Hull.java rename to impl/hull-2d/java/Hull.java index dbc0f2a..6b99aa9 100644 --- a/algorithms/hull-2d/impl/java/Hull.java +++ b/impl/hull-2d/java/Hull.java @@ -1,6 +1,15 @@ import java.util.*; public class Hull { + static class Point { + long x; + long y; + Point(long x, long y) { + this.x = x; + this.y = y; + } + } + static long dir(Point a, Point b, Point c) { return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x); } @@ -38,12 +47,3 @@ public class Hull { return out; } } - -class Point { - long x; - long y; - Point(long x, long y) { - this.x = x; - this.y = y; - } -} diff --git a/impl/hull-2d/java/Test.java b/impl/hull-2d/java/Test.java new file mode 100644 index 0000000..868f782 --- /dev/null +++ b/impl/hull-2d/java/Test.java @@ -0,0 +1,16 @@ +import java.util.*; + +public class Test { + public static void main(String[] args) { + Hull.Point a = new Hull.Point(0, 0); + Hull.Point b = new Hull.Point(-2, 2); + Hull.Point c = new Hull.Point(0, 4); + Hull.Point d = new Hull.Point(2, 2); + Hull.Point e = new Hull.Point(0, 2); + + List hull = Hull.hull(new HashSet<>(Arrays.asList(new Hull.Point[] {a, b, c, d, e}))); + assert hull.equals(Arrays.asList(new Hull.Point[] {a, d, c, b})); + + System.out.println("Pass"); + } +} diff --git a/impl/hull-2d/java/Usage.java b/impl/hull-2d/java/Usage.java new file mode 100644 index 0000000..e045ee6 --- /dev/null +++ b/impl/hull-2d/java/Usage.java @@ -0,0 +1,21 @@ +import java.util.*; + +public class Usage { + public static void main(String[] args) { + Hull.Point a = new Hull.Point(0, 3); + Hull.Point b = new Hull.Point(-2, 2); + Hull.Point c = new Hull.Point(1, -6); + + // construct a set of points for input + Set points = new HashSet<>(Arrays.asList(new Hull.Point[] {a, b, c})); + // or manually: + Set points2 = new HashSet<>(); + points2.add(a); + points2.add(b); + points2.add(c); + + List out = Hull.hull(points); + System.out.println(out.get(0) == c); + System.out.println(out.contains(b)); + } +} diff --git a/impl/hull-2d/java/makefile b/impl/hull-2d/java/makefile new file mode 100644 index 0000000..e950b22 --- /dev/null +++ b/impl/hull-2d/java/makefile @@ -0,0 +1,10 @@ +.PHONY: test + +SOURCES := Hull.java Test.java Usage.java + +test: output/Test.class + @java -enableassertions -cp output Test + +output/Test.class: $(SOURCES) + @mkdir -p output + javac -d output Test.java Usage.java diff --git a/algorithms/hull-2d/impl/python3/hull.py b/impl/hull-2d/python3/hull.py similarity index 100% rename from algorithms/hull-2d/impl/python3/hull.py rename to impl/hull-2d/python3/hull.py diff --git a/impl/hull-2d/python3/makefile b/impl/hull-2d/python3/makefile new file mode 100644 index 0000000..ecb77a0 --- /dev/null +++ b/impl/hull-2d/python3/makefile @@ -0,0 +1,6 @@ +.PHONY: test + +SOURCES := hull.py test.py + +test: $(SOURCES) + @python3 test.py diff --git a/impl/hull-2d/python3/test.py b/impl/hull-2d/python3/test.py new file mode 100644 index 0000000..8976d21 --- /dev/null +++ b/impl/hull-2d/python3/test.py @@ -0,0 +1,6 @@ +from hull import * + +points = {(0,0), (-2,2), (0,4), (2,2), (0,2)} +assert hull(points) == [(0,0), (2,2), (0,4), (-2,2)] + +print("Pass") diff --git a/algorithms/hull-2d/impl/python3/usage.py b/impl/hull-2d/python3/usage.py similarity index 100% rename from algorithms/hull-2d/impl/python3/usage.py rename to impl/hull-2d/python3/usage.py diff --git a/algorithms/network-flows/impl/java-junk/FlowNet.java b/impl/network-flows/java-junk/FlowNet.java similarity index 100% rename from algorithms/network-flows/impl/java-junk/FlowNet.java rename to impl/network-flows/java-junk/FlowNet.java diff --git a/algorithms/network-flows/impl/java-junk/Main.java b/impl/network-flows/java-junk/Main.java similarity index 100% rename from algorithms/network-flows/impl/java-junk/Main.java rename to impl/network-flows/java-junk/Main.java diff --git a/algorithms/network-flows/impl/java-junk/usage b/impl/network-flows/java-junk/usage similarity index 100% rename from algorithms/network-flows/impl/java-junk/usage rename to impl/network-flows/java-junk/usage diff --git a/algorithms/network-flows/impl/python3/flows.py b/impl/network-flows/python3/flows.py similarity index 96% rename from algorithms/network-flows/impl/python3/flows.py rename to impl/network-flows/python3/flows.py index 41ac788..a904a32 100644 --- a/algorithms/network-flows/impl/python3/flows.py +++ b/impl/network-flows/python3/flows.py @@ -26,8 +26,9 @@ class Node: e = Edge(f, t, cap) f.edges.add(e) t.edges.add(e) + return e -def ff(nodes, src, sink): +def ek(nodes, src, sink): def path(): prev = {} q = deque([src]) diff --git a/impl/network-flows/python3/makefile b/impl/network-flows/python3/makefile new file mode 100644 index 0000000..ef1e50a --- /dev/null +++ b/impl/network-flows/python3/makefile @@ -0,0 +1,6 @@ +.PHONY: test + +SOURCES := flows.py test.py + +test: $(SOURCES) + @python3 test.py diff --git a/impl/network-flows/python3/test.py b/impl/network-flows/python3/test.py new file mode 100644 index 0000000..d68b85d --- /dev/null +++ b/impl/network-flows/python3/test.py @@ -0,0 +1,21 @@ +from flows import * + +src, a, b, c, d, e, f, sink = nodes = [Node() for _ in range(8)] + +src_to_a = Node.edge(src, a, 4) +Node.edge(src, b, 4) +Node.edge(src, c, 2) +Node.edge(a, d, 3) +Node.edge(b, e, 3) +Node.edge(c, e, 3) +Node.edge(c, f, 1) +Node.edge(d, sink, 4) +Node.edge(e, sink, 5) +Node.edge(f, sink, 5) + +val, cut_src = ek(nodes, src, sink) + +assert val == 8 +assert src_to_a.cap_to(src) == 3 + +print("Pass") diff --git a/impl/network-flows/python3/usage.py b/impl/network-flows/python3/usage.py new file mode 100644 index 0000000..2c6a33e --- /dev/null +++ b/impl/network-flows/python3/usage.py @@ -0,0 +1,15 @@ +# pass a value here to store data in the node (optional) +src = Node('foo') +a = Node('bar') +b = Node() +sink = Node(1234) + +Node.edge(src, a, 5) # add an edge from `src' to `a' with capacity 5 +Node.edge(a, b, 3) +edge = Node.edge(b, sink, 6) # can capture an edge object for later use + +val, cut_src = ek(nodes, src, sink) + +assert val == 3 # flow value + +print(edge.cap_to(b)) # amount of flow from `b' to `sink' in the saturated network diff --git a/makefile b/makefile index 6edc49f..af0e338 100644 --- a/makefile +++ b/makefile @@ -1,5 +1,6 @@ -# defensively depend on all files in the `algorithms' tree +# These are more than the files we really need to depend on, but keep things simple. ALG_FILES := $(shell find algorithms -type f) +IMPL_FILES := $(shell find impl -type f) BUILD_CMD := ( cd output && pdflatex -shell-escape ../doc.tex ) @@ -10,13 +11,16 @@ doc: output/doc.pdf output/latex-defines: config.py python3 config.py -output/doc.pdf: makefile output/latex-defines doc.tex $(ALG_FILES) +output/doc.pdf: makefile output/latex-defines doc.tex $(ALG_FILES) $(IMPL_FILES) # build twice for table of contents $(BUILD_CMD) $(BUILD_CMD) +test: + @python3 util/run_all_tests.py + clean: rm -rf output mkdir output -.PHONY: clean doc all +.PHONY: all doc test clean diff --git a/readme b/readme.md similarity index 51% rename from readme rename to readme.md index 0059876..0fa4a92 100644 --- a/readme +++ b/readme.md @@ -2,19 +2,29 @@ This project aims to (ultimately) provide a reference document covering any information useful to participants in college programming contests, which typically only allow printed materials. This primarily includes algorithm implementations and documentation, but the project may at some point support building custom selections of language and standard library documentation. The text and programming language coverage are to some extent tailored to use by Oberlin College students. -# Build +# Building the document The following are currently needed to build the document using the Make build file: - Make - Python 3 - - `pdflatex' LaTeX compiler - - LaTeX packages (see `doc.tex') + - `pdflatex` LaTeX compiler + - LaTeX packages (see `doc.tex`) - Unix shell environment (typical MacOS or Linux should work) Currently all LaTeX-related requirements are provided by the TeX Live distribution. -To configure the document build, take a look at `config.py', which contains a configuration dictionary and a mechanism for passing values to LaTeX. To start the build, just run the command `make' from the project root. The document is placed at `output/doc.pdf'. +To configure the document build, take a look at `config.py`, which contains a configuration dictionary and a mechanism for passing values to LaTeX. To start the build, just run the command `make` from the project root. The document is placed at `output/doc.pdf`. + +In the future, maybe some LaTeX template system could be used to make things cleaner. + +# Working with algorithm implementations + +Algorithm implementations are found in the `impl` directory. Each implementation includes a usage sample (`usage.py`/`Usage.java`) and a test program (`test.py`/`Test.java`). The usage files are included in the document to show the interface the implementations use. + +The test program can be run to verify the implementation works on a nontrivial test case. Just invoke `make` from the directory with the source files. You'll either see "Pass" or an indication of where the test failed. + +Note that the document pulls both the source files and the usage files from this location, so references in LaTeX need to be updated if file names are changed. # Contribution, attribution, and redistribution -This document is intended to be freely editable and redistributable. For more information, see the `license' file. Please ensure that copyright and license restrictions are compatible with this project when adding algorithm implementations based on others' work. +This document is intended to be freely editable and redistributable. For more information, see the `license` file. Please ensure that copyright and license restrictions are compatible with this project when adding algorithm implementations based on others' work. diff --git a/util/run_all_tests.py b/util/run_all_tests.py new file mode 100644 index 0000000..148e18b --- /dev/null +++ b/util/run_all_tests.py @@ -0,0 +1,9 @@ +import subprocess +from pathlib import Path + +for alg in Path('impl').iterdir(): + if alg.is_dir(): + for lang in alg.iterdir(): + if lang.is_dir() and lang.joinpath('makefile').exists(): + print('{}: {}'.format(alg.name, lang.name)) + subprocess.run(['make', '--no-print-directory', '-C', str(lang)]) -- 2.30.2