Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/expanders.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 # Copyright 2014 "cheebee7i".
3 # Copyright 2014 "alexbrc".
4 # Copyright 2014 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.
5 """Provides explicit constructions of expander graphs.
6
7 """
8 import itertools
9 import networkx as nx
10
11 __all__ = ['margulis_gabber_galil_graph', 'chordal_cycle_graph']
12
13
14 # Other discrete torus expanders can be constructed by using the following edge
15 # sets. For more information, see Chapter 4, "Expander Graphs", in
16 # "Pseudorandomness", by Salil Vadhan.
17 #
18 # For a directed expander, add edges from (x, y) to:
19 #
20 # (x, y),
21 # ((x + 1) % n, y),
22 # (x, (y + 1) % n),
23 # (x, (x + y) % n),
24 # (-y % n, x)
25 #
26 # For an undirected expander, add the reverse edges.
27 #
28 # Also appearing in the paper of Gabber and Galil:
29 #
30 # (x, y),
31 # (x, (x + y) % n),
32 # (x, (x + y + 1) % n),
33 # ((x + y) % n, y),
34 # ((x + y + 1) % n, y)
35 #
36 # and:
37 #
38 # (x, y),
39 # ((x + 2*y) % n, y),
40 # ((x + (2*y + 1)) % n, y),
41 # ((x + (2*y + 2)) % n, y),
42 # (x, (y + 2*x) % n),
43 # (x, (y + (2*x + 1)) % n),
44 # (x, (y + (2*x + 2)) % n),
45 #
46 def margulis_gabber_galil_graph(n, create_using=None):
47 r"""Returns the Margulis-Gabber-Galil undirected MultiGraph on `n^2` nodes.
48
49 The undirected MultiGraph is regular with degree `8`. Nodes are integer
50 pairs. The second-largest eigenvalue of the adjacency matrix of the graph
51 is at most `5 \sqrt{2}`, regardless of `n`.
52
53 Parameters
54 ----------
55 n : int
56 Determines the number of nodes in the graph: `n^2`.
57 create_using : NetworkX graph constructor, optional (default MultiGraph)
58 Graph type to create. If graph instance, then cleared before populated.
59
60 Returns
61 -------
62 G : graph
63 The constructed undirected multigraph.
64
65 Raises
66 ------
67 NetworkXError
68 If the graph is directed or not a multigraph.
69
70 """
71 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
72 if G.is_directed() or not G.is_multigraph():
73 msg = "`create_using` must be an undirected multigraph."
74 raise nx.NetworkXError(msg)
75
76 for (x, y) in itertools.product(range(n), repeat=2):
77 for (u, v) in (((x + 2 * y) % n, y), ((x + (2 * y + 1)) % n, y),
78 (x, (y + 2 * x) % n), (x, (y + (2 * x + 1)) % n)):
79 G.add_edge((x, y), (u, v))
80 G.graph['name'] = "margulis_gabber_galil_graph({0})".format(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'] = "chordal_cycle_graph({0})".format(p)
144 return G