The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.

A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex. This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).

Any valid class of graph must implement the interface defined by AbstractGraph.

A generic search algorithm takes as input a graph, source and target vertices and a queue. A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.

Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).

This function takes in any base-10 integer and returns the string representation of that number in its specified base-n form. The code was inspired from http://code.activestate.com/recipes/65212-convert-from-decimal-to-any-base-number/ , thereby improving upon it.

General purpose technique for counting comparisons in various searching and sorting applications.

Data compression via Fibonacci encoding.

Binary Search Tree.

A data structure that holds a sorted collection of values, and supports efficient insertion, deletion, sorted iteration, and min/max finding. Values may sorted either based on their natural ordering, or on a key function (specified as an argument to the search tree's constructor). The search tree may contain duplicate values (or multiple values with equal keys) -- the ordering of such values is undefined.

This implementation was made with efficiency in mind. In particular, it is more than twice as fast as the other native-Python implementations I tried (which all use objects to store search tree nodes).

See also: http://en.wikipedia.org/wiki/Binary_search_tree, http://en.wikipedia.org/wiki/A*_search_algorithm

How to emulate SQL aggregate functions AVG, COUNT, MAX, MIN and SUM on csv type data files using tools from the standard library.

A-star (A*) Shortest Path Algorithm

This structure is a kind of dictionary which allows you to map data intervals to values. You can then query the structure for a given point, and it returns the value associated to the interval which contains the point. Boundary values don't need to be an integer.

In this version, the excellent blist library by Daniel Stutzbach is used for efficiency. By using the collections.MutableMapping abstract base class, the whole signature of mappings is supported.

Dijkstra shortest path algorithm.

Shannon-Fano Data Compression. It can compress any kind of file up to 4 GB.

(But trying to compress an already compressed file like zip, jpg etc. can produce a (slightly) larger file though. Shannon-Fano is not the best data compression algorithm anyway.)

Huffman encoding (data compression). Usage: huffman -i [input file name] -o [output file name] [-e|d]

(Discrete (Binary)) Hopfield Artificial Neural Network (ANN).

For more info see:

http://en.wikipedia.org/wiki/Hopfield_net

http://www.scholarpedia.org/article/Hopfield_network

Task:

• Think of a chess field 8x8.
• Place 8 queens in a way that no one menaces another one.

Intention:

• Writing an algorithm to provide all solutions
• Adjusting the algorithm in a way that it can handle chess fields by other sizes n x n.

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.