Package pygraphlib
[show private | hide private]
[frames | no frames]

Package pygraphlib

pygraphlib - a python graph library

pygraphlib is a python based graph (network) representation and manipulation package. The library includes methods for constructing and traversing graphs, shortest path alogrithms and many others. This library also allows you to create files that can be visualized via graphviz program..

The pygraphlib package contains the following modules:


In this representation each graph is characterezied by G(V,E), where V is the number of nodes and E is the number of edges. Both the nodes and the edges are labeled. This means that there is a unique id associated with them. For the nodes these labels are usually numbers or strings but they can potentially be any hashable python object. For the edges the labels are automatically generated integer numbers. The first edge that you create will be edge 0, the second will be edge 1 etc. In many cases you won't care about the edge labels but they'll come in very handy whenever you need to repeatedly perform operations on a group of edges.

Example usage

>>> from pygraphlib import pygraph
>>> # create a directed graph
>>> graph = pygraph.DGraph()
>>> # adding an edge also creates the nodes for it (this behavior may be turned off)
>>> # the default weight is 1
>>> graph.add_edge('New York', 'Chicago', wt=200)
>>> graph.add_edge('New York', 'Detroit', wt=100)
>>> graph.add_edge('Dallas', 'Chicago', wt=350)
>>> graph.add_edge('Detroit', 'Chicago', wt=50)
>>> graph.add_edge('Chicago', 'San Francisco', wt=200)
>>> graph.add_edge('Chicago', 'Los Angeles', wt=250)
>>> graph.add_edge('San Francisco', 'Los Angeles', wt=50)
>>> graph.add_edge('Los Angeles', 'Detroit', wt=250)
>>> graph.add_edge('Los Angeles', 'Dallas', wt=150)
>>> graph.add_edge('Dallas', 'Miami', wt=100)
>>> graph.add_edge('Miami', 'New York', wt=80)
>>> graph.add_edge('Miami', 'Detroit',  wt=50, data='Delta Airlines')
>>> print graph
DGraph: 7 nodes, 12 edges

>>> node_list = graph.node_list()
>>> node_list.sort()
>>> # every node has a label
>>> print node_list
['Chicago', 'Dallas', 'Detroit', 'Los Angeles', 'Miami', 'New York', 'San Francisco']

>>> # but also every edge has a label (generated internally)
>>> print graph.edge_list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

>>> # the airports with a flight to Chicago
>>> print graph.inc_nbrs('Chicago')
['New York', 'Dallas', 'Detroit']

>>> # the airports that you can visit from Chicago
>>> print graph.out_nbrs('Chicago')
['San Francisco', 'Los Angeles']

>>> # all the edges that lead into Detroit
>>> edges = graph.inc_edges('Detroit')
>>> print edges
[1, 7, 11]

>>> # the edge between Miami and Detroit
>>> edge = graph.get_edge('Miami', 'Detroit')
>>> print edge

>>> # the data associated with this edge
>>> print graph.get_edge_data(edge)
Delta Airlines

>>> # save the graph into a file
>>> pygraph.to_file(graph, 'airports.dat')
>>> # we can now reload it from the file
>>> graph = pygraph.from_file('airports.dat')
>>> print graph
DGraph: 7 nodes, 12 edges
We may visualize the graph
>>> from pygraphlib import pydot
>>> dot = pydot.Dot(graph)
>>> # simple output
>>> dot.save_image('airports1.gif', mode='gif')
>>> # for a bit fancier output label each edge with its weight
>>> for edge in graph.edge_list():
...     head, tail = graph.edge_nodes(edge)
...     dot.set_edge_style(head, tail, label=graph.get_edge_wt(edge))
>>> dot.save_image('airports2.gif', mode='gif')

Here are the outputs generated by the code above: airports1.gif and airports2.gif

Using graph algorithms:
>>> from pygraphlib import algo
>>> # the cheapest route from Dallas to Chicago costs $200
>>> algo.shortest_path(graph, 'Dallas', 'Chicago')
[('Dallas', 0.0), ('Miami', 100.0), ('Detroit', 150.0), ('Chicago', 200.0)]

>>> # if we cannot fly through Miami
>>> graph.hide_node('Miami')
>>> # then the cheapest route from Dallas to Chicago costs $350
>>> algo.shortest_path(graph, 'Dallas', 'Chicago')
[('Dallas', 0.0), ('Chicago', 350.0)]

>>> graph.restore_all_nodes()
>>> # the five closest airports that can be reached from Dallas
>>> algo.bfs(graph, 'Dallas')[:5]
[('Dallas', 0), ('Chicago', 1), ('Miami', 1), ('San Francisco', 2), ('Los Angeles', 2)]

>>> # the five closest airports that can fly into Dallas
>>> algo.bfs(graph, 'Dallas', forward=False)[:5]
[('Dallas', 0), ('Los Angeles', 1), ('Chicago', 2), ('San Francisco', 2), ('New York', 3)]
Above we use the term closest to mean fewest connections (hops).


This library has started out as an extension to the graph_lib module written by Nathan Denny but over time it has been significantly optimized and expanded. The API is loosely modeled after the LEDA (Library of Efficient Datatypes) graph representation.

Author: Istvan Albert

License: MIT License


  • algo: Graph algorithms
  • pydot: The pydot module provides a simple interface to the file format used in the graphviz program.
  • pygraph: Base Graph class
  • util: Utility classes and functions

Variable Summary
str __version__ = '0.6.0'

Variable Details



Generated by Epydoc 2.1 on Wed Jan 5 09:50:42 2005