ioftools / networkxMiCe / networkxmaster / networkx / algorithms / distance_regular.py @ 5cef0f13
History  View  Annotate  Download (6.99 KB)
1 
# Copyright (C) 2011 by


2 
# Dheeraj M R <dheerajrav@gmail.com>

3 
# Aric Hagberg <aric.hagberg@gmail.com>

4 
# All rights reserved.

5 
# BSD license.

6 
"""

7 
=======================

8 
Distanceregular graphs

9 
=======================

10 
"""

11  
12 
import networkx as nx 
13 
from networkx.utils import not_implemented_for 
14 
from .distance_measures import diameter 
15  
16 
__author__ = """\n""".join(['Dheeraj M R <dheerajrav@gmail.com>', 
17 
'Aric Hagberg <aric.hagberg@gmail.com>'])

18  
19 
__all__ = ['is_distance_regular', 'is_strongly_regular', 
20 
'intersection_array', 'global_parameters'] 
21  
22  
23 
def is_distance_regular(G): 
24 
"""Returns True if the graph is distance regular, False otherwise.

25 

26 
A connected graph G is distanceregular if for any nodes x,y

27 
and any integers i,j=0,1,...,d (where d is the graph

28 
diameter), the number of vertices at distance i from x and

29 
distance j from y depends only on i,j and the graph distance

30 
between x and y, independently of the choice of x and y.

31 

32 
Parameters

33 


34 
G: Networkx graph (undirected)

35 

36 
Returns

37 


38 
bool

39 
True if the graph is Distance Regular, False otherwise

40 

41 
Examples

42 


43 
>>> G=nx.hypercube_graph(6)

44 
>>> nx.is_distance_regular(G)

45 
True

46 

47 
See Also

48 


49 
intersection_array, global_parameters

50 

51 
Notes

52 


53 
For undirected and simple graphs only

54 

55 
References

56 


57 
.. [1] Brouwer, A. E.; Cohen, A. M.; and Neumaier, A.

58 
DistanceRegular Graphs. New York: SpringerVerlag, 1989.

59 
.. [2] Weisstein, Eric W. "DistanceRegular Graph."

60 
http://mathworld.wolfram.com/DistanceRegularGraph.html

61 

62 
"""

63 
try:

64 
intersection_array(G) 
65 
return True 
66 
except nx.NetworkXError:

67 
return False 
68  
69  
70 
def global_parameters(b, c): 
71 
"""Returns global parameters for a given intersection array.

72 

73 
Given a distanceregular graph G with integers b_i, c_i,i = 0,....,d

74 
such that for any 2 vertices x,y in G at a distance i=d(x,y), there

75 
are exactly c_i neighbors of y at a distance of i1 from x and b_i

76 
neighbors of y at a distance of i+1 from x.

77 

78 
Thus, a distance regular graph has the global parameters,

79 
[[c_0,a_0,b_0],[c_1,a_1,b_1],......,[c_d,a_d,b_d]] for the

80 
intersection array [b_0,b_1,.....b_{d1};c_1,c_2,.....c_d]

81 
where a_i+b_i+c_i=k , k= degree of every vertex.

82 

83 
Parameters

84 


85 
b : list

86 

87 
c : list

88 

89 
Returns

90 


91 
iterable

92 
An iterable over three tuples.

93 

94 
Examples

95 


96 
>>> G = nx.dodecahedral_graph()

97 
>>> b, c = nx.intersection_array(G)

98 
>>> list(nx.global_parameters(b, c))

99 
[(0, 0, 3), (1, 0, 2), (1, 1, 1), (1, 1, 1), (2, 0, 1), (3, 0, 0)]

100 

101 
References

102 


103 
.. [1] Weisstein, Eric W. "Global Parameters."

104 
From MathWorldA Wolfram Web Resource.

105 
http://mathworld.wolfram.com/GlobalParameters.html

106 

107 
See Also

108 


109 
intersection_array

110 
"""

