Simple graph algorithms with a modular design

Category: Python - Miscellaneous

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). Date: 22 May, 2012


Algorithms - Breadth - Depth - Directed - First - Graph - Object - Oriented - Python - Search - Theory - Undirected - Visit

Homepage: http://code.activestate.com/recipes/577668-simple-graph-algorithms-with-a-modular-design/?in=lang-python

Developer: Alessandro Presta

License: Freeware

Operating System: Windows

Add a Comment

all are required fields

     
What do you think of this resource?

Select Your Rate:

Votes:0

 

Related Scripts Download

CPU scheduling algorithms simulates the scheduling of a CPU, calculate waiting time & average, turnaround time,etc.

developer Developer: planet-source-code.com
license License: Freeware
operating systems Operating System: All


This code is a representation of the First In First Out Algorithm in Page Replacement Algorithms.

developer Developer: planet-source-code.com
license License: Freeware
operating systems Operating System: All


This script implements the three standard relational join algorithms: nested loops join, hash join, and merge join, using the iterator algebra support in Python.

developer Developer: code.activestate.com
license License: Freeware
operating systems Operating System: All


This code contains all the common sorting/searching algorithms, all with comments.

developer Developer: planet-source-code.com
license License: Freeware
operating systems Operating System: All


This script demonstrates a 2D boids simulation.

developer Developer: code.activestate.com
license License: Freeware
operating systems Operating System: All


This script presents two approaches to generate all combination of elements from a number of sets.

developer Developer: code.activestate.com
license License: Freeware
operating systems Operating System: All


The List monad in Haskell has many uses, including parsing and nondeterministic algorithms.

developer Developer: code.activestate.com
license License: Freeware
operating systems Operating System: All


A simple decorator that helps define abstract methods: when such a method is called, an appropriate exception is raised.

developer Developer: Alessandro Presta
license License: Freeware
operating systems Operating System: Windows


Here is a handy script that uses the simplex algorithm to compute an optimum list of refunds (for example, after a trip with shared expenses with friends).

developer Developer: Raphael Jolivet
license License: Freeware
operating systems Operating System: Windows