ioftools / networkxMiCe / networkxmaster / networkx / generators / lattice.py @ 5cef0f13
History  View  Annotate  Download (13.2 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 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://wwwcsstudents.stanford.edu/~amitp/gameprogramming/grids/

24 
.. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling

25 

26 
"""

27 
from __future__ import division 
28  
29 
from math import sqrt 
30  
31 
from networkx.classes import Graph 
32 
from networkx.classes import set_node_attributes 
33 
from networkx.algorithms.minors import contracted_nodes 
34 
from networkx.algorithms.operators.product import cartesian_product 
35 
from networkx.exception import NetworkXError 
36 
from networkx.relabel import relabel_nodes 
37 
from networkx.utils import flatten 
38 
from networkx.utils import is_list_of_ints 
39 
from networkx.utils import nodes_or_number 
40 
from networkx.utils import pairwise 
41 
from networkx.generators.classic import cycle_graph 
42 
from networkx.generators.classic import empty_graph 
43 
from networkx.generators.classic import path_graph 
44  
45 
__all__ = ['grid_2d_graph', 'grid_graph', 'hypercube_graph', 
46 
'triangular_lattice_graph', 'hexagonal_lattice_graph'] 
47  
48  
49 
@nodes_or_number([0, 1]) 
50 
def grid_2d_graph(m, n, periodic=False, create_using=None): 
51 
"""Returns the twodimensional grid graph.

52 

53 
The grid graph has each node connected to its four nearest neighbors.

54 

55 
Parameters

56 


57 
m, n : int or iterable container of nodes

58 
If an integer, nodes are from `range(n)`.

59 
If a container, elements become the coordinate of the nodes.

60 

61 
periodic : bool (default: False)

62 
If this is ``True`` the nodes on the grid boundaries are joined

63 
to the corresponding nodes on the opposite grid boundaries.

64 

65 
create_using : NetworkX graph constructor, optional (default=nx.Graph)

66 
Graph type to create. If graph instance, then cleared before populated.

67 

68 
Returns

69 


70 
NetworkX graph

71 
The (possibly periodic) grid graph of the specified dimensions.

72 

73 
"""

74 
G = empty_graph(0, create_using)

75 
row_name, rows = m 
76 
col_name, cols = n 
77 
G.add_nodes_from((i, j) for i in rows for j in cols) 
78 
G.add_edges_from(((i, j), (pi, j)) 
79 
for pi, i in pairwise(rows) for j in cols) 
80 
G.add_edges_from(((i, j), (i, pj)) 
81 
for i in rows for pj, j in pairwise(cols)) 
82 
if periodic is True: 
83 
if len(rows) > 2: 
84 
first = rows[0]

85 
last = rows[1]

86 
G.add_edges_from(((first, j), (last, j)) for j in cols) 
87 
if len(cols) > 2: 
88 
first = cols[0]

89 
last = cols[1]

90 
G.add_edges_from(((i, first), (i, last)) for i in rows) 
91 
# both directions for directed

92 
if G.is_directed():

93 
G.add_edges_from((v, u) for u, v in G.edges()) 
94 
return G

95  
96  
97 
def grid_graph(dim, periodic=False): 
98 
"""Returns the *n*dimensional grid graph.

99 

100 
The dimension *n* is the length of the list `dim` and the size in

101 
each dimension is the value of the corresponding list element.

102 

103 
Parameters

104 


105 
dim : list or tuple of numbers or iterables of nodes

106 
'dim' is a tuple or list with, for each dimension, either a number

107 
that is the size of that dimension or an iterable of nodes for

108 
that dimension. The dimension of the grid_graph is the length

109 
of `dim`.

110 

111 
periodic : bool

112 
If `periodic is True` the nodes on the grid boundaries are joined

113 
to the corresponding nodes on the opposite grid boundaries.

114 

115 
Returns

116 


117 
NetworkX graph

118 
The (possibly periodic) grid graph of the specified dimensions.

119 

120 
Examples

121 


122 
To produce a 2 by 3 by 4 grid graph, a graph on 24 nodes:

123 

124 
>>> from networkx import grid_graph

125 
>>> G = grid_graph(dim=[2, 3, 4])

126 
>>> len(G)

127 
24

128 
>>> G = grid_graph(dim=[range(7, 9), range(3, 6)])

129 
>>> len(G)

130 
6

131 
"""

132 
dlabel = "%s" % dim

133 
if not dim: 
134 
return empty_graph(0) 
135  
136 
func = cycle_graph if periodic else path_graph 
137 
G = func(dim[0])

138 
for current_dim in dim[1:]: 
139 
Gnew = 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

144  
145  
146 
def hypercube_graph(n): 
147 
"""Returns the *n*dimensional hypercube graph.

148 

149 
The nodes are the integers between 0 and ``2 ** n  1``, inclusive.

150 

151 
For more information on the hypercube graph, see the Wikipedia

152 
article `Hypercube graph`_.

153 

154 
.. _Hypercube graph: https://en.wikipedia.org/wiki/Hypercube_graph

155 

156 
Parameters

157 


158 
n : int

159 
The dimension of the hypercube.

160 
The number of nodes in the graph will be ``2 ** n``.

161 

162 
Returns

163 


164 
NetworkX graph

165 
The hypercube graph of dimension *n*.

166 
"""

167 
dim = n * [2]

168 
G = grid_graph(dim) 
169 
return G

170  
171  
172 
def triangular_lattice_graph(m, n, periodic=False, with_positions=True, 
173 
create_using=None):

174 
r"""Returns the $m$ by $n$ triangular lattice graph.

175 

176 
The `triangular lattice graph`_ is a twodimensional `grid graph`_ in

177 
which each square unit has a diagonal edge (each grid unit has a chord).

178 

179 
The returned graph has $m$ rows and $n$ columns of triangles. Rows and

180 
columns include both triangles pointing up and down. Rows form a strip

181 
of constant height. Columns form a series of diamond shapes, staggered

182 
with the columns on either side. Another way to state the size is that

183 
the nodes form a grid of `m+1` rows and `(n + 1) // 2` columns.

184 
The odd row nodes are shifted horizontally relative to the even rows.

185 

186 
Directed graph types have edges pointed up or right.

187 

188 
Positions of nodes are computed by default or `with_positions is True`.

189 
The position of each node (embedded in a euclidean plane) is stored in

190 
the graph using equilateral triangles with sidelength 1.

191 
The height between rows of nodes is thus $\sqrt(3)/2$.

192 
Nodes lie in the first quadrant with the node $(0, 0)$ at the origin.

193 

194 
.. _triangular lattice graph: http://mathworld.wolfram.com/TriangularGrid.html

195 
.. _grid graph: http://wwwcsstudents.stanford.edu/~amitp/gameprogramming/grids/

196 
.. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling

197 

198 
Parameters

199 


200 
m : int

201 
The number of rows in the lattice.

202 

203 
n : int

204 
The number of columns in the lattice.

205 

206 
periodic : bool (default: False)

207 
If True, join the boundary vertices of the grid using periodic

208 
boundary conditions. The join between boundaries is the final row

209 
and column of triangles. This means there is one row and one column

210 
fewer nodes for the periodic lattice. Periodic lattices require

211 
`m >= 3`, `n >= 5` and are allowed but misaligned if `m` or `n` are odd

212 

213 
with_positions : bool (default: True)

214 
Store the coordinates of each node in the graph node attribute 'pos'.

215 
The coordinates provide a lattice with equilateral triangles.

216 
Periodic positions shift the nodes vertically in a nonlinear way so

217 
the edges don't overlap so much.

218 

219 
create_using : NetworkX graph constructor, optional (default=nx.Graph)

220 
Graph type to create. If graph instance, then cleared before populated.

221 

222 
Returns

223 


224 
NetworkX graph

225 
The *m* by *n* triangular lattice graph.

226 
"""

227 
H = empty_graph(0, create_using)

228 
if n == 0 or m == 0: 
229 
return H

230 
if periodic:

231 
if n < 5 or m < 3: 
232 
msg = "m > 2 and n > 4 required for periodic. m={}, n={}"

233 
raise NetworkXError(msg.format(m, n))

234  
235 
N = (n + 1) // 2 # number of nodes in row 
236 
rows = range(m + 1) 
237 
cols = range(N + 1) 
238 
# Make grid

239 
H.add_edges_from(((i, j), (i + 1, j)) for j in rows for i in cols[:N]) 
240 
H.add_edges_from(((i, j), (i, j + 1)) for j in rows[:m] for i in cols) 
241 
# add diagonals

242 
H.add_edges_from(((i, j), (i + 1, j + 1)) 
243 
for j in rows[1:m:2] for i in cols[:N]) 
244 
H.add_edges_from(((i + 1, j), (i, j + 1)) 
245 
for j in rows[:m:2] for i in cols[:N]) 
246 
# identify boundary nodes if periodic

247 
if periodic is True: 
248 
for i in cols: 
249 
H = contracted_nodes(H, (i, 0), (i, m))

250 
for j in rows[:m]: 
251 
H = contracted_nodes(H, (0, j), (N, j))

252 
elif n % 2: 
253 
# remove extra nodes

254 
H.remove_nodes_from(((N, j) for j in rows[1::2])) 
255  
256 
# Add position node attributes

257 
if with_positions:

258 
ii = (i for i in cols for j in rows) 
259 
jj = (j for i in cols for j in rows) 
260 
xx = (0.5 * (j % 2) + i for i in cols for j in rows) 
261 
h = sqrt(3) / 2 
262 
if periodic:

263 
yy = (h * j + .01 * i * i for i in cols for j in rows) 
264 
else:

265 
yy = (h * j for i in cols for j in rows) 
266 
pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) 
267 
if (i, j) in H} 
268 
set_node_attributes(H, pos, 'pos')

269 
return H

270  
271  
272 
def hexagonal_lattice_graph(m, n, periodic=False, with_positions=True, 
273 
create_using=None):

274 
"""Returns an `m` by `n` hexagonal lattice graph.

275 

276 
The *hexagonal lattice graph* is a graph whose nodes and edges are

277 
the `hexagonal tiling`_ of the plane.

278 

279 
The returned graph will have `m` rows and `n` columns of hexagons.

280 
`Odd numbered columns`_ are shifted up relative to even numbered columns.

281 

282 
Positions of nodes are computed by default or `with_positions is True`.

283 
Node positions creating the standard embedding in the plane

284 
with sidelength 1 and are stored in the node attribute 'pos'.

285 
`pos = nx.get_node_attributes(G, 'pos')` creates a dict ready for drawing.

286 

287 
.. _hexagonal tiling: https://en.wikipedia.org/wiki/Hexagonal_tiling

288 
.. _Odd numbered columns: http://wwwcsstudents.stanford.edu/~amitp/gameprogramming/grids/

289 

290 
Parameters

291 


292 
m : int

293 
The number of rows of hexagons in the lattice.

294 

295 
n : int

296 
The number of columns of hexagons in the lattice.

297 

298 
periodic : bool

299 
Whether to make a periodic grid by joining the boundary vertices.

300 
For this to work `n` must be odd and both `n > 1` and `m > 1`.

301 
The periodic connections create another row and column of hexagons

302 
so these graphs have fewer nodes as boundary nodes are identified.

303 

304 
with_positions : bool (default: True)

305 
Store the coordinates of each node in the graph node attribute 'pos'.

306 
The coordinates provide a lattice with vertical columns of hexagons

307 
offset to interleave and cover the plane.

308 
Periodic positions shift the nodes vertically in a nonlinear way so

309 
the edges don't overlap so much.

310 

311 
create_using : NetworkX graph constructor, optional (default=nx.Graph)

312 
Graph type to create. If graph instance, then cleared before populated.

313 
If graph is directed, edges will point up or right.

314 

315 
Returns

316 


317 
NetworkX graph

318 
The *m* by *n* hexagonal lattice graph.

319 
"""

320 
G = empty_graph(0, create_using)

321 
if m == 0 or n == 0: 
322 
return G

323 
if periodic and (n % 2 == 1 or m < 2 or n < 2): 
324 
msg = "periodic hexagonal lattice needs m > 1, n > 1 and even n"

325 
raise NetworkXError(msg)

326  
327 
M = 2 * m # twice as many nodes as hexagons vertically 
328 
rows = range(M + 2) 
329 
cols = range(n + 1) 
330 
# make lattice

331 
col_edges = (((i, j), (i, j + 1)) for i in cols for j in rows[:M + 1]) 
332 
row_edges = (((i, j), (i + 1, j)) for i in cols[:n] for j in rows 
333 
if i % 2 == j % 2) 
334 
G.add_edges_from(col_edges) 
335 
G.add_edges_from(row_edges) 
336 
# Remove corner nodes with one edge

337 
G.remove_node((0, M + 1)) 
338 
G.remove_node((n, (M + 1) * (n % 2))) 
339  
340 
# identify boundary nodes if periodic

341 
if periodic:

342 
for i in cols[:n]: 
343 
G = contracted_nodes(G, (i, 0), (i, M))

344 
for i in cols[1:]: 
345 
G = contracted_nodes(G, (i, 1), (i, M + 1)) 
346 
for j in rows[1:M]: 
347 
G = contracted_nodes(G, (0, j), (n, j))

348 
G.remove_node((n, M)) 
349  
350 
# calc position in embedded space

351 
ii = (i for i in cols for j in rows) 
352 
jj = (j for i in cols for j in rows) 
353 
xx = (0.5 + i + i // 2 + (j % 2) * ((i % 2)  .5) 
354 
for i in cols for j in rows) 
355 
h = sqrt(3) / 2 
356 
if periodic:

357 
yy = (h * j + .01 * i * i for i in cols for j in rows) 
358 
else:

359 
yy = (h * j for i in cols for j in rows) 
360 
# exclude nodes not in G

361 
pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in G} 
362 
set_node_attributes(G, pos, 'pos')

363 
return G