111 
return ((y, b[0]  x  y, x) for x, y in zip(b + [0], [0] + c)) 
112  
113  
114 
@not_implemented_for('directed', 'multigraph') 
115 
def intersection_array(G): 
116 
"""Returns the intersection array of a distanceregular graph.

117 

118 
Given a distanceregular graph G with integers b_i, c_i,i = 0,....,d

119 
such that for any 2 vertices x,y in G at a distance i=d(x,y), there

120 
are exactly c_i neighbors of y at a distance of i1 from x and b_i

121 
neighbors of y at a distance of i+1 from x.

122 

123 
A distance regular graph's intersection array is given by,

124 
[b_0,b_1,.....b_{d1};c_1,c_2,.....c_d]

125 

126 
Parameters

127 


128 
G: Networkx graph (undirected)

129 

130 
Returns

131 


132 
b,c: tuple of lists

133 

134 
Examples

135 


136 
>>> G=nx.icosahedral_graph()

137 
>>> nx.intersection_array(G)

138 
([5, 2, 1], [1, 2, 5])

139 

140 
References

141 


142 
.. [1] Weisstein, Eric W. "Intersection Array."

143 
From MathWorldA Wolfram Web Resource.

144 
http://mathworld.wolfram.com/IntersectionArray.html

145 

146 
See Also

147 


148 
global_parameters

149 
"""

150 
# test for regular graph (all degrees must be equal)

151 
degree = iter(G.degree())

152 
(_, k) = next(degree)

153 
for _, knext in degree: 
154 
if knext != k:

155 
raise nx.NetworkXError('Graph is not distance regular.') 
156 
k = knext 
157 
path_length = dict(nx.all_pairs_shortest_path_length(G))

158 
diameter = max([max(path_length[n].values()) for n in path_length]) 
159 
bint = {} # 'b' intersection array

160 
cint = {} # 'c' intersection array

161 
for u in G: 
162 
for v in G: 
163 
try:

164 
i = path_length[u][v] 
165 
except KeyError: # graph must be connected 
166 
raise nx.NetworkXError('Graph is not distance regular.') 
167 
# number of neighbors of v at a distance of i1 from u

168 
c = len([n for n in G[v] if path_length[n][u] == i  1]) 
169 
# number of neighbors of v at a distance of i+1 from u

170 
b = len([n for n in G[v] if path_length[n][u] == i + 1]) 
171 
# b,c are independent of u and v

172 
if cint.get(i, c) != c or bint.get(i, b) != b: 
173 
raise nx.NetworkXError('Graph is not distance regular') 
174 
bint[i] = b 
175 
cint[i] = c 
176 
return ([bint.get(j, 0) for j in range(diameter)], 
177 
[cint.get(j + 1, 0) for j in range(diameter)]) 
178  
179  
180 
# TODO There is a definition for directed strongly regular graphs.

181 
@not_implemented_for('directed', 'multigraph') 
182 
def is_strongly_regular(G): 
183 
"""Returns True if and only if the given graph is strongly

184 
regular.

185 

186 
An undirected graph is *strongly regular* if

187 

188 
* it is regular,

189 
* each pair of adjacent vertices has the same number of neighbors in

190 
common,

191 
* each pair of nonadjacent vertices has the same number of neighbors

192 
in common.

193 

194 
Each strongly regular graph is a distanceregular graph.

195 
Conversely, if a distanceregular graph has diameter two, then it is

196 
a strongly regular graph. For more information on distanceregular

197 
graphs, see :func:`is_distance_regular`.

198 

199 
Parameters

200 


201 
G : NetworkX graph

202 
An undirected graph.

203 

204 
Returns

205 


206 
bool

207 
Whether `G` is strongly regular.

208 

209 
Examples

210 


211 

212 
The cycle graph on five vertices is strongly regular. It is

213 
tworegular, each pair of adjacent vertices has no shared neighbors,

214 
and each pair of nonadjacent vertices has one shared neighbor::

215 

216 
>>> import networkx as nx

217 
>>> G = nx.cycle_graph(5)

218 
>>> nx.is_strongly_regular(G)

219 
True

220 

221 
"""

222 
# Here is an alternate implementation based directly on the

223 
# definition of strongly regular graphs:

224 
#

225 
# return (all_equal(G.degree().values())

226 
# and all_equal(len(common_neighbors(G, u, v))

227 
# for u, v in G.edges())

228 
# and all_equal(len(common_neighbors(G, u, v))

229 
# for u, v in non_edges(G)))

230 
#

231 
# We instead use the fact that a distanceregular graph of diameter

232 
# two is strongly regular.

233 
return is_distance_regular(G) and diameter(G) == 2 