Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2=======================
3Distance-regular graphs
4=======================
5"""
7from collections import defaultdict
8from itertools import combinations_with_replacement
9from math import log
11import networkx as nx
12from networkx.utils import not_implemented_for
14from .distance_measures import diameter
16__all__ = [
17 "is_distance_regular",
18 "is_strongly_regular",
19 "intersection_array",
20 "global_parameters",
21]
24@nx._dispatchable
25def is_distance_regular(G):
26 """Returns True if the graph is distance regular, False otherwise.
28 A connected graph G is distance-regular if for any nodes x,y
29 and any integers i,j=0,1,...,d (where d is the graph
30 diameter), the number of vertices at distance i from x and
31 distance j from y depends only on i,j and the graph distance
32 between x and y, independently of the choice of x and y.
34 Parameters
35 ----------
36 G: Networkx graph (undirected)
38 Returns
39 -------
40 bool
41 True if the graph is Distance Regular, False otherwise
43 Examples
44 --------
45 >>> G = nx.hypercube_graph(6)
46 >>> nx.is_distance_regular(G)
47 True
49 See Also
50 --------
51 intersection_array, global_parameters
53 Notes
54 -----
55 For undirected and simple graphs only
57 References
58 ----------
59 .. [1] Brouwer, A. E.; Cohen, A. M.; and Neumaier, A.
60 Distance-Regular Graphs. New York: Springer-Verlag, 1989.
61 .. [2] Weisstein, Eric W. "Distance-Regular Graph."
62 http://mathworld.wolfram.com/Distance-RegularGraph.html
64 """
65 try:
66 intersection_array(G)
67 return True
68 except nx.NetworkXError:
69 return False
72def global_parameters(b, c):
73 """Returns global parameters for a given intersection array.
75 Given a distance-regular graph G with diameter d and integers b_i,
76 c_i,i = 0,....,d such that for any 2 vertices x,y in G at a distance
77 i=d(x,y), there are exactly c_i neighbors of y at a distance of i-1 from x
78 and b_i neighbors of y at a distance of i+1 from x.
80 Thus, a distance regular graph has the global parameters,
81 [[c_0,a_0,b_0],[c_1,a_1,b_1],......,[c_d,a_d,b_d]] for the
82 intersection array [b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d]
83 where a_i+b_i+c_i=k , k= degree of every vertex.
85 Parameters
86 ----------
87 b : list
89 c : list
91 Returns
92 -------
93 iterable
94 An iterable over three tuples.
96 Examples
97 --------
98 >>> G = nx.dodecahedral_graph()
99 >>> b, c = nx.intersection_array(G)
100 >>> list(nx.global_parameters(b, c))
101 [(0, 0, 3), (1, 0, 2), (1, 1, 1), (1, 1, 1), (2, 0, 1), (3, 0, 0)]
103 References
104 ----------
105 .. [1] Weisstein, Eric W. "Global Parameters."
106 From MathWorld--A Wolfram Web Resource.
107 http://mathworld.wolfram.com/GlobalParameters.html
109 See Also
110 --------
111 intersection_array
112 """
113 return ((y, b[0] - x - y, x) for x, y in zip(b + [0], [0] + c))
116@not_implemented_for("directed")
117@not_implemented_for("multigraph")
118@nx._dispatchable
119def intersection_array(G):
120 """Returns the intersection array of a distance-regular graph.
122 Given a distance-regular graph G with integers b_i, c_i,i = 0,....,d
123 such that for any 2 vertices x,y in G at a distance i=d(x,y), there
124 are exactly c_i neighbors of y at a distance of i-1 from x and b_i
125 neighbors of y at a distance of i+1 from x.
127 A distance regular graph's intersection array is given by,
128 [b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d]
130 Parameters
131 ----------
132 G: Networkx graph (undirected)
134 Returns
135 -------
136 b,c: tuple of lists
138 Examples
139 --------
140 >>> G = nx.icosahedral_graph()
141 >>> nx.intersection_array(G)
142 ([5, 2, 1], [1, 2, 5])
144 References
145 ----------
146 .. [1] Weisstein, Eric W. "Intersection Array."
147 From MathWorld--A Wolfram Web Resource.
148 http://mathworld.wolfram.com/IntersectionArray.html
150 See Also
151 --------
152 global_parameters
153 """
154 # the input graph is very unlikely to be distance-regular: here are the
155 # number a(n) of connected simple graphs, and the number b(n) of
156 # distance-regular graphs among them:
157 #
158 # n | 1 2 3 4 5 6 7 8 9 10
159 # -----+------------------------------------------------------------------
160 # a(n) | 1 1 2 6 21 112 853 11117 261080 11716571 https://oeis.org/A001349
161 # b(n) | 1 1 1 2 2 4 2 5 4 7 https://oeis.org/A241814
162 #
163 # in light of this, let's compute shortest path lengths as we go instead of
164 # precomputing them all
165 # test for regular graph (all degrees must be equal)
166 if not nx.is_regular(G) or not nx.is_connected(G):
167 raise nx.NetworkXError("Graph is not distance regular.")
169 path_length = defaultdict(dict)
170 bint = {} # 'b' intersection array
171 cint = {} # 'c' intersection array
173 # see https://doi.org/10.1016/j.ejc.2004.07.004, Theorem 1.5, page 81:
174 # the diameter of a distance-regular graph is at most (8 log_2 n) / 3,
175 # so let's compute it as we go in the hope that we can stop early
176 diam = 0
177 max_diameter_for_dr_graphs = (8 * log(len(G), 2)) / 3
178 for u, v in combinations_with_replacement(G, 2):
179 # compute needed shortest path lengths
180 pl_u = path_length[u]
181 if v not in pl_u:
182 pl_u.update(nx.single_source_shortest_path_length(G, u))
183 for x, distance in pl_u.items():
184 path_length[x][u] = distance
186 i = path_length[u][v]
187 diam = max(diam, i)
189 # diameter too large: graph can't be distance-regular
190 if diam > max_diameter_for_dr_graphs:
191 raise nx.NetworkXError("Graph is not distance regular.")
193 vnbrs = G[v]
194 # compute needed path lengths
195 for n in vnbrs:
196 pl_n = path_length[n]
197 if u not in pl_n:
198 pl_n.update(nx.single_source_shortest_path_length(G, n))
199 for x, distance in pl_n.items():
200 path_length[x][n] = distance
202 # number of neighbors of v at a distance of i-1 from u
203 c = sum(1 for n in vnbrs if pl_u[n] == i - 1)
204 # number of neighbors of v at a distance of i+1 from u
205 b = sum(1 for n in vnbrs if pl_u[n] == i + 1)
206 # b, c are independent of u and v
207 if cint.get(i, c) != c or bint.get(i, b) != b:
208 raise nx.NetworkXError("Graph is not distance regular")
209 bint[i] = b
210 cint[i] = c
212 return (
213 [bint.get(j, 0) for j in range(diam)],
214 [cint.get(j + 1, 0) for j in range(diam)],
215 )
218# TODO There is a definition for directed strongly regular graphs.
219@not_implemented_for("directed")
220@not_implemented_for("multigraph")
221@nx._dispatchable
222def is_strongly_regular(G):
223 """Returns True if and only if the given graph is strongly
224 regular.
226 An undirected graph is *strongly regular* if
228 * it is regular,
229 * each pair of adjacent vertices has the same number of neighbors in
230 common,
231 * each pair of nonadjacent vertices has the same number of neighbors
232 in common.
234 Each strongly regular graph is a distance-regular graph.
235 Conversely, if a distance-regular graph has diameter two, then it is
236 a strongly regular graph. For more information on distance-regular
237 graphs, see :func:`is_distance_regular`.
239 Parameters
240 ----------
241 G : NetworkX graph
242 An undirected graph.
244 Returns
245 -------
246 bool
247 Whether `G` is strongly regular.
249 Examples
250 --------
252 The cycle graph on five vertices is strongly regular. It is
253 two-regular, each pair of adjacent vertices has no shared neighbors,
254 and each pair of nonadjacent vertices has one shared neighbor::
256 >>> G = nx.cycle_graph(5)
257 >>> nx.is_strongly_regular(G)
258 True
260 """
261 # Here is an alternate implementation based directly on the
262 # definition of strongly regular graphs:
263 #
264 # return (all_equal(G.degree().values())
265 # and all_equal(len(common_neighbors(G, u, v))
266 # for u, v in G.edges())
267 # and all_equal(len(common_neighbors(G, u, v))
268 # for u, v in non_edges(G)))
269 #
270 # We instead use the fact that a distance-regular graph of diameter
271 # two is strongly regular.
272 return is_distance_regular(G) and diameter(G) == 2