Popular recipes tagged "graph"

Simple Graph library (Python)

2015-12-22T10:49:59-08:00

Python recipe 579141 by Narayana Chikkam (graph). Revision 2.

A collection of generally used Graph Algorithms in one place with simple constructs.

Simple Bash Text Mode Sine Curve Generator. (Bash)

2014-08-12T20:57:39-07:00

Bash recipe 578921 by Barry Walker (apple, bash, cygwin, graph, linux, macbook_pro, text). Revision 2.

This bash script is a taster for a kids level, audio, text mode, sweep generator. The code just creates a single cycle of a quantised sine curve inside an 80 x 24 bash terminal. This will be the calculator for a sinewave sweep generator from about 50Hz the 12KHz... The code tells you more and the display is in comments at the end...

Strongly connected components of a directed graph. (Python)

2013-04-03T19:30:32-07:00

Python recipe 578507 by Mark Dickinson (connected, directed, graph, strong, tarjan). Revision 3.

Two linear-time algorithms for finding the strongly connected components of a directed graph. strongly_connected_components_tree implements (a variant of) Tarjan's well-known algorithm for finding strongly connected components, while strongly_connected_components_path implements a path-based algorithm due (in this form) to Gabow.

Edit: I added an iterative function strongly_connected_components_iterative; this is a direct conversion of strongly_connected_components_path into iterative form. It's therefore safe to use on high-depth graphs, without risk of running into Python's recursion limit.

graph (Python)

2015-10-15T21:33:32-07:00

Python recipe 578615 by user (abstract_base_class, datastructures, graph). Revision 4.

Abstract Graph Class: A Graph is a very abstract and powerful data structure to hold many different kinds of data relationships.

topological sorting again (Python)

2013-03-06T19:21:11-08:00

Python recipe 578406 by yota (algorithm, graph, python3, sort, topological). Revision 9.

Topological sorting is the answer to the following question : in a direct acyclic graph, how can I pick up nodes "in order", such as upstream nodes are always before downstream ones ? Many solutions may exists, many algorithms too.

Alas, it seems I'm too stupid to understand already proposed recipes on topological sorting. Hopefully I do grasp the "write once, read many" concept.

Here, you will find a plain algorithm, optimized only for code clarity, of a topological sorting for direct acyclic graphs, implemented in python from the pseudo code found on wikipedia:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Only tested with python3.2, should work with other versions. Be careful, code indented with tabs, since space is evil è_é

A-star Shortest Path Algorithm (C++)

2010-12-25T23:36:35-08:00

C++ recipe 577457 by FB36 (algorithm, algorithms, game, graph, graphs, routes). Revision 4.

A-star (A*) is a shortest path algorithm widely used for RTS games, GPS navigation etc.

Simple Dijkstra Algorithm (Python)

2012-06-08T02:20:18-07:00

Python recipe 578156 by Filippo Squillace (graph). Revision 3.

The algorithm uses the priority queue version of Dijkstra and return the distance between the source node and the others nodes d(s,i).

Experiment with Kaprekar's routine (Python)

2011-06-12T03:29:01-07:00

Python recipe 577749 by Raymond Hettinger (6174, dot, graph, kaprekar). Revision 2.

Explore the story behind the mysterious number 6174. Generate all possible chains leading to 6174, show their length and their patterns of convergence.

A-star Shortest Path Algorithm (Python)

2010-12-26T08:31:16-08:00

Python recipe 577519 by FB36 (algorithm, algorithms, graph, routes). Revision 3.

A-star (A*) Shortest Path Algorithm

Dijkstra Shortest Path Algorithm (Python)

2011-10-29T18:46:53-07:00

Python recipe 577506 by FB36 (algorithm, algorithms, graph, routes). Revision 5.

Dijkstra shortest path algorithm.

Simple graph algorithms with a modular design (Python)

2011-04-21T13:40:32-07:00

Python recipe 577668 by jimmy2times (algorithms, breadth, depth, directed, first, graph, object, oriented, python, search, theory, undirected, visit). Revision 7.

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).

Mandelbrot trajectories (Python)

2011-04-06T18:18:48-07:00

Python recipe 577642 by Kaushik Ghose (graph, interactive, matplotlib, plotting, widget).

An interactive graph to plot the trajectory of points on and off the mandelbrot set. Illustrates the use of sliders in matplotlib

Chaotic Function Analysis Graph (Python)

2010-12-10T03:31:50-08:00

Python recipe 577487 by FB36 (chaos, graph, graphics, math, mathematics). Revision 2.

There are 3 chaotic functions to graph as examples.

Graph of function (0) is a curve. Graph of function (1) is a group of lines. (Both are Xn+1 = f(Xn) type functions.)

Graph of function (2) on the other hand is a plane. (It is Xn+1 = f(Xn, Xn-1) type function.)

These mean there is a simple relationship between the previous and next X values in (0) and (1). (Next X value can always be predicted from the previous X value by using the graph of the function w/o knowing the function itself.) But (2) does not have a discernible relationship. (No prediction possible!) So (2) is clearly more chaotic than others. (I think it could be used as a Pseudo-Random Number Generator (PRNG).)

tgraph - Simple ASCII graphing utility (Python)

2011-07-28T21:13:23-07:00

Python recipe 577077 by Drew Gulino (ascii, graph, log, sysadmin, tail, unix).

Takes a stream of numbers and outputs simple ASCII graphs of those numbers

dfs and bfs graph traversal (Python)

2013-06-28T09:59:38-07:00

Python recipe 576723 by bruce wernick (algorithm, graph).

Very simple depth first search and breath first graph traversal. This is based on the find_path written by Guido van Rossum.

Creating fake data using numpy (Python)

2009-08-07T09:22:34-07:00

Python recipe 576870 by tat.wright (data, fake, gaussian, graph, histogram, normal, sample_data).

Create a deliberately bad normal distribution for sample data - varying the badness, mean, standard deviation and range of results shown.

Covert color space from HSV to RGB and RGB to HSV (Python)

2008-11-04T02:13:01-08:00

Python recipe 576554 by Victor Lin (color, color_space, convert, graph).

Functions for converting bwtween RGB and HSV color space.