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 """
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._dispatchable(graphs=None, returns_graph=True)
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 collections.abc import Iterable
129 from networkx.algorithms.operators.product import cartesian_product
131 if not dim:
132 return empty_graph(0)
134 periodic = repeat(periodic) if not isinstance(periodic, Iterable) else periodic
135 func = (cycle_graph if p else path_graph for p in periodic)
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._dispatchable(graphs=None, returns_graph=True)
147def hypercube_graph(n):
148 """Returns the *n*-dimensional hypercube graph.
150 The *n*-dimensional hypercube graph [1]_ has ``2**n`` nodes, each represented as
151 a binary integer in the form of a tuple of 0's and 1's. Edges exist between
152 nodes that differ in exactly one bit.
154 Parameters
155 ----------
156 n : int
157 Dimension of the hypercube, must be a positive integer.
159 Returns
160 -------
161 networkx.Graph
162 The n-dimensional hypercube graph as an undirected graph.
164 Examples
165 --------
166 >>> G = nx.hypercube_graph(3)
167 >>> list(G.neighbors((0, 0, 0)))
168 [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
170 References
171 ----------
172 .. [1] https://en.wikipedia.org/wiki/Hypercube_graph
173 """
174 dim = n * [2]
175 G = grid_graph(dim)
176 return G
179@nx._dispatchable(graphs=None, returns_graph=True)
180def triangular_lattice_graph(
181 m, n, periodic=False, with_positions=True, create_using=None
182):
183 r"""Returns the $m$ by $n$ triangular lattice graph.
185 The `triangular lattice graph`_ is a two-dimensional `grid graph`_ in
186 which each square unit has a diagonal edge (each grid unit has a chord).
188 The returned graph has $m$ rows and $n$ columns of triangles. Rows and
189 columns include both triangles pointing up and down. Rows form a strip
190 of constant height. Columns form a series of diamond shapes, staggered
191 with the columns on either side. Another way to state the size is that
192 the nodes form a grid of `m+1` rows and `(n + 1) // 2` columns.
193 The odd row nodes are shifted horizontally relative to the even rows.
195 Directed graph types have edges pointed up or right.
197 Positions of nodes are computed by default or `with_positions is True`.
198 The position of each node (embedded in a euclidean plane) is stored in
199 the graph using equilateral triangles with sidelength 1.
200 The height between rows of nodes is thus $\sqrt(3)/2$.
201 Nodes lie in the first quadrant with the node $(0, 0)$ at the origin.
203 .. _triangular lattice graph: http://mathworld.wolfram.com/TriangularGrid.html
204 .. _grid graph: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
205 .. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
207 Parameters
208 ----------
209 m : int
210 The number of rows in the lattice.
212 n : int
213 The number of columns in the lattice.
215 periodic : bool (default: False)
216 If True, join the boundary vertices of the grid using periodic
217 boundary conditions. The join between boundaries is the final row
218 and column of triangles. This means there is one row and one column
219 fewer nodes for the periodic lattice. Periodic lattices require
220 `m >= 3`, `n >= 5` and are allowed but misaligned if `m` or `n` are odd
222 with_positions : bool (default: True)
223 Store the coordinates of each node in the graph node attribute 'pos'.
224 The coordinates provide a lattice with equilateral triangles.
225 Periodic positions shift the nodes vertically in a nonlinear way so
226 the edges don't overlap so much.
228 create_using : NetworkX graph constructor, optional (default=nx.Graph)
229 Graph type to create. If graph instance, then cleared before populated.
231 Returns
232 -------
233 NetworkX graph
234 The *m* by *n* triangular lattice graph.
235 """
236 H = empty_graph(0, create_using)
237 if n == 0 or m == 0:
238 return H
239 if periodic:
240 if n < 5 or m < 3:
241 msg = f"m > 2 and n > 4 required for periodic. m={m}, n={n}"
242 raise NetworkXError(msg)
244 N = (n + 1) // 2 # number of nodes in row
245 rows = range(m + 1)
246 cols = range(N + 1)
247 # Make grid
248 H.add_edges_from(((i, j), (i + 1, j)) for j in rows for i in cols[:N])
249 H.add_edges_from(((i, j), (i, j + 1)) for j in rows[:m] for i in cols)
250 # add diagonals
251 H.add_edges_from(((i, j), (i + 1, j + 1)) for j in rows[1:m:2] for i in cols[:N])
252 H.add_edges_from(((i + 1, j), (i, j + 1)) for j in rows[:m:2] for i in cols[:N])
253 # identify boundary nodes if periodic
254 from networkx.algorithms.minors import contracted_nodes
256 if periodic is True:
257 for i in cols:
258 H = contracted_nodes(H, (i, 0), (i, m))
259 for j in rows[:m]:
260 H = contracted_nodes(H, (0, j), (N, j))
261 elif n % 2:
262 # remove extra nodes
263 H.remove_nodes_from((N, j) for j in rows[1::2])
265 # Add position node attributes
266 if with_positions:
267 ii = (i for i in cols for j in rows)
268 jj = (j for i in cols for j in rows)
269 xx = (0.5 * (j % 2) + i for i in cols for j in rows)
270 h = sqrt(3) / 2
271 if periodic:
272 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
273 else:
274 yy = (h * j for i in cols for j in rows)
275 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in H}
276 set_node_attributes(H, pos, "pos")
277 return H
280@nx._dispatchable(graphs=None, returns_graph=True)
281def hexagonal_lattice_graph(
282 m, n, periodic=False, with_positions=True, create_using=None
283):
284 """Returns an `m` by `n` hexagonal lattice graph.
286 The *hexagonal lattice graph* is a graph whose nodes and edges are
287 the `hexagonal tiling`_ of the plane.
289 The returned graph will have `m` rows and `n` columns of hexagons.
290 `Odd numbered columns`_ are shifted up relative to even numbered columns.
292 Positions of nodes are computed by default or `with_positions is True`.
293 Node positions creating the standard embedding in the plane
294 with sidelength 1 and are stored in the node attribute 'pos'.
295 `pos = nx.get_node_attributes(G, 'pos')` creates a dict ready for drawing.
297 .. _hexagonal tiling: https://en.wikipedia.org/wiki/Hexagonal_tiling
298 .. _Odd numbered columns: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
300 Parameters
301 ----------
302 m : int
303 The number of rows of hexagons in the lattice.
305 n : int
306 The number of columns of hexagons in the lattice.
308 periodic : bool
309 Whether to make a periodic grid by joining the boundary vertices.
310 For this to work `n` must be even and both `n > 1` and `m > 1`.
311 The periodic connections create another row and column of hexagons
312 so these graphs have fewer nodes as boundary nodes are identified.
314 with_positions : bool (default: True)
315 Store the coordinates of each node in the graph node attribute 'pos'.
316 The coordinates provide a lattice with vertical columns of hexagons
317 offset to interleave and cover the plane.
318 Periodic positions shift the nodes vertically in a nonlinear way so
319 the edges don't overlap so much.
321 create_using : NetworkX graph constructor, optional (default=nx.Graph)
322 Graph type to create. If graph instance, then cleared before populated.
323 If graph is directed, edges will point up or right.
325 Returns
326 -------
327 NetworkX graph
328 The *m* by *n* hexagonal lattice graph.
329 """
330 G = empty_graph(0, create_using)
331 if m == 0 or n == 0:
332 return G
333 if periodic and (n % 2 == 1 or m < 2 or n < 2):
334 msg = "periodic hexagonal lattice needs m > 1, n > 1 and even n"
335 raise NetworkXError(msg)
337 M = 2 * m # twice as many nodes as hexagons vertically
338 rows = range(M + 2)
339 cols = range(n + 1)
340 # make lattice
341 col_edges = (((i, j), (i, j + 1)) for i in cols for j in rows[: M + 1])
342 row_edges = (((i, j), (i + 1, j)) for i in cols[:n] for j in rows if i % 2 == j % 2)
343 G.add_edges_from(col_edges)
344 G.add_edges_from(row_edges)
345 # Remove corner nodes with one edge
346 G.remove_node((0, M + 1))
347 G.remove_node((n, (M + 1) * (n % 2)))
349 # identify boundary nodes if periodic
350 from networkx.algorithms.minors import contracted_nodes
352 if periodic:
353 for i in cols[:n]:
354 G = contracted_nodes(G, (i, 0), (i, M))
355 for i in cols[1:]:
356 G = contracted_nodes(G, (i, 1), (i, M + 1))
357 for j in rows[1:M]:
358 G = contracted_nodes(G, (0, j), (n, j))
359 G.remove_node((n, M))
361 # calc position in embedded space
362 ii = (i for i in cols for j in rows)
363 jj = (j for i in cols for j in rows)
364 xx = (0.5 + i + i // 2 + (j % 2) * ((i % 2) - 0.5) for i in cols for j in rows)
365 h = sqrt(3) / 2
366 if periodic:
367 yy = (h * j + 0.01 * i * i for i in cols for j in rows)
368 else:
369 yy = (h * j for i in cols for j in rows)
370 # exclude nodes not in G
371 pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in G}
372 set_node_attributes(G, pos, "pos")
373 return G