Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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@nx._dispatchable(graphs=None, returns_graph=True)
36@nodes_or_number([0, 1])
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 See Also
63 --------
64 triangular_lattice_graph, hexagonal_lattice_graph :
65 Other 2D lattice graphs
66 grid_graph, hypercube_graph :
67 N-dimensional lattice graphs
68 """
69 G = empty_graph(0, create_using)
70 row_name, rows = m
71 col_name, cols = n
72 G.add_nodes_from((i, j) for i in rows for j in cols)
73 G.add_edges_from(((i, j), (pi, j)) for pi, i in pairwise(rows) for j in cols)
74 G.add_edges_from(((i, j), (i, pj)) for i in rows for pj, j in pairwise(cols))
76 try:
77 periodic_r, periodic_c = periodic
78 except TypeError:
79 periodic_r = periodic_c = periodic
81 if periodic_r and len(rows) > 2:
82 first = rows[0]
83 last = rows[-1]
84 G.add_edges_from(((first, j), (last, j)) for j in cols)
85 if periodic_c and len(cols) > 2:
86 first = cols[0]
87 last = cols[-1]
88 G.add_edges_from(((i, first), (i, last)) for i in rows)
89 # both directions for directed
90 if G.is_directed():
91 G.add_edges_from((v, u) for u, v in G.edges())
92 return G
95@nx._dispatchable(graphs=None, returns_graph=True)
96def grid_graph(dim, periodic=False):
97 """Returns the *n*-dimensional grid graph.
99 The dimension *n* is the length of the list `dim` and the size in
100 each dimension is the value of the corresponding list element.
102 Parameters
103 ----------
104 dim : list or tuple of numbers or iterables of nodes
105 'dim' is a tuple or list with, for each dimension, either a number
106 that is the size of that dimension or an iterable of nodes for
107 that dimension. The dimension of the grid_graph is the length
108 of `dim`.
110 periodic : bool or iterable
111 If `periodic` is True, all dimensions are periodic. If False all
112 dimensions are not periodic. If `periodic` is iterable, it should
113 yield `dim` bool values each of which indicates whether the
114 corresponding axis is periodic.
116 Returns
117 -------
118 NetworkX graph
119 The (possibly periodic) grid graph of the specified dimensions.
121 See Also
122 --------
123 grid_2d_graph, triangular_lattice_graph, hexagonal_lattice_graph :
124 2D lattice graphs
125 hypercube_graph :
126 A special case of `grid_graph` where all elements of `dim` are identical
128 Examples
129 --------
130 To produce a 2 by 3 by 4 grid graph, a graph on 24 nodes:
132 >>> from networkx import grid_graph
133 >>> G = grid_graph(dim=(2, 3, 4))
134 >>> len(G)
135 24
136 >>> G = grid_graph(dim=(range(7, 9), range(3, 6)))
137 >>> len(G)
138 6
139 """
140 from collections.abc import Iterable
142 from networkx.algorithms.operators.product import cartesian_product
144 if not dim:
145 return empty_graph(0)
147 periodic = repeat(periodic) if not isinstance(periodic, Iterable) else periodic
148 func = (cycle_graph if p else path_graph for p in periodic)
150 G = next(func)(dim[0])
151 for current_dim in dim[1:]:
152 Gnew = next(func)(current_dim)
153 G = cartesian_product(Gnew, G)
154 # graph G is done but has labels of the form (1, (2, (3, 1))) so relabel
155 H = relabel_nodes(G, flatten)
156 return H
159@nx._dispatchable(graphs=None, returns_graph=True)
160def hypercube_graph(n):
161 """Returns the *n*-dimensional hypercube graph.
163 The *n*-dimensional hypercube graph [1]_ has ``2**n`` nodes, each represented as
164 a binary integer in the form of a tuple of 0's and 1's. Edges exist between
165 nodes that differ in exactly one bit.
167 Parameters
168 ----------
169 n : int
170 Dimension of the hypercube, must be a positive integer.
172 Returns
173 -------
174 networkx.Graph
175 The n-dimensional hypercube graph as an undirected graph.
177 See Also
178 --------
179 grid_2d_graph, triangular_lattice_graph, hexagonal_lattice_graph :
180 2D lattice graphs
181 grid_graph :
182 A more general N-dimensional grid
184 Examples
185 --------
186 >>> G = nx.hypercube_graph(3)
187 >>> list(G.neighbors((0, 0, 0)))
188 [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
190 References
191 ----------
192 .. [1] https://en.wikipedia.org/wiki/Hypercube_graph
193 """
194 dim = n * [2]
195 G = grid_graph(dim)
196 return G
199@nx._dispatchable(graphs=None, returns_graph=True)
200def triangular_lattice_graph(
201 m, n, periodic=False, with_positions=True, create_using=None
202):
203 r"""Returns the $m$ by $n$ triangular lattice graph.
205 The `triangular lattice graph`_ is a two-dimensional `grid graph`_ in
206 which each square unit has a diagonal edge (each grid unit has a chord).
208 The returned graph has $m$ rows and $n$ columns of triangles. Rows and
209 columns include both triangles pointing up and down. Rows form a strip
210 of constant height. Columns form a series of diamond shapes, staggered
211 with the columns on either side. Another way to state the size is that
212 the nodes form a grid of `m+1` rows and `(n + 1) // 2` columns.
213 The odd row nodes are shifted horizontally relative to the even rows.
215 Directed graph types have edges pointed up or right.
217 Positions of nodes are computed by default or `with_positions is True`.
218 The position of each node (embedded in a euclidean plane) is stored in
219 the graph using equilateral triangles with sidelength 1.
220 The height between rows of nodes is thus $\sqrt(3)/2$.
221 Nodes lie in the first quadrant with the node $(0, 0)$ at the origin.
223 .. _triangular lattice graph: http://mathworld.wolfram.com/TriangularGrid.html
224 .. _grid graph: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
225 .. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
227 Parameters
228 ----------
229 m : int
230 The number of rows in the lattice.
232 n : int
233 The number of columns in the lattice.
235 periodic : bool (default: False)
236 If True, join the boundary vertices of the grid using periodic
237 boundary conditions. The join between boundaries is the final row
238 and column of triangles. This means there is one row and one column
239 fewer nodes for the periodic lattice. Periodic lattices require
240 `m >= 3`, `n >= 5` and are allowed but misaligned if `m` or `n` are odd
242 with_positions : bool (default: True)
243 Store the coordinates of each node in the graph node attribute 'pos'.
244 The coordinates provide a lattice with equilateral triangles.
245 Periodic positions shift the nodes vertically in a nonlinear way so
246 the edges don't overlap so much.
248 create_using : NetworkX graph constructor, optional (default=nx.Graph)
249 Graph type to create. If graph instance, then cleared before populated.
251 Returns
252 -------
253 NetworkX graph
254 The *m* by *n* triangular lattice graph.
256 See Also
257 --------
258 grid_2d_graph, hexagonal_lattice_graph :
259 Other 2D lattice graphs
260 grid_graph, hypercube_graph :
261 N-dimensional lattice graphs
262 """
263 H = empty_graph(0, create_using)
264 if n == 0 or m == 0:
265 return H
266 if periodic:
267 if n < 5 or m < 3:
268 msg = f"m > 2 and n > 4 required for periodic. m={m}, n={n}"
269 raise NetworkXError(msg)
271 N = (n + 1) // 2 # number of nodes in row
272 rows = range(m + 1)
273 cols = range(N + 1)
274 # Make grid
275 H.add_edges_from(((i, j), (i + 1, j)) for j in rows for i in cols[:N])
276 H.add_edges_from(((i, j), (i, j + 1)) for j in rows[:m] for i in cols)
277 # add diagonals
278 H.add_edges_from(((i, j), (i + 1, j + 1)) for j in rows[1:m:2] for i in cols[:N])
279 H.add_edges_from(((i + 1, j), (i, j + 1)) for j in rows[:m:2] for i in cols[:N])
281 # identify boundary nodes if periodic
282 if periodic is True:
283 for i in cols:
284 H = nx.contracted_nodes(H, (i, 0), (i, m), store_contraction_as=None)
285 for j in rows[:m]:
286 H = nx.contracted_nodes(H, (0, j), (N, j), store_contraction_as=None)
287 elif n % 2:
288 # remove extra nodes
289 H.remove_nodes_from((N, j) for j in rows[1::2])
291 # Add position node attributes
292 if with_positions:
293 ii = (i for i in cols for j in rows)
294 jj = (j for i in cols for j in rows)
295 xx = (0.5 * (j % 2) + i for i in cols for j in rows)
296 h = sqrt(3) / 2
297 if periodic:
298 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
299 else:
300 yy = (h * j for i in cols for j in rows)
301 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in H}
302 set_node_attributes(H, pos, "pos")
303 return H
306@nx._dispatchable(graphs=None, returns_graph=True)
307def hexagonal_lattice_graph(
308 m, n, periodic=False, with_positions=True, create_using=None
309):
310 """Returns an `m` by `n` hexagonal lattice graph.
312 The *hexagonal lattice graph* is a graph whose nodes and edges are
313 the `hexagonal tiling`_ of the plane.
315 The returned graph will have `m` rows and `n` columns of hexagons.
316 `Odd numbered columns`_ are shifted up relative to even numbered columns.
318 Positions of nodes are computed by default or `with_positions is True`.
319 Node positions creating the standard embedding in the plane
320 with sidelength 1 and are stored in the node attribute 'pos'.
321 `pos = nx.get_node_attributes(G, 'pos')` creates a dict ready for drawing.
323 .. _hexagonal tiling: https://en.wikipedia.org/wiki/Hexagonal_tiling
324 .. _Odd numbered columns: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
326 Parameters
327 ----------
328 m : int
329 The number of rows of hexagons in the lattice.
331 n : int
332 The number of columns of hexagons in the lattice.
334 periodic : bool
335 Whether to make a periodic grid by joining the boundary vertices.
336 For this to work `n` must be even and both `n > 1` and `m > 1`.
337 The periodic connections create another row and column of hexagons
338 so these graphs have fewer nodes as boundary nodes are identified.
340 with_positions : bool (default: True)
341 Store the coordinates of each node in the graph node attribute 'pos'.
342 The coordinates provide a lattice with vertical columns of hexagons
343 offset to interleave and cover the plane.
344 Periodic positions shift the nodes vertically in a nonlinear way so
345 the edges don't overlap so much.
347 create_using : NetworkX graph constructor, optional (default=nx.Graph)
348 Graph type to create. If graph instance, then cleared before populated.
349 If graph is directed, edges will point up or right.
351 Returns
352 -------
353 NetworkX graph
354 The *m* by *n* hexagonal lattice graph.
356 See Also
357 --------
358 grid_2d_graph, triangular_lattice_graph :
359 Other 2D lattice graphs
360 grid_graph, hypercube_graph :
361 N-dimensional lattice graphs
362 """
363 G = empty_graph(0, create_using)
364 if m == 0 or n == 0:
365 return G
366 if periodic and (n % 2 == 1 or m < 2 or n < 2):
367 msg = "periodic hexagonal lattice needs m > 1, n > 1 and even n"
368 raise NetworkXError(msg)
370 M = 2 * m # twice as many nodes as hexagons vertically
371 rows = range(M + 2)
372 cols = range(n + 1)
373 # make lattice
374 col_edges = (((i, j), (i, j + 1)) for i in cols for j in rows[: M + 1])
375 row_edges = (((i, j), (i + 1, j)) for i in cols[:n] for j in rows if i % 2 == j % 2)
376 G.add_edges_from(col_edges)
377 G.add_edges_from(row_edges)
378 # Remove corner nodes with one edge
379 G.remove_node((0, M + 1))
380 G.remove_node((n, (M + 1) * (n % 2)))
382 # identify boundary nodes if periodic
383 if periodic:
384 for i in cols[:n]:
385 G = nx.contracted_nodes(G, (i, 0), (i, M), store_contraction_as=None)
386 for i in cols[1:]:
387 G = nx.contracted_nodes(G, (i, 1), (i, M + 1), store_contraction_as=None)
388 for j in rows[1:M]:
389 G = nx.contracted_nodes(G, (0, j), (n, j), store_contraction_as=None)
390 G.remove_node((n, M))
392 # calc position in embedded space
393 if with_positions:
394 ii = (i for i in cols for j in rows)
395 jj = (j for i in cols for j in rows)
396 xx = (0.5 + i + i // 2 + (j % 2) * ((i % 2) - 0.5) for i in cols for j in rows)
397 h = sqrt(3) / 2
398 if periodic:
399 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
400 else:
401 yy = (h * j for i in cols for j in rows)
402 # exclude nodes not in G
403 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in G}
404 set_node_attributes(G, pos, "pos")
405 return G