/usr/lib/python2.7/dist-packages/networkx/algorithms/distance_regular.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 170 171 172 173 174 175 176 177 | """
=======================
Distance-regular graphs
=======================
"""
# Copyright (C) 2011 by
# Dheeraj M R <dheerajrav@gmail.com>
# Aric Hagberg <aric.hagberg@gmail.com>
# All rights reserved.
# BSD license.
import networkx as nx
__author__ = """\n""".join(['Dheeraj M R <dheerajrav@gmail.com>',
'Aric Hagberg <aric.hagberg@gmail.com>'])
__all__ = ['is_distance_regular','intersection_array','global_parameters']
def is_distance_regular(G):
"""Returns True if the graph is distance regular, False otherwise.
A connected graph G is distance-regular if for any nodes x,y
and any integers i,j=0,1,...,d (where d is the graph
diameter), the number of vertices at distance i from x and
distance j from y depends only on i,j and the graph distance
between x and y, independently of the choice of x and y.
Parameters
----------
G: Networkx graph (undirected)
Returns
-------
bool
True if the graph is Distance Regular, False otherwise
Examples
--------
>>> G=nx.hypercube_graph(6)
>>> nx.is_distance_regular(G)
True
See Also
--------
intersection_array, global_parameters
Notes
-----
For undirected and simple graphs only
References
----------
.. [1] Brouwer, A. E.; Cohen, A. M.; and Neumaier, A.
Distance-Regular Graphs. New York: Springer-Verlag, 1989.
.. [2] Weisstein, Eric W. "Distance-Regular Graph."
http://mathworld.wolfram.com/Distance-RegularGraph.html
"""
try:
a=intersection_array(G)
return True
except nx.NetworkXError:
return False
def global_parameters(b,c):
"""Return global parameters for a given intersection array.
Given a distance-regular graph G with integers b_i, c_i,i = 0,....,d
such that for any 2 vertices x,y in G at a distance i=d(x,y), there
are exactly c_i neighbors of y at a distance of i-1 from x and b_i
neighbors of y at a distance of i+1 from x.
Thus, a distance regular graph has the global parameters,
[[c_0,a_0,b_0],[c_1,a_1,b_1],......,[c_d,a_d,b_d]] for the
intersection array [b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d]
where a_i+b_i+c_i=k , k= degree of every vertex.
Parameters
----------
b,c: tuple of lists
Returns
-------
p : list of three-tuples
Examples
--------
>>> G=nx.dodecahedral_graph()
>>> b,c=nx.intersection_array(G)
>>> list(nx.global_parameters(b,c))
[(0, 0, 3), (1, 0, 2), (1, 1, 1), (1, 1, 1), (2, 0, 1), (3, 0, 0)]
References
----------
.. [1] Weisstein, Eric W. "Global Parameters."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/GlobalParameters.html
See Also
--------
intersection_array
"""
d=len(b)
ba=b[:]
ca=c[:]
ba.append(0)
ca.insert(0,0)
k = ba[0]
aa = [k-x-y for x,y in zip(ba,ca)]
return zip(*[ca,aa,ba])
def intersection_array(G):
"""Returns the intersection array of a distance-regular graph.
Given a distance-regular graph G with integers b_i, c_i,i = 0,....,d
such that for any 2 vertices x,y in G at a distance i=d(x,y), there
are exactly c_i neighbors of y at a distance of i-1 from x and b_i
neighbors of y at a distance of i+1 from x.
A distance regular graph'sintersection array is given by,
[b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d]
Parameters
----------
G: Networkx graph (undirected)
Returns
-------
b,c: tuple of lists
Examples
--------
>>> G=nx.icosahedral_graph()
>>> nx.intersection_array(G)
([5, 2, 1], [1, 2, 5])
References
----------
.. [1] Weisstein, Eric W. "Intersection Array."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IntersectionArray.html
See Also
--------
global_parameters
"""
if G.is_multigraph() or G.is_directed():
raise nx.NetworkxException('Not implemented for directed ',
'or multiedge graphs.')
# test for regular graph (all degrees must be equal)
degree = G.degree_iter()
(_,k) = next(degree)
for _,knext in degree:
if knext != k:
raise nx.NetworkXError('Graph is not distance regular.')
k = knext
path_length = nx.all_pairs_shortest_path_length(G)
diameter = max([max(path_length[n].values()) for n in path_length])
bint = {} # 'b' intersection array
cint = {} # 'c' intersection array
for u in G:
for v in G:
try:
i = path_length[u][v]
except KeyError: # graph must be connected
raise nx.NetworkXError('Graph is not distance regular.')
# number of neighbors of v at a distance of i-1 from u
c = len([n for n in G[v] if path_length[n][u]==i-1])
# number of neighbors of v at a distance of i+1 from u
b = len([n for n in G[v] if path_length[n][u]==i+1])
# b,c are independent of u and v
if cint.get(i,c) != c or bint.get(i,b) != b:
raise nx.NetworkXError('Graph is not distance regular')
bint[i] = b
cint[i] = c
return ([bint.get(i,0) for i in range(diameter)],
[cint.get(i+1,0) for i in range(diameter)])
|