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