Popular recipes by David Eppstein

Generator for integer partitions (Python)

2003-08-27T14:02:53-07:00

Python recipe 218332 by David Eppstein (algorithms).

A "partition" is a way of representing a given integer as a sum of zero or more positive integers, e.g. the partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, and 4. This recipe uses simple generators recursively to produce a stream of all partitions of its argument. Each partition is represented as a sorted list of the numbers to be summed, e.g. [1,1,1,1], [1,1,2], [2,2], [1,3], [4].

Dijkstra's algorithm for shortest paths (Python)

2002-04-04T12:38:22-08:00

Python recipe 119466 by David Eppstein (algorithms).

Dijkstra(G,s) finds all shortest paths from s to each other vertex in the graph, and shortestPath(G,s,t) uses Dijkstra to find the shortest path from s to t. Uses the priorityDictionary data structure (Recipe 117228) to keep track of estimated distances to each vertex.

Breadth first traversal of tree (Python)

2003-10-31T15:34:40-08:00

Python recipe 231503 by David Eppstein (algorithms). Revision 2.

Uses a recursively called simple generator (with the same arguments as the outer call!) to traverse a tree in breadth first order.

LaTeX codec (Python)

2003-11-13T23:19:20-08:00

Python recipe 252124 by David Eppstein (text).

Codec for converting unicodes to LaTeX markup and vice versa.

Maximum cardinality matching in general graphs (Python)

2003-09-12T21:54:02-07:00

Python recipe 221251 by David Eppstein (algorithms). Revision 2.

This is an implementation of Edmonds' blossom-contraction algorithm for maximum cardinality matching in general graphs. It's maybe a little long and complex for the recipe book, but I hope it will spare someone else the agony of implementing it themselves.

Range minima and least common ancestors (Python)

2003-11-13T23:10:41-08:00

Python recipe 252123 by David Eppstein (algorithms).

Data structures for solving the following two problems:

Range minimization: given an array X of data, quickly find min(X[i:j]) for different ranges i:j.
Least common ancestors: given a tree, quickly find the lowest tree node that is an ancestor of all of a given set of nodes.

Both problems are solved by data structures that take linear time and space to set up, after which queries can be answered in constant time.

Self-recursive generators (Python)

2003-09-13T15:06:06-07:00

Python recipe 221457 by David Eppstein (algorithms).

For a function without arguments, calling itself recursively is a quick way to get into an infinite loop. But for a generator, it can actually be useful...here are some simple numerical examples.

Sieve of Eratosthenes (Python)

2002-03-01T18:21:25-08:00

Python recipe 117119 by David Eppstein (algorithms). Revision 2.

Computes an infinite sequence of primes using simple generators. A Python dictionary is used to mark multiples of the generated primes, according to the Sieve of Eratosthenes.

Knuth-Morris-Pratt string matching (Python)

2002-03-01T23:49:23-08:00

Python recipe 117214 by David Eppstein (search).

This is an implementation of the Knuth-Morris-Pratt algorithm for finding copies of a given pattern as a contiguous subsequence of a larger text. Since KMP accesses the text only sequentially, it is natural to implement it in a way that allows the text to be an arbitrary iterator. After a preprocessing stage which takes time linear in the length of the pattern, each text symbol is processed in constant amortized time.

Hopcroft-Karp bipartite matching (Python)

2002-04-27T16:53:22-07:00

Python recipe 123641 by David Eppstein (algorithms).

Takes as input a bipartite graph in a variation of Guido van Rossum's dictionary-of-lists format, and outputs both a maximum matching (largest possible set of nonadjacent edges) and a maximum independent set (largest possible set of nonadjacent vertices). The running time in the worst case is O(E sqrt(V)) but for many graphs it runs faster due to doing fewer than the worst case number of iterations.

Priority dictionary (Python)

2002-03-08T22:09:16-08:00

Python recipe 117228 by David Eppstein (algorithms).

This data structure acts almost like a dictionary, with two modifications: First, D.smallest() returns the value x minimizing D[x]. For this to work correctly, all values D[x] stored in the dictionary must be comparable. Second, iterating "for x in D" finds and removes the items from D in sorted order. Each item is not removed until the next item is requested, so D[x] will still return a useful value until the next iteration of the for-loop.

Convex hull and diameter of 2d point sets (Python)

2003-10-16T18:44:57-07:00

Python recipe 117225 by David Eppstein (algorithms). Revision 2.

Returns the convex hull (separated into upper and lower chains of vertices) and the diameter (farthest pair of points), given input consisting of a list of 2d points represented as pairs (x,y). The convex hull algorithm is Graham's scan, using a coordinate-based sorted order rather than the more commonly seen radial sorted order. A rotating calipers algorithm generates candidate pairs of vertices for the diameter calculation. Care was taken handling tricky cases such as pairs of points with the same x-coordinate and colinear triples of points.

Dendrogram drawing (Python)

2002-07-13T21:17:10-07:00

Python recipe 139422 by David Eppstein (text).

This recipe draws a dendrogram (horizontal format used for evolutionary trees), as ASCII text, given as input a binary tree in the form of a tuple for each tree node. Tree leaves can be any Python object other than a length-2 tuple, and are converted to strings in the output. Tree nodes at the same distance from the root will line up at the same column, with the distance between tree levels controlled by an optional "sep" parameter. The algorithm works by a straightforward inorder traversal, keeping some simple data structures to keep track of the tree edges that need to be drawn on each output line. Its output is via print statements but it could easily be modified to send its output lines to any other kind of stream.

SMAWK totally monotone matrix searching algorithm (Python)

2002-03-17T18:04:31-08:00

Python recipe 117244 by David Eppstein (algorithms).

This algorithm takes as input a function for computing matrix values, and searches for the position of maximum value in each row. The matrix must satisfy the "totally monotone" property: in each submatrix (in particular each 2x2 submatrix) the positions of the maxima must move leftward as you go down the rows. The algorithm uses this property to greatly reduce the number of matrix elements evaluated, compared to a naive algorithm that explicitly constructs the matrix.

As a simple example, we apply the algorithm to finding nearest neighbors in B for each point in A, where B may be distributed arbitrarily in space but the points of A lie along a single line. Using SMAWK for this problem takes only linear time if the input is already sorted.