1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
# -*- coding: utf-8 -*-
# Copyright 2014 "cheebee7i".
# Copyright 2014 "alexbrc".
# Copyright 2014 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.
"""Provides explicit constructions of expander graphs.
"""
import itertools
import networkx as nx
__all__ = ['margulis_gabber_galil_graph', 'chordal_cycle_graph']
# Other discrete torus expanders can be constructed by using the following edge
# sets. For more information, see Chapter 4, "Expander Graphs", in
# "Pseudorandomness", by Salil Vadhan.
#
# For a directed expander, add edges from (x, y) to:
#
# (x, y),
# ((x + 1) % n, y),
# (x, (y + 1) % n),
# (x, (x + y) % n),
# (-y % n, x)
#
# For an undirected expander, add the reverse edges.
#
# Also appearing in the paper of Gabber and Galil:
#
# (x, y),
# (x, (x + y) % n),
# (x, (x + y + 1) % n),
# ((x + y) % n, y),
# ((x + y + 1) % n, y)
#
# and:
#
# (x, y),
# ((x + 2*y) % n, y),
# ((x + (2*y + 1)) % n, y),
# ((x + (2*y + 2)) % n, y),
# (x, (y + 2*x) % n),
# (x, (y + (2*x + 1)) % n),
# (x, (y + (2*x + 2)) % n),
#
def margulis_gabber_galil_graph(n, create_using=None):
"""Return the Margulis-Gabber-Galil undirected MultiGraph on `n^2` nodes.
The undirected MultiGraph is regular with degree `8`. Nodes are integer
pairs. The second-largest eigenvalue of the adjacency matrix of the graph
is at most `5 \sqrt{2}`, regardless of `n`.
Parameters
----------
n : int
Determines the number of nodes in the graph: `n^2`.
create_using : graph-like
A graph-like object that receives the constructed edges. If ``None``,
then a :class:`~networkx.MultiGraph` instance is used.
Returns
-------
G : graph
The constructed undirected multigraph.
Raises
------
NetworkXError
If the graph is directed or not a multigraph.
"""
if create_using is None:
create_using = nx.MultiGraph()
elif create_using.is_directed() or not create_using.is_multigraph():
msg = "`create_using` must be an undirected multigraph."
raise nx.NetworkXError(msg)
G = create_using
G.clear()
for (x, y) in itertools.product(range(n), repeat=2):
for (u, v) in (((x + 2 * y) % n, y), ((x + (2 * y + 1)) % n, y),
(x, (y + 2 * x) % n), (x, (y + (2 * x + 1)) % n)):
G.add_edge((x, y), (u, v))
G.graph['name'] = "margulis_gabber_galil_graph({0})".format(n)
return G
def chordal_cycle_graph(p, create_using=None):
"""Return the chordal cycle graph on `p` nodes.
The returned graph is a cycle graph on `p` nodes with chords joining each
vertex `x` to its inverse modulo `p`. This graph is a (mildly explicit)
3-regular expander [1]_.
``p`` *must* be a prime number.
Parameters
----------
p : a prime number
The number of vertices in the graph. This also indicates where the
chordal edges in the cycle will be created.
create_using : graph-like
A graph-like object that receives the constructed edges. If ``None``,
then a :class:`~networkx.MultiGraph` instance is used.
Returns
-------
G : graph
The constructed undirected multigraph.
Raises
------
NetworkXError
If the graph provided in ``create_using`` is directed or not a
multigraph.
References
----------
.. [1] Theorem 4.4.2 in A. Lubotzky. "Discrete groups, expanding graphs and
invariant measures", volume 125 of Progress in Mathematics.
Birkhäuser Verlag, Basel, 1994.
"""
if create_using is None:
create_using = nx.MultiGraph()
elif create_using.is_directed() or not create_using.is_multigraph():
msg = "`create_using` must be an undirected multigraph."
raise nx.NetworkXError(msg)
G = create_using
G.clear()
for x in range(p):
left = (x - 1) % p
right = (x + 1) % p
# Here we apply Fermat's Little Theorem to compute the multiplicative
# inverse of x in Z/pZ. By Fermat's Little Theorem,
#
# x^p = x (mod p)
#
# Therefore,
#
# x * x^(p - 2) = 1 (mod p)
#
# The number 0 is a special case: we just let its inverse be itself.
chord = pow(x, p - 2, p) if x > 0 else 0
for y in (left, right, chord):
G.add_edge(x, y)
G.graph['name'] = "chordal_cycle_graph({0})".format(p)
return G
|
