/usr/lib/python2.7/dist-packages/networkx/algorithms/distance_measures.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 166 167 168 169 | # -*- 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 lengths as a dictionary of dictionaries
Returns
-------
ecc : dictionary
A dictionary of eccentricity values keyed by node.
"""
# nodes=
# nodes=[]
# if v is None: # none, use entire graph
# nodes=G.nodes()
# elif v in G: # is v a single node
# nodes=[v]
# else: # assume v is a container of nodes
# nodes=v
order=G.order()
e={}
for n in G.nbunch_iter(v):
if sp is None:
length=networkx.single_source_shortest_path_length(G,n)
L = len(length)
else:
try:
length=sp[n]
L = len(length)
except TypeError:
raise networkx.NetworkXError('Format of "sp" is invalid.')
if L != order:
msg = "Graph not connected: infinite path length"
raise networkx.NetworkXError(msg)
e[n]=max(length.values())
if v in G:
return e[v] # 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 center 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
|