Home  Trees  Index  Help 

Package pygraphlib ::
Module algo


Graph algorithms
This module contains a collection of functions that operate on graphs.Function Summary  

Collects and returns a list of nodes in some breadth first order.  
Collects and returns a list of nodes in some depth first order.  
Dijkstra's algorithm for shortest paths  
Minimum weight spanning tree with Prim's algorithm using priority queues.  
Returns a single shortest path from the given start node to the given end node. 
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 thealgo.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 asalgo.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)] 
Home  Trees  Index  Help 

Generated by Epydoc 2.1 on Wed Jan 5 09:38:28 2005  http://epydoc.sf.net 