Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/lattice.py: 16%
124 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for generating grid graphs and lattices
3The :func:`grid_2d_graph`, :func:`triangular_lattice_graph`, and
4:func:`hexagonal_lattice_graph` functions correspond to the three
5`regular tilings of the plane`_, the square, triangular, and hexagonal
6tilings, respectively. :func:`grid_graph` and :func:`hypercube_graph`
7are similar for arbitrary dimensions. Useful relevant discussion can
8be found about `Triangular Tiling`_, and `Square, Hex and Triangle Grids`_
10.. _regular tilings of the plane: https://en.wikipedia.org/wiki/List_of_regular_polytopes_and_compounds#Euclidean_tilings
11.. _Square, Hex and Triangle Grids: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
12.. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
14"""
16from itertools import repeat
17from math import sqrt
19import networkx as nx
20from networkx.classes import set_node_attributes
21from networkx.exception import NetworkXError
22from networkx.generators.classic import cycle_graph, empty_graph, path_graph
23from networkx.relabel import relabel_nodes
24from networkx.utils import flatten, nodes_or_number, pairwise
26__all__ = [
27 "grid_2d_graph",
28 "grid_graph",
29 "hypercube_graph",
30 "triangular_lattice_graph",
31 "hexagonal_lattice_graph",
32]
35@nodes_or_number([0, 1])
36@nx._dispatch(graphs=None)
37def grid_2d_graph(m, n, periodic=False, create_using=None):
38 """Returns the two-dimensional grid graph.
40 The grid graph has each node connected to its four nearest neighbors.
42 Parameters
43 ----------
44 m, n : int or iterable container of nodes
45 If an integer, nodes are from `range(n)`.
46 If a container, elements become the coordinate of the nodes.
48 periodic : bool or iterable
49 If `periodic` is True, both dimensions are periodic. If False, none
50 are periodic. If `periodic` is iterable, it should yield 2 bool
51 values indicating whether the 1st and 2nd axes, respectively, are
52 periodic.
54 create_using : NetworkX graph constructor, optional (default=nx.Graph)
55 Graph type to create. If graph instance, then cleared before populated.
57 Returns
58 -------
59 NetworkX graph
60 The (possibly periodic) grid graph of the specified dimensions.
62 """
63 G = empty_graph(0, create_using)
64 row_name, rows = m
65 col_name, cols = n
66 G.add_nodes_from((i, j) for i in rows for j in cols)
67 G.add_edges_from(((i, j), (pi, j)) for pi, i in pairwise(rows) for j in cols)
68 G.add_edges_from(((i, j), (i, pj)) for i in rows for pj, j in pairwise(cols))
70 try:
71 periodic_r, periodic_c = periodic
72 except TypeError:
73 periodic_r = periodic_c = periodic
75 if periodic_r and len(rows) > 2:
76 first = rows[0]
77 last = rows[-1]
78 G.add_edges_from(((first, j), (last, j)) for j in cols)
79 if periodic_c and len(cols) > 2:
80 first = cols[0]
81 last = cols[-1]
82 G.add_edges_from(((i, first), (i, last)) for i in rows)
83 # both directions for directed
84 if G.is_directed():
85 G.add_edges_from((v, u) for u, v in G.edges())
86 return G
89@nx._dispatch(graphs=None)
90def grid_graph(dim, periodic=False):
91 """Returns the *n*-dimensional grid graph.
93 The dimension *n* is the length of the list `dim` and the size in
94 each dimension is the value of the corresponding list element.
96 Parameters
97 ----------
98 dim : list or tuple of numbers or iterables of nodes
99 'dim' is a tuple or list with, for each dimension, either a number
100 that is the size of that dimension or an iterable of nodes for
101 that dimension. The dimension of the grid_graph is the length
102 of `dim`.
104 periodic : bool or iterable
105 If `periodic` is True, all dimensions are periodic. If False all
106 dimensions are not periodic. If `periodic` is iterable, it should
107 yield `dim` bool values each of which indicates whether the
108 corresponding axis is periodic.
110 Returns
111 -------
112 NetworkX graph
113 The (possibly periodic) grid graph of the specified dimensions.
115 Examples
116 --------
117 To produce a 2 by 3 by 4 grid graph, a graph on 24 nodes:
119 >>> from networkx import grid_graph
120 >>> G = grid_graph(dim=(2, 3, 4))
121 >>> len(G)
122 24
123 >>> G = grid_graph(dim=(range(7, 9), range(3, 6)))
124 >>> len(G)
125 6
126 """
127 from networkx.algorithms.operators.product import cartesian_product
129 if not dim:
130 return empty_graph(0)
132 try:
133 func = (cycle_graph if p else path_graph for p in periodic)
134 except TypeError:
135 func = repeat(cycle_graph if periodic else path_graph)
137 G = next(func)(dim[0])
138 for current_dim in dim[1:]:
139 Gnew = next(func)(current_dim)
140 G = cartesian_product(Gnew, G)
141 # graph G is done but has labels of the form (1, (2, (3, 1))) so relabel
142 H = relabel_nodes(G, flatten)
143 return H
146@nx._dispatch(graphs=None)
147def hypercube_graph(n):
148 """Returns the *n*-dimensional hypercube graph.
150 The nodes are the integers between 0 and ``2 ** n - 1``, inclusive.
152 For more information on the hypercube graph, see the Wikipedia
153 article `Hypercube graph`_.
155 .. _Hypercube graph: https://en.wikipedia.org/wiki/Hypercube_graph
157 Parameters
158 ----------
159 n : int
160 The dimension of the hypercube.
161 The number of nodes in the graph will be ``2 ** n``.
163 Returns
164 -------
165 NetworkX graph
166 The hypercube graph of dimension *n*.
167 """
168 dim = n * [2]
169 G = grid_graph(dim)
170 return G
173@nx._dispatch(graphs=None)
174def triangular_lattice_graph(
175 m, n, periodic=False, with_positions=True, create_using=None
176):
177 r"""Returns the $m$ by $n$ triangular lattice graph.
179 The `triangular lattice graph`_ is a two-dimensional `grid graph`_ in
180 which each square unit has a diagonal edge (each grid unit has a chord).
182 The returned graph has $m$ rows and $n$ columns of triangles. Rows and
183 columns include both triangles pointing up and down. Rows form a strip
184 of constant height. Columns form a series of diamond shapes, staggered
185 with the columns on either side. Another way to state the size is that
186 the nodes form a grid of `m+1` rows and `(n + 1) // 2` columns.
187 The odd row nodes are shifted horizontally relative to the even rows.
189 Directed graph types have edges pointed up or right.
191 Positions of nodes are computed by default or `with_positions is True`.
192 The position of each node (embedded in a euclidean plane) is stored in
193 the graph using equilateral triangles with sidelength 1.
194 The height between rows of nodes is thus $\sqrt(3)/2$.
195 Nodes lie in the first quadrant with the node $(0, 0)$ at the origin.
197 .. _triangular lattice graph: http://mathworld.wolfram.com/TriangularGrid.html
198 .. _grid graph: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
199 .. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
201 Parameters
202 ----------
203 m : int
204 The number of rows in the lattice.
206 n : int
207 The number of columns in the lattice.
209 periodic : bool (default: False)
210 If True, join the boundary vertices of the grid using periodic
211 boundary conditions. The join between boundaries is the final row
212 and column of triangles. This means there is one row and one column
213 fewer nodes for the periodic lattice. Periodic lattices require
214 `m >= 3`, `n >= 5` and are allowed but misaligned if `m` or `n` are odd
216 with_positions : bool (default: True)
217 Store the coordinates of each node in the graph node attribute 'pos'.
218 The coordinates provide a lattice with equilateral triangles.
219 Periodic positions shift the nodes vertically in a nonlinear way so
220 the edges don't overlap so much.
222 create_using : NetworkX graph constructor, optional (default=nx.Graph)
223 Graph type to create. If graph instance, then cleared before populated.
225 Returns
226 -------
227 NetworkX graph
228 The *m* by *n* triangular lattice graph.
229 """
230 H = empty_graph(0, create_using)
231 if n == 0 or m == 0:
232 return H
233 if periodic:
234 if n < 5 or m < 3:
235 msg = f"m > 2 and n > 4 required for periodic. m={m}, n={n}"
236 raise NetworkXError(msg)
238 N = (n + 1) // 2 # number of nodes in row
239 rows = range(m + 1)
240 cols = range(N + 1)
241 # Make grid
242 H.add_edges_from(((i, j), (i + 1, j)) for j in rows for i in cols[:N])
243 H.add_edges_from(((i, j), (i, j + 1)) for j in rows[:m] for i in cols)
244 # add diagonals
245 H.add_edges_from(((i, j), (i + 1, j + 1)) for j in rows[1:m:2] for i in cols[:N])
246 H.add_edges_from(((i + 1, j), (i, j + 1)) for j in rows[:m:2] for i in cols[:N])
247 # identify boundary nodes if periodic
248 from networkx.algorithms.minors import contracted_nodes
250 if periodic is True:
251 for i in cols:
252 H = contracted_nodes(H, (i, 0), (i, m))
253 for j in rows[:m]:
254 H = contracted_nodes(H, (0, j), (N, j))
255 elif n % 2:
256 # remove extra nodes
257 H.remove_nodes_from((N, j) for j in rows[1::2])
259 # Add position node attributes
260 if with_positions:
261 ii = (i for i in cols for j in rows)
262 jj = (j for i in cols for j in rows)
263 xx = (0.5 * (j % 2) + i for i in cols for j in rows)
264 h = sqrt(3) / 2
265 if periodic:
266 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
267 else:
268 yy = (h * j for i in cols for j in rows)
269 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in H}
270 set_node_attributes(H, pos, "pos")
271 return H
274@nx._dispatch(graphs=None)
275def hexagonal_lattice_graph(
276 m, n, periodic=False, with_positions=True, create_using=None
277):
278 """Returns an `m` by `n` hexagonal lattice graph.
280 The *hexagonal lattice graph* is a graph whose nodes and edges are
281 the `hexagonal tiling`_ of the plane.
283 The returned graph will have `m` rows and `n` columns of hexagons.
284 `Odd numbered columns`_ are shifted up relative to even numbered columns.
286 Positions of nodes are computed by default or `with_positions is True`.
287 Node positions creating the standard embedding in the plane
288 with sidelength 1 and are stored in the node attribute 'pos'.
289 `pos = nx.get_node_attributes(G, 'pos')` creates a dict ready for drawing.
291 .. _hexagonal tiling: https://en.wikipedia.org/wiki/Hexagonal_tiling
292 .. _Odd numbered columns: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
294 Parameters
295 ----------
296 m : int
297 The number of rows of hexagons in the lattice.
299 n : int
300 The number of columns of hexagons in the lattice.
302 periodic : bool
303 Whether to make a periodic grid by joining the boundary vertices.
304 For this to work `n` must be even and both `n > 1` and `m > 1`.
305 The periodic connections create another row and column of hexagons
306 so these graphs have fewer nodes as boundary nodes are identified.
308 with_positions : bool (default: True)
309 Store the coordinates of each node in the graph node attribute 'pos'.
310 The coordinates provide a lattice with vertical columns of hexagons
311 offset to interleave and cover the plane.
312 Periodic positions shift the nodes vertically in a nonlinear way so
313 the edges don't overlap so much.
315 create_using : NetworkX graph constructor, optional (default=nx.Graph)
316 Graph type to create. If graph instance, then cleared before populated.
317 If graph is directed, edges will point up or right.
319 Returns
320 -------
321 NetworkX graph
322 The *m* by *n* hexagonal lattice graph.
323 """
324 G = empty_graph(0, create_using)
325 if m == 0 or n == 0:
326 return G
327 if periodic and (n % 2 == 1 or m < 2 or n < 2):
328 msg = "periodic hexagonal lattice needs m > 1, n > 1 and even n"
329 raise NetworkXError(msg)
331 M = 2 * m # twice as many nodes as hexagons vertically
332 rows = range(M + 2)
333 cols = range(n + 1)
334 # make lattice
335 col_edges = (((i, j), (i, j + 1)) for i in cols for j in rows[: M + 1])
336 row_edges = (((i, j), (i + 1, j)) for i in cols[:n] for j in rows if i % 2 == j % 2)
337 G.add_edges_from(col_edges)
338 G.add_edges_from(row_edges)
339 # Remove corner nodes with one edge
340 G.remove_node((0, M + 1))
341 G.remove_node((n, (M + 1) * (n % 2)))
343 # identify boundary nodes if periodic
344 from networkx.algorithms.minors import contracted_nodes
346 if periodic:
347 for i in cols[:n]:
348 G = contracted_nodes(G, (i, 0), (i, M))
349 for i in cols[1:]:
350 G = contracted_nodes(G, (i, 1), (i, M + 1))
351 for j in rows[1:M]:
352 G = contracted_nodes(G, (0, j), (n, j))
353 G.remove_node((n, M))
355 # calc position in embedded space
356 ii = (i for i in cols for j in rows)
357 jj = (j for i in cols for j in rows)
358 xx = (0.5 + i + i // 2 + (j % 2) * ((i % 2) - 0.5) for i in cols for j in rows)
359 h = sqrt(3) / 2
360 if periodic:
361 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
362 else:
363 yy = (h * j for i in cols for j in rows)
364 # exclude nodes not in G
365 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in G}
366 set_node_attributes(G, pos, "pos")
367 return G