From ba100e03db561835be9fa9f6b38638bf38f15128 Mon Sep 17 00:00:00 2001 From: Jakob Cornell Date: Fri, 26 Jun 2020 01:55:58 -0500 Subject: [PATCH] Add structures section, implement disjoint set and Kruskal's --- algorithms/dijkstra/topic.tex | 43 ----------------- algorithms/hull-2d/topic.tex | 30 ------------ algorithms/network-flows/topic.tex | 26 ---------- config.py | 2 +- contributors | 12 +++-- doc.tex | 19 ++++++-- .../{ => algorithms}/dijkstra/java/Graph.java | 0 impl/{ => algorithms}/dijkstra/java/Test.java | 0 .../{ => algorithms}/dijkstra/java/Usage.java | 0 impl/{ => algorithms}/dijkstra/java/makefile | 0 .../dijkstra/python3/dijkstra.py | 0 .../dijkstra/python3/makefile | 0 .../{ => algorithms}/dijkstra/python3/test.py | 0 .../dijkstra/python3/usage.py | 0 impl/{ => algorithms}/hull-2d/java/Hull.java | 0 impl/{ => algorithms}/hull-2d/java/Test.java | 0 impl/{ => algorithms}/hull-2d/java/Usage.java | 0 impl/{ => algorithms}/hull-2d/java/makefile | 0 impl/{ => algorithms}/hull-2d/python3/hull.py | 0 .../{ => algorithms}/hull-2d/python3/makefile | 0 impl/{ => algorithms}/hull-2d/python3/test.py | 0 .../{ => algorithms}/hull-2d/python3/usage.py | 0 impl/algorithms/kruskals/python3/kruskals.py | 12 +++++ impl/algorithms/kruskals/python3/makefile | 8 ++++ impl/algorithms/kruskals/python3/test.py | 32 +++++++++++++ impl/algorithms/kruskals/python3/usage.py | 10 ++++ impl/algorithms/network-flows/Ek.java | 47 +++++++++++++++++++ .../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 | 2 +- .../network-flows/python3/makefile | 0 impl/algorithms/network-flows/python3/test.py | 21 +++++++++ .../network-flows/python3/usage.py | 0 impl/network-flows/python3/test.py | 21 --------- .../disjoint-sets/python3/disjoint_sets.py | 26 ++++++++++ .../structures/disjoint-sets/python3/usage.py | 10 ++++ latex/algorithms/dijkstra.tex | 43 +++++++++++++++++ latex/algorithms/hull-2d.tex | 30 ++++++++++++ latex/algorithms/kruskals.tex | 42 +++++++++++++++++ latex/algorithms/network-flows.tex | 26 ++++++++++ latex/structures/disjoint-sets.tex | 25 ++++++++++ makefile | 2 +- todo | 2 +- util/run_all_tests.py | 2 +- 45 files changed, 362 insertions(+), 131 deletions(-) delete mode 100644 algorithms/dijkstra/topic.tex delete mode 100644 algorithms/hull-2d/topic.tex delete mode 100644 algorithms/network-flows/topic.tex rename impl/{ => algorithms}/dijkstra/java/Graph.java (100%) rename impl/{ => algorithms}/dijkstra/java/Test.java (100%) rename impl/{ => algorithms}/dijkstra/java/Usage.java (100%) rename impl/{ => algorithms}/dijkstra/java/makefile (100%) rename impl/{ => algorithms}/dijkstra/python3/dijkstra.py (100%) rename impl/{ => algorithms}/dijkstra/python3/makefile (100%) rename impl/{ => algorithms}/dijkstra/python3/test.py (100%) rename impl/{ => algorithms}/dijkstra/python3/usage.py (100%) rename impl/{ => algorithms}/hull-2d/java/Hull.java (100%) rename impl/{ => algorithms}/hull-2d/java/Test.java (100%) rename impl/{ => algorithms}/hull-2d/java/Usage.java (100%) rename impl/{ => algorithms}/hull-2d/java/makefile (100%) rename impl/{ => algorithms}/hull-2d/python3/hull.py (100%) rename impl/{ => algorithms}/hull-2d/python3/makefile (100%) rename impl/{ => algorithms}/hull-2d/python3/test.py (100%) rename impl/{ => algorithms}/hull-2d/python3/usage.py (100%) create mode 100644 impl/algorithms/kruskals/python3/kruskals.py create mode 100644 impl/algorithms/kruskals/python3/makefile create mode 100644 impl/algorithms/kruskals/python3/test.py create mode 100644 impl/algorithms/kruskals/python3/usage.py create mode 100644 impl/algorithms/network-flows/Ek.java rename impl/{ => algorithms}/network-flows/java-junk/FlowNet.java (100%) rename impl/{ => algorithms}/network-flows/java-junk/Main.java (100%) rename impl/{ => algorithms}/network-flows/java-junk/usage (100%) rename impl/{ => algorithms}/network-flows/python3/flows.py (97%) rename impl/{ => algorithms}/network-flows/python3/makefile (100%) create mode 100644 impl/algorithms/network-flows/python3/test.py rename impl/{ => algorithms}/network-flows/python3/usage.py (100%) delete mode 100644 impl/network-flows/python3/test.py create mode 100644 impl/structures/disjoint-sets/python3/disjoint_sets.py create mode 100644 impl/structures/disjoint-sets/python3/usage.py create mode 100644 latex/algorithms/dijkstra.tex create mode 100644 latex/algorithms/hull-2d.tex create mode 100644 latex/algorithms/kruskals.tex create mode 100644 latex/algorithms/network-flows.tex create mode 100644 latex/structures/disjoint-sets.tex diff --git a/algorithms/dijkstra/topic.tex b/algorithms/dijkstra/topic.tex deleted file mode 100644 index 35d4d8e..0000000 --- a/algorithms/dijkstra/topic.tex +++ /dev/null @@ -1,43 +0,0 @@ -{ -\newcommand{\ImplPath}{\ProjRootPrefix/impl/dijkstra} - -\TopicHeader{Weighted Shortest Path: Dijkstra's Agorithm} - - Dijkstra's algorithm is useful for computing the shortest path between nodes in a graph where edges have nonnegative weights. - The worst-case performance of the algorithm is $O(E + V \log V)$, if the graph has $E$ edges and $V$ nodes. - - All implementations here provide as output, for each node, the following information: - \begin{itemize} - \item whether the node was reachable from the search root - \item the shortest distance between the root and the node - \item the previous node along the shortest path, i.e. the node that was being explored when this node was first found - \end{itemize} - Note that the path of nodes from the root to any reachable node can be computed by following the previous-node links iteratively until the search root is reached. - - The implementations use directed graphs, so in order to emulate searching an undirected graph, two directed edges going in opposite directions should be made for each edge in the desired undirected graph. - - \TopicSubHeader{Python 3} - - \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}{\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. - - \TopicSubHeader{Java} - - \centerline{\texttt{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}{\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/topic.tex b/algorithms/hull-2d/topic.tex deleted file mode 100644 index 4eb9cc2..0000000 --- a/algorithms/hull-2d/topic.tex +++ /dev/null @@ -1,30 +0,0 @@ -{ -\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 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. - - \TopicSubHeader{Java} - - \centerline{\texttt{Hull.java}} - \inputminted{java}{\ImplPath/java/Hull.java} - - This may be used as follows: - - \inputminted{java}{\ImplPath/java/Usage.java} - - \TopicSubHeader{Python 3} - - \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}{\ImplPath/python3/usage.py} -} diff --git a/algorithms/network-flows/topic.tex b/algorithms/network-flows/topic.tex deleted file mode 100644 index 1dd1a68..0000000 --- a/algorithms/network-flows/topic.tex +++ /dev/null @@ -1,26 +0,0 @@ -{ -\newcommand{\ImplPath}{\ProjRootPrefix/impl/network-flows} - -\TopicHeader{Network Flows: Edmonds--Karp} - - Network flows algorithms find the maximum flow through and the minimum cut of a flow network. - This terminology and relevant algorithms are covered in Algorithms (CS 280) at Oberlin. - - The implementations here use the Edmonds--Karp algorithm on flow networks with integer capacities. - The time complexity of the algorithm is $O\left( VE^2 \right)$, where $V$ and $E$ are the number of vertices and edges in the network, respectively. - - \TopicSubHeader{Java} - - Coming soon... - - \TopicSubHeader{Python 3} - - \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 67eb52e..c835871 100644 --- a/config.py +++ b/config.py @@ -5,7 +5,7 @@ Some/all parameters are passed to LaTeX as generated code, which is probably a b config = { # whether to insert page breaks before reference items to ease lookup - 'RefPageBrk': False, + 'RefPageBrk': True, # languages for which to exclude implementations (java, python3) (to be implemented) 'exclude_langs': [], } diff --git a/contributors b/contributors index ba95e4b..e2d6d69 100644 --- a/contributors +++ b/contributors @@ -1,6 +1,12 @@ Contributors - - Jakob Cornell, creator: LaTeX code, build system, Python/Java algorithm implementations + - Jakob Cornell, creator: LaTeX code, build system, Python/Java 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) - - convex hull implementation and complexity analysis based on content here: https://en.wikipedia.org/wiki/Graham_scan (reused under CC-BY-SA) + - Dijkstra's Algorithm implementations and complexity analysis based on content here: + https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (reused under CC-BY-SA) + - convex hull implementation and complexity analysis based on content here: + https://en.wikipedia.org/wiki/Graham_scan (reused under CC-BY-SA) + - Kruskal's Algorithm implementations and complexity analysis based on content here: + https://en.wikipedia.org/wiki/Kruskal's_algorithm (reused under CC-BY-SA) + - Disjoint sets implementation and complexity analysis based on content here: + https://en.wikipedia.org/wiki/Disjoint-set_data_structure (reused under CC-BY-SA) diff --git a/doc.tex b/doc.tex index 231c016..7d2265a 100644 --- a/doc.tex +++ b/doc.tex @@ -5,6 +5,7 @@ \usepackage{parskip} % replaces paragraph indentation with vertical space \usepackage{float} % used for captions on code listings \usepackage{ifthen} % for conditional compilation +\usepackage[toc,page]{appendix} \newcommand{\ProjRootPrefix}{..} @@ -15,6 +16,10 @@ \newcommand{\TopicHeader}{\subsection} \newcommand{\TopicSubHeader}{\subsubsection} +% values used in includes +\newcommand{\ImplPath}{\ProjRootPrefix/impl/algorithms} +\newcommand{\DsImplPath}{\ProjRootPrefix/impl/structures} + \newcommand{\RefBreak}{ \ifthenelse{\boolean{RefPageBrk}}{\pagebreak}{} } @@ -31,9 +36,17 @@ \pagebreak \section{Algorithms} - \input{\ProjRootPrefix/algorithms/dijkstra/topic.tex} + \input{\ProjRootPrefix/latex/algorithms/dijkstra.tex} + \RefBreak + \input{\ProjRootPrefix/latex/algorithms/hull-2d.tex} \RefBreak - \input{\ProjRootPrefix/algorithms/hull-2d/topic.tex} + \input{\ProjRootPrefix/latex/algorithms/network-flows.tex} + \RefBreak + \input{\ProjRootPrefix/latex/algorithms/kruskals.tex} + \RefBreak - \input{\ProjRootPrefix/algorithms/network-flows/topic.tex} + \begin{appendix} + \section{Data Structures} + \input{\ProjRootPrefix/latex/structures/disjoint-sets.tex} + \end{appendix} \end{document} diff --git a/impl/dijkstra/java/Graph.java b/impl/algorithms/dijkstra/java/Graph.java similarity index 100% rename from impl/dijkstra/java/Graph.java rename to impl/algorithms/dijkstra/java/Graph.java diff --git a/impl/dijkstra/java/Test.java b/impl/algorithms/dijkstra/java/Test.java similarity index 100% rename from impl/dijkstra/java/Test.java rename to impl/algorithms/dijkstra/java/Test.java diff --git a/impl/dijkstra/java/Usage.java b/impl/algorithms/dijkstra/java/Usage.java similarity index 100% rename from impl/dijkstra/java/Usage.java rename to impl/algorithms/dijkstra/java/Usage.java diff --git a/impl/dijkstra/java/makefile b/impl/algorithms/dijkstra/java/makefile similarity index 100% rename from impl/dijkstra/java/makefile rename to impl/algorithms/dijkstra/java/makefile diff --git a/impl/dijkstra/python3/dijkstra.py b/impl/algorithms/dijkstra/python3/dijkstra.py similarity index 100% rename from impl/dijkstra/python3/dijkstra.py rename to impl/algorithms/dijkstra/python3/dijkstra.py diff --git a/impl/dijkstra/python3/makefile b/impl/algorithms/dijkstra/python3/makefile similarity index 100% rename from impl/dijkstra/python3/makefile rename to impl/algorithms/dijkstra/python3/makefile diff --git a/impl/dijkstra/python3/test.py b/impl/algorithms/dijkstra/python3/test.py similarity index 100% rename from impl/dijkstra/python3/test.py rename to impl/algorithms/dijkstra/python3/test.py diff --git a/impl/dijkstra/python3/usage.py b/impl/algorithms/dijkstra/python3/usage.py similarity index 100% rename from impl/dijkstra/python3/usage.py rename to impl/algorithms/dijkstra/python3/usage.py diff --git a/impl/hull-2d/java/Hull.java b/impl/algorithms/hull-2d/java/Hull.java similarity index 100% rename from impl/hull-2d/java/Hull.java rename to impl/algorithms/hull-2d/java/Hull.java diff --git a/impl/hull-2d/java/Test.java b/impl/algorithms/hull-2d/java/Test.java similarity index 100% rename from impl/hull-2d/java/Test.java rename to impl/algorithms/hull-2d/java/Test.java diff --git a/impl/hull-2d/java/Usage.java b/impl/algorithms/hull-2d/java/Usage.java similarity index 100% rename from impl/hull-2d/java/Usage.java rename to impl/algorithms/hull-2d/java/Usage.java diff --git a/impl/hull-2d/java/makefile b/impl/algorithms/hull-2d/java/makefile similarity index 100% rename from impl/hull-2d/java/makefile rename to impl/algorithms/hull-2d/java/makefile diff --git a/impl/hull-2d/python3/hull.py b/impl/algorithms/hull-2d/python3/hull.py similarity index 100% rename from impl/hull-2d/python3/hull.py rename to impl/algorithms/hull-2d/python3/hull.py diff --git a/impl/hull-2d/python3/makefile b/impl/algorithms/hull-2d/python3/makefile similarity index 100% rename from impl/hull-2d/python3/makefile rename to impl/algorithms/hull-2d/python3/makefile diff --git a/impl/hull-2d/python3/test.py b/impl/algorithms/hull-2d/python3/test.py similarity index 100% rename from impl/hull-2d/python3/test.py rename to impl/algorithms/hull-2d/python3/test.py diff --git a/impl/hull-2d/python3/usage.py b/impl/algorithms/hull-2d/python3/usage.py similarity index 100% rename from impl/hull-2d/python3/usage.py rename to impl/algorithms/hull-2d/python3/usage.py diff --git a/impl/algorithms/kruskals/python3/kruskals.py b/impl/algorithms/kruskals/python3/kruskals.py new file mode 100644 index 0000000..805ec0f --- /dev/null +++ b/impl/algorithms/kruskals/python3/kruskals.py @@ -0,0 +1,12 @@ +def min_span_tree(graph): + ds = DisjointSets() + for e in graph: + for n in e: + ds.add(n) + out = set() + for e in sorted(graph, key = lambda e: graph[e]): + a, b = e + if ds.find(a) is not ds.find(b): + out.add(e) + ds.union(a, b) + return out diff --git a/impl/algorithms/kruskals/python3/makefile b/impl/algorithms/kruskals/python3/makefile new file mode 100644 index 0000000..b16805a --- /dev/null +++ b/impl/algorithms/kruskals/python3/makefile @@ -0,0 +1,8 @@ +.PHONY: test + +PP := ../../../structures/disjoint-sets/python3 + +SOURCES := kruskals.py test.py $(PP)/disjoint_sets.py + +test: $(SOURCES) + @PYTHONPATH=$(PP) python3 test.py diff --git a/impl/algorithms/kruskals/python3/test.py b/impl/algorithms/kruskals/python3/test.py new file mode 100644 index 0000000..886052f --- /dev/null +++ b/impl/algorithms/kruskals/python3/test.py @@ -0,0 +1,32 @@ +from kruskals import min_span_tree +from disjoint_sets import DisjointSets +import kruskals + +kruskals.DisjointSets = DisjointSets + +_graph = { + ('a', 'b'): 7, + ('a', 'd'): 5, + ('b', 'c'): 8, + ('b', 'd'): 9, + ('b', 'e'): 7, + ('c', 'e'): 5, + ('d', 'e'): 15, + ('d', 'f'): 6, + ('e', 'f'): 8, + ('e', 'g'): 9, + ('f', 'g'): 11, +} +graph = {frozenset(k): v for (k, v) in _graph.items()} + +exp = set(map(frozenset, [ + ('a', 'b'), + ('a', 'd'), + ('b', 'e'), + ('c', 'e'), + ('d', 'f'), + ('e', 'g'), +])) + +assert min_span_tree(graph) == exp +print("Pass") diff --git a/impl/algorithms/kruskals/python3/usage.py b/impl/algorithms/kruskals/python3/usage.py new file mode 100644 index 0000000..ee9eb72 --- /dev/null +++ b/impl/algorithms/kruskals/python3/usage.py @@ -0,0 +1,10 @@ +graph = { + frozenset(["a", "b"]): 10, + frozenset(["b", "c"]): 12, + frozenset(["a", "c"]): 50, +} + +tree = min_span_tree(graph) +assert frozenset(["b", "c"]) in tree +assert frozenset(["a", "c"]) not in tree +total_cost = sum(graph[e] for e in tree) diff --git a/impl/algorithms/network-flows/Ek.java b/impl/algorithms/network-flows/Ek.java new file mode 100644 index 0000000..f043e76 --- /dev/null +++ b/impl/algorithms/network-flows/Ek.java @@ -0,0 +1,47 @@ +import java.util.*; + +public class Ek { + static class Node { + public Set edges = new HashSet<>(); + + public static Edge connect(Node from, Node to, long cap) { + Edge e = new Edge(from, to, cap); + from.edges.add(e); + to.edges.add(e); + return e; + } + } + + static class Edge { + public final Node from, to; + public final long cap; + public long flow; + + public Edge(Node from, Node to, long cap) { + self.from = from; + self.to = to; + self.cap = cap; + self.flow = 0; + } + public long capTo(Edge node) { + return node.equals(from) ? flow : cap - flow; + } + public void addTo(Node to, long amt) { + flow += node.equals(from) ? -amt : amt; + } + public Node other(Node node) { + return node.equals(from) ? to : from; + } + } + + static class EkResult { + public long val; + public Set cutSrc; + } + + static + + public static EkResult ek(Set nodes, Node src, Node sink) { + + } +} diff --git a/impl/network-flows/java-junk/FlowNet.java b/impl/algorithms/network-flows/java-junk/FlowNet.java similarity index 100% rename from impl/network-flows/java-junk/FlowNet.java rename to impl/algorithms/network-flows/java-junk/FlowNet.java diff --git a/impl/network-flows/java-junk/Main.java b/impl/algorithms/network-flows/java-junk/Main.java similarity index 100% rename from impl/network-flows/java-junk/Main.java rename to impl/algorithms/network-flows/java-junk/Main.java diff --git a/impl/network-flows/java-junk/usage b/impl/algorithms/network-flows/java-junk/usage similarity index 100% rename from impl/network-flows/java-junk/usage rename to impl/algorithms/network-flows/java-junk/usage diff --git a/impl/network-flows/python3/flows.py b/impl/algorithms/network-flows/python3/flows.py similarity index 97% rename from impl/network-flows/python3/flows.py rename to impl/algorithms/network-flows/python3/flows.py index a904a32..eaa97bf 100644 --- a/impl/network-flows/python3/flows.py +++ b/impl/algorithms/network-flows/python3/flows.py @@ -22,7 +22,7 @@ class Node: s.edges = set() @staticmethod - def edge(f, t, cap): + def connect(f, t, cap): e = Edge(f, t, cap) f.edges.add(e) t.edges.add(e) diff --git a/impl/network-flows/python3/makefile b/impl/algorithms/network-flows/python3/makefile similarity index 100% rename from impl/network-flows/python3/makefile rename to impl/algorithms/network-flows/python3/makefile diff --git a/impl/algorithms/network-flows/python3/test.py b/impl/algorithms/network-flows/python3/test.py new file mode 100644 index 0000000..7c9d54d --- /dev/null +++ b/impl/algorithms/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.connect(src, a, 4) +Node.connect(src, b, 4) +Node.connect(src, c, 2) +Node.connect(a, d, 3) +Node.connect(b, e, 3) +Node.connect(c, e, 3) +Node.connect(c, f, 1) +Node.connect(d, sink, 4) +Node.connect(e, sink, 5) +Node.connect(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/algorithms/network-flows/python3/usage.py similarity index 100% rename from impl/network-flows/python3/usage.py rename to impl/algorithms/network-flows/python3/usage.py diff --git a/impl/network-flows/python3/test.py b/impl/network-flows/python3/test.py deleted file mode 100644 index d68b85d..0000000 --- a/impl/network-flows/python3/test.py +++ /dev/null @@ -1,21 +0,0 @@ -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/structures/disjoint-sets/python3/disjoint_sets.py b/impl/structures/disjoint-sets/python3/disjoint_sets.py new file mode 100644 index 0000000..32c5071 --- /dev/null +++ b/impl/structures/disjoint-sets/python3/disjoint_sets.py @@ -0,0 +1,26 @@ +class Node: + pass + +class DisjointSets(dict): + def add(self, val): + if val not in self: + self[val] = n = Node() + n.val = val + n.parent = None + n.size = 1 + + def find(self, val): + n = self[val] + while n.parent: + newp = n.parent.parent or n.parent + n.parent = newp + n = newp + return n + + def union(self, v1, v2): + r1 = self.find(v1) + r2 = self.find(v2) + if r1 != r2: + ch, p = sorted([r1, r2], key = lambda n: n.size) + ch.parent = p + p.size += ch.size diff --git a/impl/structures/disjoint-sets/python3/usage.py b/impl/structures/disjoint-sets/python3/usage.py new file mode 100644 index 0000000..86612b4 --- /dev/null +++ b/impl/structures/disjoint-sets/python3/usage.py @@ -0,0 +1,10 @@ +# Make a new disjoint sets instance +ds = DisjointSets() + +# Add singleton values to the structure +ds.add("my value") +ds.add(0) + +# Union and Find operations +ds.union("my value", 0) +assert ds.find("my value") is ds.find(0) diff --git a/latex/algorithms/dijkstra.tex b/latex/algorithms/dijkstra.tex new file mode 100644 index 0000000..17f3e4d --- /dev/null +++ b/latex/algorithms/dijkstra.tex @@ -0,0 +1,43 @@ +{ + \newcommand{\ThisImpl}{\ImplPath/dijkstra} + + \TopicHeader{Weighted Shortest Path: Dijkstra's Agorithm} + + Dijkstra's algorithm is useful for computing the shortest path between nodes in a graph where edges have nonnegative weights. + The worst-case performance of the algorithm is $O(E + V \log V)$, if the graph has $E$ edges and $V$ nodes. + + All implementations here provide as output, for each node, the following information: + \begin{itemize} + \item whether the node was reachable from the search root + \item the shortest distance between the root and the node + \item the previous node along the shortest path, i.e. the node that was being explored when this node was first found + \end{itemize} + Note that the path of nodes from the root to any reachable node can be computed by following the previous-node links iteratively until the search root is reached. + + The implementations use directed graphs, so in order to emulate searching an undirected graph, two directed edges going in opposite directions should be made for each edge in the desired undirected graph. + + \TopicSubHeader{Python 3} + + \inputminted{python}{\ThisImpl/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}{\ThisImpl/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. + + \TopicSubHeader{Java} + + \centerline{\texttt{Graph.java}} + \inputminted{java}{\ThisImpl/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}{\ThisImpl/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/latex/algorithms/hull-2d.tex b/latex/algorithms/hull-2d.tex new file mode 100644 index 0000000..2f6f010 --- /dev/null +++ b/latex/algorithms/hull-2d.tex @@ -0,0 +1,30 @@ +{ + \newcommand{\ThisImpl}{\ImplPath/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 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. + + \TopicSubHeader{Java} + + \centerline{\texttt{Hull.java}} + \inputminted{java}{\ThisImpl/java/Hull.java} + + This may be used as follows: + + \inputminted{java}{\ThisImpl/java/Usage.java} + + \TopicSubHeader{Python 3} + + \inputminted{python}{\ThisImpl/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}{\ThisImpl/python3/usage.py} +} diff --git a/latex/algorithms/kruskals.tex b/latex/algorithms/kruskals.tex new file mode 100644 index 0000000..74b9a4a --- /dev/null +++ b/latex/algorithms/kruskals.tex @@ -0,0 +1,42 @@ +{ + \newcommand{\ThisImpl}{\ImplPath/kruskals} + + \TopicHeader{Minimum Spanning Tree: Kruskal's Algorithm} + + Kruskal's algorithm finds a spanning tree in a weighted undirected graph (or a collection of + spanning trees if the graph isn't connected) whose total edge cost is minimal. The algorithm + runs in $O(E \log V)$ (or equivalently $O(E \log E)$) time, where $V$ is the number of + vertices and $E$ the number of edges in the graph. + + \TopicSubHeader{Python 3} + + \inputminted{python}{\ThisImpl/python3/kruskals.py} + + \paragraph{Note} This implementation uses the disjoint sets type defined on page + \pageref{structures-disjoint-sets-python3}. + + The input for this algorithm is a graph, and in this implementation the graph is + represented by a dictionary mapping edges to their costs. The cost values are just + numbers, but the edges are iterables of two nodes. Because the edges need to be used as + dictionary keys, they need to be hashable, and because the graph is undirected the + programmer should be careful not to accidentally look up the edge $(b, a)$ when only + $(a, b)$ is present. In Python, the simplest way to accomplish this is to use immutable + sets, so that the order in which the two nodes are listed within an edge doesn't make a + difference. Tuples also work, but this approach requires the programmer to be consistent + about the order of nodes within each edge. + + The nodes can be of any type, as long as hashing and equality behave correctly. Many + primitive types will work fine, as well as typical class types you define. + + The algorithm returns a set of edges, that is, a subset of the keys in the input + dictionary. The costs of the edges can then be looked up using the graph dictionary + passed to the implementation. + + Here's a simple usage example: + + \inputminted{python}{\ThisImpl/python3/usage.py} + + \TopicSubHeader{Java} + + Coming soon\ldots +} diff --git a/latex/algorithms/network-flows.tex b/latex/algorithms/network-flows.tex new file mode 100644 index 0000000..7806098 --- /dev/null +++ b/latex/algorithms/network-flows.tex @@ -0,0 +1,26 @@ +{ + \newcommand{\ThisImpl}{\ImplPath/network-flows} + + \TopicHeader{Network Flows: Edmonds--Karp} + + Network flows algorithms find the maximum flow through and the minimum cut of a flow network. + This terminology and relevant algorithms are covered in Algorithms (CS 280) at Oberlin. + + The implementations here use the Edmonds--Karp algorithm on flow networks with integer capacities. + The time complexity of the algorithm is $O\left( VE^2 \right)$, where $V$ and $E$ are the number of vertices and edges in the network, respectively. + + \TopicSubHeader{Java} + + Coming soon... + + \TopicSubHeader{Python 3} + + \inputminted{python}{\ThisImpl/python3/flows.py} + + To use the code: + + \inputminted{python}{\ThisImpl/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/latex/structures/disjoint-sets.tex b/latex/structures/disjoint-sets.tex new file mode 100644 index 0000000..768a125 --- /dev/null +++ b/latex/structures/disjoint-sets.tex @@ -0,0 +1,25 @@ +{ + \newcommand{\ThisImpl}{\DsImplPath/disjoint-sets} + + \TopicHeader{Disjoint Sets} + + This data structure is a forest of disjoint sets with path halving and union by size. The + \textit{union} and \textit{find} operations are essentially constant-time amortized. + + \TopicSubHeader{Python 3} \label{structures-disjoint-sets-python3} + + \inputminted{python}{\ThisImpl/python3/disjoint_sets.py} + + Basic usage: + + \inputminted{python}{\ThisImpl/python3/usage.py} + + The values in the sets may be of any type, as long as they are hashable. The data + structures uses hashing and equality testing to locate nodes. Generally, this means you + can safely use immutable built-in types or your own custom object types as values in the + sets. + + \TopicSubHeader{Java} \label{structures-disjoint-sets-java} + + Coming soon\ldots +} diff --git a/makefile b/makefile index af0e338..0e6560b 100644 --- a/makefile +++ b/makefile @@ -1,5 +1,5 @@ # These are more than the files we really need to depend on, but keep things simple. -ALG_FILES := $(shell find algorithms -type f) +ALG_FILES := $(shell find latex -type f) IMPL_FILES := $(shell find impl -type f) BUILD_CMD := ( cd output && pdflatex -shell-escape ../doc.tex ) diff --git a/todo b/todo index 903d8cc..2bdb5a9 100644 --- a/todo +++ b/todo @@ -1,5 +1,5 @@ -- add tests for implementations and automate - implement configurable sections (select specific algorithms) +- implement configurable languages - copy useful stuff from https://en.wikibooks.org/wiki/Algorithm_implementation - DFS, BFS, Bellman Ford, area of polygons, minimum spanning tree, brute force TSP - canonical problems (24: ecna17 twentyfour, coin problem) diff --git a/util/run_all_tests.py b/util/run_all_tests.py index 148e18b..2caeb6c 100644 --- a/util/run_all_tests.py +++ b/util/run_all_tests.py @@ -1,7 +1,7 @@ import subprocess from pathlib import Path -for alg in Path('impl').iterdir(): +for alg in Path('impl', 'algorithms').iterdir(): if alg.is_dir(): for lang in alg.iterdir(): if lang.is_dir() and lang.joinpath('makefile').exists(): -- 2.30.2