Mercurial > repos > guerler > springsuite

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