1 ''' 2 altgraph - a python graph library 3 ================================= 4 5 altgraph is a fork of `graphlib <http://pygraphlib.sourceforge.net>`_ tailored 6 to use newer Python 2.3+ features, including additional support used by the 7 py2app suite (modulegraph and macholib, specifically). 8 9 altgraph is a python based graph (network) representation and manipulation package. 10 It has started out as an extension to the `graph_lib module <http://www.ece.arizona.edu/~denny/python_nest/graph_lib_1.0.1.html>`_ 11 written by Nathan Denny it has been significantly optimized and expanded. 12 13 The :class:`altgraph.Graph.Graph` class is loosely modeled after the `LEDA <http://www.algorithmic-solutions.com/enleda.htm>`_ 14 (Library of Efficient Datatypes) representation. The library 15 includes methods for constructing graphs, BFS and DFS traversals, 16 topological sort, finding connected components, shortest paths as well as a number 17 graph statistics functions. The library can also visualize graphs 18 via `graphviz <http://www.research.att.com/sw/tools/graphviz/>`_. 19 20 The package contains the following modules: 21 22 - the :py:mod:`altgraph.Graph` module contains the :class:`~altgraph.Graph.Graph` class that stores the graph data 23 24 - the :py:mod:`altgraph.GraphAlgo` module implements graph algorithms operating on graphs (:py:class:`~altgraph.Graph.Graph`} instances) 25 26 - the :py:mod:`altgraph.GraphStat` module contains functions for computing statistical measures on graphs 27 28 - the :py:mod:`altgraph.GraphUtil` module contains functions for generating, reading and saving graphs 29 30 - the :py:mod:`altgraph.Dot` module contains functions for displaying graphs via `graphviz <http://www.research.att.com/sw/tools/graphviz/>`_ 31 32 - the :py:mod:`altgraph.ObjectGraph` module implements a graph of objects with a unique identifier 33 34 Installation 35 ------------ 36 37 Download and unpack the archive then type:: 38 39 python setup.py install 40 41 This will install the library in the default location. For instructions on 42 how to customize the install procedure read the output of:: 43 44 python setup.py --help install 45 46 To verify that the code works run the test suite:: 47 48 python setup.py test 49 50 Example usage 51 ------------- 52 53 Lets assume that we want to analyze the graph below (links to the full picture) GRAPH_IMG. 54 Our script then might look the following way:: 55 56 from altgraph import Graph, GraphAlgo, Dot 57 58 # these are the edges 59 edges = [ (1,2), (2,4), (1,3), (2,4), (3,4), (4,5), (6,5), 60 (6,14), (14,15), (6, 15), (5,7), (7, 8), (7,13), (12,8), 61 (8,13), (11,12), (11,9), (13,11), (9,13), (13,10) ] 62 63 # creates the graph 64 graph = Graph.Graph() 65 for head, tail in edges: 66 graph.add_edge(head, tail) 67 68 # do a forward bfs from 1 at most to 20 69 print(graph.forw_bfs(1)) 70 71 This will print the nodes in some breadth first order:: 72 73 [1, 2, 3, 4, 5, 7, 8, 13, 11, 10, 12, 9] 74 75 If we wanted to get the hop-distance from node 1 to node 8 76 we coud write:: 77 78 print(graph.get_hops(1, 8)) 79 80 This will print the following:: 81 82 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] 83 84 Node 1 is at 0 hops since it is the starting node, nodes 2,3 are 1 hop away ... 85 node 8 is 5 hops away. To find the shortest distance between two nodes you 86 can use:: 87 88 print(GraphAlgo.shortest_path(graph, 1, 12)) 89 90 It will print the nodes on one (if there are more) the shortest paths:: 91 92 [1, 2, 4, 5, 7, 13, 11, 12] 93 94 To display the graph we can use the GraphViz backend:: 95 96 dot = Dot.Dot(graph) 97 98 # display the graph on the monitor 99 dot.display() 100 101 # save it in an image file 102 dot.save_img(file_name='graph', file_type='gif') 103 104 105 106 .. 107 @author: U{Istvan Albert<http://www.personal.psu.edu/staff/i/u/iua1/>} 108 109 @license: MIT License 110 111 Copyright (c) 2004 Istvan Albert unless otherwise noted. 112 113 Permission is hereby granted, free of charge, to any person obtaining a copy of this software 114 and associated documentation files (the "Software"), to deal in the Software without restriction, 115 including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 116 and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do 117 so. 118 119 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 120 INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 121 PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE 122 FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 123 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 124 THE SOFTWARE. 125 @requires: Python 2.3 or higher 126 127 @newfield contributor: Contributors: 128 @contributor: U{Reka Albert <http://www.phys.psu.edu/~ralbert/>} 129 130 ''' 131 import pkg_resources 132 __version__ = pkg_resources.require('altgraph')[0].version 133 134 class GraphError(ValueError): 135 pass 136
