Package networkx :: Module distance
[hide private]
[frames] | no frames]

Source Code for Module networkx.distance

  1  """ 
  2  Shortest paths, diameter, radius, eccentricity, and related methods. 
  3  """ 
  4  __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 
  5  #    Copyright (C) 2004-2006 by  
  6  #    Aric Hagberg <hagberg@lanl.gov> 
  7  #    Dan Schult <dschult@colgate.edu> 
  8  #    Pieter Swart <swart@lanl.gov> 
  9  #    Distributed under the terms of the GNU Lesser General Public License 
 10  #    http://www.gnu.org/copyleft/lesser.html 
 11  import networkx 
 12  from networkx.path import single_source_shortest_path_length 
 13   
14 -def eccentricity(G, v=None, sp=None, with_labels=False):
15 """Return the eccentricity of node v in G (or all nodes if v is None). 16 17 The eccentricity is the maximum of shortest paths to all other nodes. 18 19 The optional keyword sp must be a dict of dicts of 20 shortest_path_length keyed by source and target. 21 That is, sp[v][t] is the length from v to t. 22 23 If with_labels=True 24 return dict of eccentricities keyed by vertex. 25 """ 26 nodes=[] 27 if v is None: # none, use entire graph 28 nodes=G.nodes() 29 elif isinstance(v, list): # check for a list 30 nodes=v 31 else: # assume it is a single value 32 nodes=[v] 33 34 e={} 35 for v in nodes: 36 if sp is None: 37 length=single_source_shortest_path_length(G,v) 38 else: 39 length=sp[v] 40 try: 41 assert len(length)==G.number_of_nodes() 42 except: 43 raise networkx.NetworkXError,\ 44 "Graph not connected: infinite path length" 45 46 e[v]=max(length.values()) 47 48 if with_labels: 49 return e 50 else: 51 if len(e)==1: return e.values()[0] # return single value 52 return e.values()
53
54 -def diameter(G, e=None):
55 """Return the diameter of the graph G. 56 57 The diameter is the maximum of all pairs shortest path. 58 """ 59 if e is None: 60 e=eccentricity(G,with_labels=True) 61 return max(e.values())
62
63 -def periphery(G, e=None):
64 """Return the periphery of the graph G. 65 66 The periphery is the set of nodes with eccentricity equal to the diameter. 67 """ 68 if e is None: 69 e=eccentricity(G,with_labels=True) 70 diameter=max(e.values()) 71 p=[v for v in e if e[v]==diameter] 72 return p
73 74
75 -def radius(G, e=None):
76 """Return the radius of the graph G. 77 78 The radius is the minimum of all pairs shortest path. 79 """ 80 if e is None: 81 e=eccentricity(G,with_labels=True) 82 return min(e.values())
83
84 -def center(G, e=None):
85 """Return the center of graph G. 86 87 The center is the set of nodes with eccentricity equal to radius. 88 """ 89 if e is None: 90 e=eccentricity(G,with_labels=True) 91 # order the nodes by path length 92 radius=min(e.values()) 93 p=[v for v in e if e[v]==radius] 94 return p
95 96 97
98 -def _test_suite():
99 import doctest 100 suite = doctest.DocFileSuite('tests/distance.txt',package='networkx') 101 return suite
102 103 104 if __name__ == "__main__": 105 import os 106 import sys 107 import unittest 108 if sys.version_info[:2] < (2, 4): 109 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 110 sys.exit(-1) 111 # directory of networkx package (relative to this) 112 nxbase=sys.path[0]+os.sep+os.pardir 113 sys.path.insert(0,nxbase) # prepend to search path 114 unittest.TextTestRunner().run(_test_suite()) 115