# 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

Developer: Alessandro Presta

License: Freeware

Operating System: Windows

all are required fields

# Related Scripts Download

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

** Developer:** planet-source-code.com

** License:** Freeware

** Operating System:** All

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

** Developer:** planet-source-code.com

** License:** Freeware

** 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:** code.activestate.com

** License:** Freeware

** Operating System:** All

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

** Developer:** planet-source-code.com

** License:** Freeware

** Operating System:** All

This script demonstrates a 2D boids simulation.

** Developer:** code.activestate.com

** License:** Freeware

** Operating System:** All

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

** Developer:** code.activestate.com

** License:** Freeware

** Operating System:** All

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

** Developer:** code.activestate.com

** License:** Freeware

** Operating System:** All

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

** Developer:** Alessandro Presta

** License:** Freeware

** 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:** Raphael Jolivet

** License:** Freeware

** Operating System:** Windows