Uses a recursively called simple generator (with the same arguments as the outer call!) to traverse a tree in breadth first order.
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...
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...
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...
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...
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...
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...
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...
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.
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... |