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