Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / lattice.py @ 5cef0f13

History | View | Annotate | Download (13.2 KB)

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
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 two-dimensional 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 two-dimensional `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://www-cs-students.stanford.edu/~amitp/game-programming/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://www-cs-students.stanford.edu/~amitp/game-programming/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