Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/distance_regular.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 ======================= | |
3 Distance-regular graphs | |
4 ======================= | |
5 """ | |
6 | |
7 import networkx as nx | |
8 from networkx.utils import not_implemented_for | |
9 from .distance_measures import diameter | |
10 | |
11 __all__ = [ | |
12 "is_distance_regular", | |
13 "is_strongly_regular", | |
14 "intersection_array", | |
15 "global_parameters", | |
16 ] | |
17 | |
18 | |
19 def is_distance_regular(G): | |
20 """Returns True if the graph is distance regular, False otherwise. | |
21 | |
22 A connected graph G is distance-regular if for any nodes x,y | |
23 and any integers i,j=0,1,...,d (where d is the graph | |
24 diameter), the number of vertices at distance i from x and | |
25 distance j from y depends only on i,j and the graph distance | |
26 between x and y, independently of the choice of x and y. | |
27 | |
28 Parameters | |
29 ---------- | |
30 G: Networkx graph (undirected) | |
31 | |
32 Returns | |
33 ------- | |
34 bool | |
35 True if the graph is Distance Regular, False otherwise | |
36 | |
37 Examples | |
38 -------- | |
39 >>> G = nx.hypercube_graph(6) | |
40 >>> nx.is_distance_regular(G) | |
41 True | |
42 | |
43 See Also | |
44 -------- | |
45 intersection_array, global_parameters | |
46 | |
47 Notes | |
48 ----- | |
49 For undirected and simple graphs only | |
50 | |
51 References | |
52 ---------- | |
53 .. [1] Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. | |
54 Distance-Regular Graphs. New York: Springer-Verlag, 1989. | |
55 .. [2] Weisstein, Eric W. "Distance-Regular Graph." | |
56 http://mathworld.wolfram.com/Distance-RegularGraph.html | |
57 | |
58 """ | |
59 try: | |
60 intersection_array(G) | |
61 return True | |
62 except nx.NetworkXError: | |
63 return False | |
64 | |
65 | |
66 def global_parameters(b, c): | |
67 """Returns global parameters for a given intersection array. | |
68 | |
69 Given a distance-regular graph G with integers b_i, c_i,i = 0,....,d | |
70 such that for any 2 vertices x,y in G at a distance i=d(x,y), there | |
71 are exactly c_i neighbors of y at a distance of i-1 from x and b_i | |
72 neighbors of y at a distance of i+1 from x. | |
73 | |
74 Thus, a distance regular graph has the global parameters, | |
75 [[c_0,a_0,b_0],[c_1,a_1,b_1],......,[c_d,a_d,b_d]] for the | |
76 intersection array [b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d] | |
77 where a_i+b_i+c_i=k , k= degree of every vertex. | |
78 | |
79 Parameters | |
80 ---------- | |
81 b : list | |
82 | |
83 c : list | |
84 | |
85 Returns | |
86 ------- | |
87 iterable | |
88 An iterable over three tuples. | |
89 | |
90 Examples | |
91 -------- | |
92 >>> G = nx.dodecahedral_graph() | |
93 >>> b, c = nx.intersection_array(G) | |
94 >>> list(nx.global_parameters(b, c)) | |
95 [(0, 0, 3), (1, 0, 2), (1, 1, 1), (1, 1, 1), (2, 0, 1), (3, 0, 0)] | |
96 | |
97 References | |
98 ---------- | |
99 .. [1] Weisstein, Eric W. "Global Parameters." | |
100 From MathWorld--A Wolfram Web Resource. | |
101 http://mathworld.wolfram.com/GlobalParameters.html | |
102 | |
103 See Also | |
104 -------- | |
105 intersection_array | |
106 """ | |
107 return ((y, b[0] - x - y, x) for x, y in zip(b + [0], [0] + c)) | |
108 | |
109 | |
110 @not_implemented_for("directed", "multigraph") | |
111 def intersection_array(G): | |
112 """Returns the intersection array of a distance-regular graph. | |
113 | |
114 Given a distance-regular graph G with integers b_i, c_i,i = 0,....,d | |
115 such that for any 2 vertices x,y in G at a distance i=d(x,y), there | |
116 are exactly c_i neighbors of y at a distance of i-1 from x and b_i | |
117 neighbors of y at a distance of i+1 from x. | |
118 | |
119 A distance regular graph's intersection array is given by, | |
120 [b_0,b_1,.....b_{d-1};c_1,c_2,.....c_d] | |
121 | |
122 Parameters | |
123 ---------- | |
124 G: Networkx graph (undirected) | |
125 | |
126 Returns | |
127 ------- | |
128 b,c: tuple of lists | |
129 | |
130 Examples | |
131 -------- | |
132 >>> G = nx.icosahedral_graph() | |
133 >>> nx.intersection_array(G) | |
134 ([5, 2, 1], [1, 2, 5]) | |
135 | |
136 References | |
137 ---------- | |
138 .. [1] Weisstein, Eric W. "Intersection Array." | |
139 From MathWorld--A Wolfram Web Resource. | |
140 http://mathworld.wolfram.com/IntersectionArray.html | |
141 | |
142 See Also | |
143 -------- | |
144 global_parameters | |
145 """ | |
146 # test for regular graph (all degrees must be equal) | |
147 degree = iter(G.degree()) | |
148 (_, k) = next(degree) | |
149 for _, knext in degree: | |
150 if knext != k: | |
151 raise nx.NetworkXError("Graph is not distance regular.") | |
152 k = knext | |
153 path_length = dict(nx.all_pairs_shortest_path_length(G)) | |
154 diameter = max([max(path_length[n].values()) for n in path_length]) | |
155 bint = {} # 'b' intersection array | |
156 cint = {} # 'c' intersection array | |
157 for u in G: | |
158 for v in G: | |
159 try: | |
160 i = path_length[u][v] | |
161 except KeyError as e: # graph must be connected | |
162 raise nx.NetworkXError("Graph is not distance regular.") from e | |
163 # number of neighbors of v at a distance of i-1 from u | |
164 c = len([n for n in G[v] if path_length[n][u] == i - 1]) | |
165 # number of neighbors of v at a distance of i+1 from u | |
166 b = len([n for n in G[v] if path_length[n][u] == i + 1]) | |
167 # b,c are independent of u and v | |
168 if cint.get(i, c) != c or bint.get(i, b) != b: | |
169 raise nx.NetworkXError("Graph is not distance regular") | |
170 bint[i] = b | |
171 cint[i] = c | |
172 return ( | |
173 [bint.get(j, 0) for j in range(diameter)], | |
174 [cint.get(j + 1, 0) for j in range(diameter)], | |
175 ) | |
176 | |
177 | |
178 # TODO There is a definition for directed strongly regular graphs. | |
179 @not_implemented_for("directed", "multigraph") | |
180 def is_strongly_regular(G): | |
181 """Returns True if and only if the given graph is strongly | |
182 regular. | |
183 | |
184 An undirected graph is *strongly regular* if | |
185 | |
186 * it is regular, | |
187 * each pair of adjacent vertices has the same number of neighbors in | |
188 common, | |
189 * each pair of nonadjacent vertices has the same number of neighbors | |
190 in common. | |
191 | |
192 Each strongly regular graph is a distance-regular graph. | |
193 Conversely, if a distance-regular graph has diameter two, then it is | |
194 a strongly regular graph. For more information on distance-regular | |
195 graphs, see :func:`is_distance_regular`. | |
196 | |
197 Parameters | |
198 ---------- | |
199 G : NetworkX graph | |
200 An undirected graph. | |
201 | |
202 Returns | |
203 ------- | |
204 bool | |
205 Whether `G` is strongly regular. | |
206 | |
207 Examples | |
208 -------- | |
209 | |
210 The cycle graph on five vertices is strongly regular. It is | |
211 two-regular, each pair of adjacent vertices has no shared neighbors, | |
212 and each pair of nonadjacent vertices has one shared neighbor:: | |
213 | |
214 >>> G = nx.cycle_graph(5) | |
215 >>> nx.is_strongly_regular(G) | |
216 True | |
217 | |
218 """ | |
219 # Here is an alternate implementation based directly on the | |
220 # definition of strongly regular graphs: | |
221 # | |
222 # return (all_equal(G.degree().values()) | |
223 # and all_equal(len(common_neighbors(G, u, v)) | |
224 # for u, v in G.edges()) | |
225 # and all_equal(len(common_neighbors(G, u, v)) | |
226 # for u, v in non_edges(G))) | |
227 # | |
228 # We instead use the fact that a distance-regular graph of diameter | |
229 # two is strongly regular. | |
230 return is_distance_regular(G) and diameter(G) == 2 |