1''' 2altgraph - a python graph library 3================================= 4 5altgraph is a fork of `graphlib <http://pygraphlib.sourceforge.net>`_ tailored 6to use newer Python 2.3+ features, including additional support used by the 7py2app suite (modulegraph and macholib, specifically). 8 9altgraph is a python based graph (network) representation and manipulation package. 10It 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>`_ 11written by Nathan Denny it has been significantly optimized and expanded. 12 13The :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 15includes methods for constructing graphs, BFS and DFS traversals, 16topological sort, finding connected components, shortest paths as well as a number 17graph statistics functions. The library can also visualize graphs 18via `graphviz <http://www.research.att.com/sw/tools/graphviz/>`_. 19 20The 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 34Installation 35------------ 36 37Download and unpack the archive then type:: 38 39 python setup.py install 40 41This will install the library in the default location. For instructions on 42how to customize the install procedure read the output of:: 43 44 python setup.py --help install 45 46To verify that the code works run the test suite:: 47 48 python setup.py test 49 50Example usage 51------------- 52 53Lets assume that we want to analyze the graph below (links to the full picture) GRAPH_IMG. 54Our 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 71This will print the nodes in some breadth first order:: 72 73 [1, 2, 3, 4, 5, 7, 8, 13, 11, 10, 12, 9] 74 75If we wanted to get the hop-distance from node 1 to node 8 76we coud write:: 77 78 print(graph.get_hops(1, 8)) 79 80This will print the following:: 81 82 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] 83 84Node 1 is at 0 hops since it is the starting node, nodes 2,3 are 1 hop away ... 85node 8 is 5 hops away. To find the shortest distance between two nodes you 86can use:: 87 88 print(GraphAlgo.shortest_path(graph, 1, 12)) 89 90It will print the nodes on one (if there are more) the shortest paths:: 91 92 [1, 2, 4, 5, 7, 13, 11, 12] 93 94To 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''' 131import pkg_resources 132__version__ = pkg_resources.require('altgraph')[0].version 133 134class GraphError(ValueError): 135 pass 136