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
178
179
|
"""
=======================
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)])
|
