Tag : algorithms
|Simple graph algorithms with a modular design||Alessandro Presta||python||algorithms breadth depth directed first graph object oriented python search theory undirected visit||
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).
|April 20, 2011|
|Converts from decimal to any base ( between 2 and 26 )||Shashwat Anand||python||algorithms base||
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.
|February 24, 2011|
|Compare algorithms for heapq.smallest||Raymond Hettinger||python||algorithms benchmark heaps performance||
General purpose technique for counting comparisons in various searching and sorting applications.
|February 12, 2011|
|Fibonacci Data Compression||FB36||python||algorithm algorithms data_compression||
Data compression via Fibonacci encoding.
|January 28, 2011|
|Binary Search Tree||FB36||python||algorithm algorithms datastructures||
Binary Search Tree.
|January 26, 2011|
|Python Binary Search Tree||Edward Loper||python||algorithms maximum minimum search sort||
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).
|January 9, 2011|
|Aggregates using groupby, defaultdict and Counter||N N||python||algorithms||
How to emulate SQL aggregate functions AVG, COUNT, MAX, MIN and SUM on csv type data files using tools from the standard library.
|January 7, 2011|
|A-star Shortest Path Algorithm||FB36||python||algorithm algorithms graph routes||
A-star (A*) Shortest Path Algorithm
|December 26, 2010|
|An interval mapping data structure||Matteo Dell'Amico||python||algorithms interval mapping||
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.
|December 23, 2010|
|Dijkstra Shortest Path Algorithm||FB36||python||algorithm algorithms graph routes||
Dijkstra shortest path algorithm.
|December 20, 2010|
|Shannon-Fano Data Compression||FB36||python||algorithm algorithms data_compression||
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.)
|December 16, 2010|
|Huffman Data Compression||FB36||python||algorithm algorithms datastructures data_compression||
Huffman encoding (data compression). Usage: huffman -i [input file name] -o [output file name] [-e|d]
|December 1, 2010|
|Hopfield Artificial Neural Network||FB36||python||ai algorithm algorithms artificial_intelligence neural_network||
(Discrete (Binary)) Hopfield Artificial Neural Network (ANN).
For more info see:
|November 14, 2010|
|Eight queen problem||Thomas Lehmann||python||algorithms queen||
|October 23, 2010|
|Dijkstra's algorithm for shortest paths||poromenos||python||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.
|August 2, 2010|