1 """
2 Shortest paths, diameter, radius, eccentricity, and related methods.
3 """
4 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
5
6
7
8
9
10
11 import networkx
12 from networkx.path import single_source_shortest_path_length
13
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:
28 nodes=G.nodes()
29 elif isinstance(v, list):
30 nodes=v
31 else:
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]
52 return e.values()
53
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
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
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
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
92 radius=min(e.values())
93 p=[v for v in e if e[v]==radius]
94 return p
95
96
97
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
112 nxbase=sys.path[0]+os.sep+os.pardir
113 sys.path.insert(0,nxbase)
114 unittest.TextTestRunner().run(_test_suite())
115