pygraphlib.algo

Package pygraphlib :: Module algo

[show private | hide private]

Module pygraphlib.algo

Graph algorithms

This module contains a collection of functions that operate on graphs.

Function Summary
	`bfs(graph, start, end, forward)` Collects and returns a list of nodes in some breadth first order.
	`dfs(graph, start, end)` Collects and returns a list of nodes in some depth first order.
	`dijkstra(graph, start, end)` Dijkstra's algorithm for shortest paths
	`primpq(graph, start)` Minimum weight spanning tree with Prim's algorithm using priority queues.
	`shortest_path(graph, start, end)` Returns a single shortest path from the given start node to the given end node.
	`_dfs_full(graph, start, end, preind, postind)` Returns a generic class that stores as its attributes `dinfo.preord` and `dinfo.prostord` dictionaries with the preorder and postorder values keyed by node.
	`_dfs_rec(graph, start, end, dinfo)` The recursive element of the traversal

Function Details

bfs(graph, start, end=None, forward=True)

Collects and returns a list of nodes in some breadth first order. The forward parameter specifies wether the traversal operates over outgoing (c{forward=True}) or incoming (forward=False) edges. Returns a list of tuples where the first value is the node label the second value is the hop value.

>>> from pygraphlib import pygraph, algo
>>> edges = [ (1,2), (2,3), (3,4), (4,6), (6,7), (3,5), (4,5), (7,1), (2,5), (5,7) ]
>>> graph = pygraph.from_list(edges)
>>> print graph
DGraph: 7 nodes, 10 edges

>>> # breadth first search starting at node 4
>>> print algo.bfs(graph, 4)
[(4, 0), (6, 1), (5, 1), (7, 2), (1, 3), (2, 4), (3, 5)]

>>> # breadth first search starting at node 1 and stopping at node 7
>>> print algo.bfs(graph, 1, 7)
[(1, 0), (2, 1), (3, 2), (5, 2), (4, 3), (7, 3)]

The list of tuples is composed by the node label and the hop value at which the node has been encountered. Above node 1 was at 0 hops, node 2 was one hop away, nodes 5 and 3 were three hops away from the start node etc. Whenever the wt associated with each edge is 1 (default value) then it corresponds to the shortest distance from the start node.

dfs(graph, start, end=None)

Collects and returns a list of nodes in some depth first order. For more details see the algo.bfs function.

>>> from pygraphlib import pygraph, algo
>>> edges = [ (1,2), (2,3), (3,4), (4,6), (6,7), (3,5), (4,5), (7,1), (2,5), (5,7) ]
>>> graph = pygraph.from_list(edges)
>>> print graph
DGraph: 7 nodes, 10 edges

>>> # breadth first search starting at node 1
>>> print algo.dfs(graph, 1)
[(1, 0), (2, 1), (3, 2), (4, 3), (6, 4), (7, 5), (5, 6)]

dijkstra(graph, start, end=None)

Dijkstra's algorithm for shortest paths

by David Eppstein, UC Irvine, 4 April 2002, obtained from http://www.ics.uci.edu/~eppstein/161/python/ also available as Cookbook Recipe 119466

Finds the shortest paths from the start node to all nodes nearer than or equal to the end node.

Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive. This code does not verify this property for all edges (only the edges examined until the end vertex is reached), but will correctly compute shortest paths even for some graphs with negative edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.

primpq(graph, start)

Minimum weight spanning tree with Prim's algorithm using priority queues.

contributed by Robert C Kirby University of Chicago, September 2004

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. The minimum weight spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.

This function assumes that graph is undirected and weighted; that is, for each edge (u,v,w), (v,u,w) is also an edge of the graph. start is the index of the vertex at which we start.

shortest_path(graph, start, end)

Returns a single shortest path from the given start node to the given end node. The input has the same conventions as algo.dijkstra. The output is a list of the nodes in order along the shortest path.

>>> from pygraphlib import pygraph, algo
>>> edges = [ (1,2), (2,3), (3,4), (4,6), (6,7), (3,5), (4,5), (7,1), (2,5), (5,7) ]
>>> graph = pygraph.from_list(edges)
>>> print graph
DGraph: 7 nodes, 10 edges

>>> # by default the wt of each edge is set to 1
>>> # shortest path between 1 and 7
>>> print shortest_path(graph, 1, 7)
[(1, 0.0), (2, 1.0), (5, 2.0), (7, 3.0)]

>>> # make the edge from 2 to 5 more costly
>>> edge = graph.get_edge(2,5)
>>> graph.set_edge_wt(edge, 10)
>>> # now the shortest path between 1 and 7 is different
>>> print shortest_path(graph, 1, 7)
[(1, 0.0), (2, 1.0), (3, 2.0), (5, 3.0), (7, 4.0)]

_dfs_full(graph, start, end, preind=0, postind=0)

Returns a generic class that stores as its attributes dinfo.preord and dinfo.prostord dictionaries with the preorder and postorder values keyed by node. This function is meant to be used by other algoritms and not be directly called.

_dfs_rec(graph, start, end, dinfo)

The recursive element of the traversal

Generated by Epydoc 2.1 on Wed Jan 5 09:38:28 2005

http://epydoc.sf.net