Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/expanders.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 """Provides explicit constructions of expander graphs. | |
2 | |
3 """ | |
4 import itertools | |
5 import networkx as nx | |
6 | |
7 __all__ = ["margulis_gabber_galil_graph", "chordal_cycle_graph", "paley_graph"] | |
8 | |
9 | |
10 # Other discrete torus expanders can be constructed by using the following edge | |
11 # sets. For more information, see Chapter 4, "Expander Graphs", in | |
12 # "Pseudorandomness", by Salil Vadhan. | |
13 # | |
14 # For a directed expander, add edges from (x, y) to: | |
15 # | |
16 # (x, y), | |
17 # ((x + 1) % n, y), | |
18 # (x, (y + 1) % n), | |
19 # (x, (x + y) % n), | |
20 # (-y % n, x) | |
21 # | |
22 # For an undirected expander, add the reverse edges. | |
23 # | |
24 # Also appearing in the paper of Gabber and Galil: | |
25 # | |
26 # (x, y), | |
27 # (x, (x + y) % n), | |
28 # (x, (x + y + 1) % n), | |
29 # ((x + y) % n, y), | |
30 # ((x + y + 1) % n, y) | |
31 # | |
32 # and: | |
33 # | |
34 # (x, y), | |
35 # ((x + 2*y) % n, y), | |
36 # ((x + (2*y + 1)) % n, y), | |
37 # ((x + (2*y + 2)) % n, y), | |
38 # (x, (y + 2*x) % n), | |
39 # (x, (y + (2*x + 1)) % n), | |
40 # (x, (y + (2*x + 2)) % n), | |
41 # | |
42 def margulis_gabber_galil_graph(n, create_using=None): | |
43 r"""Returns the Margulis-Gabber-Galil undirected MultiGraph on `n^2` nodes. | |
44 | |
45 The undirected MultiGraph is regular with degree `8`. Nodes are integer | |
46 pairs. The second-largest eigenvalue of the adjacency matrix of the graph | |
47 is at most `5 \sqrt{2}`, regardless of `n`. | |
48 | |
49 Parameters | |
50 ---------- | |
51 n : int | |
52 Determines the number of nodes in the graph: `n^2`. | |
53 create_using : NetworkX graph constructor, optional (default MultiGraph) | |
54 Graph type to create. If graph instance, then cleared before populated. | |
55 | |
56 Returns | |
57 ------- | |
58 G : graph | |
59 The constructed undirected multigraph. | |
60 | |
61 Raises | |
62 ------ | |
63 NetworkXError | |
64 If the graph is directed or not a multigraph. | |
65 | |
66 """ | |
67 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
68 if G.is_directed() or not G.is_multigraph(): | |
69 msg = "`create_using` must be an undirected multigraph." | |
70 raise nx.NetworkXError(msg) | |
71 | |
72 for (x, y) in itertools.product(range(n), repeat=2): | |
73 for (u, v) in ( | |
74 ((x + 2 * y) % n, y), | |
75 ((x + (2 * y + 1)) % n, y), | |
76 (x, (y + 2 * x) % n), | |
77 (x, (y + (2 * x + 1)) % n), | |
78 ): | |
79 G.add_edge((x, y), (u, v)) | |
80 G.graph["name"] = f"margulis_gabber_galil_graph({n})" | |
81 return G | |
82 | |
83 | |
84 def chordal_cycle_graph(p, create_using=None): | |
85 """Returns the chordal cycle graph on `p` nodes. | |
86 | |
87 The returned graph is a cycle graph on `p` nodes with chords joining each | |
88 vertex `x` to its inverse modulo `p`. This graph is a (mildly explicit) | |
89 3-regular expander [1]_. | |
90 | |
91 `p` *must* be a prime number. | |
92 | |
93 Parameters | |
94 ---------- | |
95 p : a prime number | |
96 | |
97 The number of vertices in the graph. This also indicates where the | |
98 chordal edges in the cycle will be created. | |
99 | |
100 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
101 Graph type to create. If graph instance, then cleared before populated. | |
102 | |
103 Returns | |
104 ------- | |
105 G : graph | |
106 The constructed undirected multigraph. | |
107 | |
108 Raises | |
109 ------ | |
110 NetworkXError | |
111 | |
112 If `create_using` indicates directed or not a multigraph. | |
113 | |
114 References | |
115 ---------- | |
116 | |
117 .. [1] Theorem 4.4.2 in A. Lubotzky. "Discrete groups, expanding graphs and | |
118 invariant measures", volume 125 of Progress in Mathematics. | |
119 Birkhäuser Verlag, Basel, 1994. | |
120 | |
121 """ | |
122 G = nx.empty_graph(0, create_using, default=nx.MultiGraph) | |
123 if G.is_directed() or not G.is_multigraph(): | |
124 msg = "`create_using` must be an undirected multigraph." | |
125 raise nx.NetworkXError(msg) | |
126 | |
127 for x in range(p): | |
128 left = (x - 1) % p | |
129 right = (x + 1) % p | |
130 # Here we apply Fermat's Little Theorem to compute the multiplicative | |
131 # inverse of x in Z/pZ. By Fermat's Little Theorem, | |
132 # | |
133 # x^p = x (mod p) | |
134 # | |
135 # Therefore, | |
136 # | |
137 # x * x^(p - 2) = 1 (mod p) | |
138 # | |
139 # The number 0 is a special case: we just let its inverse be itself. | |
140 chord = pow(x, p - 2, p) if x > 0 else 0 | |
141 for y in (left, right, chord): | |
142 G.add_edge(x, y) | |
143 G.graph["name"] = f"chordal_cycle_graph({p})" | |
144 return G | |
145 | |
146 | |
147 def paley_graph(p, create_using=None): | |
148 """Returns the Paley (p-1)/2-regular graph on p nodes. | |
149 | |
150 The returned graph is a graph on Z/pZ with edges between x and y | |
151 if and only if x-y is a nonzero square in Z/pZ. | |
152 | |
153 If p = 1 mod 4, -1 is a square in Z/pZ and therefore x-y is a square if and | |
154 only if y-x is also a square, i.e the edges in the Paley graph are symmetric. | |
155 | |
156 If p = 3 mod 4, -1 is not a square in Z/pZ and therefore either x-y or y-x | |
157 is a square in Z/pZ but not both. | |
158 | |
159 Note that a more general definition of Paley graphs extends this construction | |
160 to graphs over q=p^n vertices, by using the finite field F_q instead of Z/pZ. | |
161 This construction requires to compute squares in general finite fields and is | |
162 not what is implemented here (i.e paley_graph(25) does not return the true | |
163 Paley graph associated with 5^2). | |
164 | |
165 Parameters | |
166 ---------- | |
167 p : int, an odd prime number. | |
168 | |
169 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
170 Graph type to create. If graph instance, then cleared before populated. | |
171 | |
172 Returns | |
173 ------- | |
174 G : graph | |
175 The constructed directed graph. | |
176 | |
177 Raises | |
178 ------ | |
179 NetworkXError | |
180 If the graph is a multigraph. | |
181 | |
182 References | |
183 ---------- | |
184 Chapter 13 in B. Bollobas, Random Graphs. Second edition. | |
185 Cambridge Studies in Advanced Mathematics, 73. | |
186 Cambridge University Press, Cambridge (2001). | |
187 """ | |
188 G = nx.empty_graph(0, create_using, default=nx.DiGraph) | |
189 if G.is_multigraph(): | |
190 msg = "`create_using` cannot be a multigraph." | |
191 raise nx.NetworkXError(msg) | |
192 | |
193 # Compute the squares in Z/pZ. | |
194 # Make it a set to uniquify (there are exactly (p-1)/2 squares in Z/pZ | |
195 # when is prime). | |
196 square_set = {(x ** 2) % p for x in range(1, p) if (x ** 2) % p != 0} | |
197 | |
198 for x in range(p): | |
199 for x2 in square_set: | |
200 G.add_edge(x, (x + x2) % p) | |
201 G.graph["name"] = f"paley({p})" | |
202 return G |