1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
# -*- coding: utf-8 -*-
"""
Graph diameter, radius, eccentricity and other properties.
"""
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Dan Schult(dschult@colgate.edu)'])
# Copyright (C) 2004-2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['eccentricity', 'diameter', 'radius', 'periphery', 'center']
import networkx
def eccentricity(G, v=None, sp=None):
"""Return the eccentricity of nodes in G.
The eccentricity of a node v is the maximum distance from v to
all other nodes in G.
Parameters
----------
G : NetworkX graph
A graph
v : node, optional
Return value of specified node
sp : dict of dicts, optional
All pairs shortest path lenghts as a dictionary of dictionaries
Returns
-------
ecc : dictionary
A dictionary of eccentricity values keyed by node.
"""
nodes=[]
if v is None: # none, use entire graph
nodes=G.nodes()
elif isinstance(v, list): # check for a list
nodes=v
else: # assume it is a single value
nodes=[v]
order=G.order()
e={}
for v in nodes:
if sp is None:
length=networkx.single_source_shortest_path_length(G,v)
else:
length=sp[v]
try:
assert len(length)==order
except:
raise networkx.NetworkXError(\
"Graph not connected: infinite path length")
e[v]=max(length.values())
if len(e)==1: return e.values()[0] # return single value
else:
return e
def diameter(G, e=None):
"""Return the diameter of the graph G.
The diameter is the maximum eccentricity.
Parameters
----------
G : NetworkX graph
A graph
e : eccentricity dictionary, optional
A precomputed dictionary of eccentricities.
Returns
-------
d : integer
Diameter of graph
See Also
--------
eccentricity
"""
if e is None:
e=eccentricity(G)
return max(e.values())
def periphery(G, e=None):
"""Return the periphery of the graph G.
The periphery is the set of nodes with eccentricity equal to the diameter.
Parameters
----------
G : NetworkX graph
A graph
e : eccentricity dictionary, optional
A precomputed dictionary of eccentricities.
Returns
-------
p : list
List of nodes in periphery
"""
if e is None:
e=eccentricity(G)
diameter=max(e.values())
p=[v for v in e if e[v]==diameter]
return p
def radius(G, e=None):
"""Return the radius of the graph G.
The radius is the minimum eccentricity.
Parameters
----------
G : NetworkX graph
A graph
e : eccentricity dictionary, optional
A precomputed dictionary of eccentricities.
Returns
-------
r : integer
Radius of graph
"""
if e is None:
e=eccentricity(G)
return min(e.values())
def center(G, e=None):
"""Return the periphery of the graph G.
The center is the set of nodes with eccentricity equal to radius.
Parameters
----------
G : NetworkX graph
A graph
e : eccentricity dictionary, optional
A precomputed dictionary of eccentricities.
Returns
-------
c : list
List of nodes in center
"""
if e is None:
e=eccentricity(G)
# order the nodes by path length
radius=min(e.values())
p=[v for v in e if e[v]==radius]
return p
|
