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..

• pygraph implements the pygraph.DGraph and pygraph.UGraph classes that represent directed and undirected graphs. The module also provides convenience functions that can create graphs from list and files.
• algo implements algorithms that operate on graphs:
  • bfs, dfs - breadth first and depth first traversals
  • primpq - minimum weight spanning tree with Prim's algorithm
  • shortest_path - shortest path finding with dijkstra's algorithm
• pydot allows you to display graphs via graphviz.

Terminology

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
11

>>> # 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

>>> 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

>>> 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)]

History

Author: Istvan Albert

License: MIT License

:

• Reka Albert
• Robert C Kirby