--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/planemo/lib/python3.7/site-packages/networkx/generators/lattice.py	Fri Jul 31 00:32:28 2020 -0400
@@ -0,0 +1,361 @@
+# -*- coding: utf-8 -*-
+#    Copyright (C) 2004-2019 by
+#    Aric Hagberg <hagberg@lanl.gov>
+#    Dan Schult <dschult@colgate.edu>
+#    Pieter Swart <swart@lanl.gov>
+#    All rights reserved.
+#    BSD license.
+#
+# Authors: Aric Hagberg (hagberg@lanl.gov)
+#          Pieter Swart (swart@lanl.gov)
+#          Joel Miller (jmiller@lanl.gov)
+#          Dan Schult (dschult@lanl.gov)
+"""Functions for generating grid graphs and lattices
+
+The :func:`grid_2d_graph`, :func:`triangular_lattice_graph`, and
+:func:`hexagonal_lattice_graph` functions correspond to the three
+`regular tilings of the plane`_, the square, triangular, and hexagonal
+tilings, respectively. :func:`grid_graph` and :func:`hypercube_graph`
+are similar for arbitrary dimensions. Useful relevant discussion can
+be found about `Triangular Tiling`_, and `Square, Hex and Triangle Grids`_
+
+.. _regular tilings of the plane: https://en.wikipedia.org/wiki/List_of_regular_polytopes_and_compounds#Euclidean_tilings
+.. _Square, Hex and Triangle Grids: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
+.. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
+
+"""
+
+from math import sqrt
+
+from networkx.classes import Graph
+from networkx.classes import set_node_attributes
+from networkx.algorithms.minors import contracted_nodes
+from networkx.algorithms.operators.product import cartesian_product
+from networkx.exception import NetworkXError
+from networkx.relabel import relabel_nodes
+from networkx.utils import flatten
+from networkx.utils import nodes_or_number
+from networkx.utils import pairwise
+from networkx.generators.classic import cycle_graph
+from networkx.generators.classic import empty_graph
+from networkx.generators.classic import path_graph
+
+__all__ = ['grid_2d_graph', 'grid_graph', 'hypercube_graph',
+           'triangular_lattice_graph', 'hexagonal_lattice_graph']
+
+
+@nodes_or_number([0, 1])
+def grid_2d_graph(m, n, periodic=False, create_using=None):
+    """Returns the two-dimensional grid graph.
+
+    The grid graph has each node connected to its four nearest neighbors.
+
+    Parameters
+    ----------
+    m, n : int or iterable container of nodes
+        If an integer, nodes are from `range(n)`.
+        If a container, elements become the coordinate of the nodes.
+
+    periodic : bool (default: False)
+        If this is ``True`` the nodes on the grid boundaries are joined
+        to the corresponding nodes on the opposite grid boundaries.
+
+    create_using : NetworkX graph constructor, optional (default=nx.Graph)
+        Graph type to create. If graph instance, then cleared before populated.
+
+    Returns
+    -------
+    NetworkX graph
+        The (possibly periodic) grid graph of the specified dimensions.
+
+    """
+    G = empty_graph(0, create_using)
+    row_name, rows = m
+    col_name, cols = n
+    G.add_nodes_from((i, j) for i in rows for j in cols)
+    G.add_edges_from(((i, j), (pi, j))
+                     for pi, i in pairwise(rows) for j in cols)
+    G.add_edges_from(((i, j), (i, pj))
+                     for i in rows for pj, j in pairwise(cols))
+    if periodic is True:
+        if len(rows) > 2:
+            first = rows[0]
+            last = rows[-1]
+            G.add_edges_from(((first, j), (last, j)) for j in cols)
+        if len(cols) > 2:
+            first = cols[0]
+            last = cols[-1]
+            G.add_edges_from(((i, first), (i, last)) for i in rows)
+    # both directions for directed
+    if G.is_directed():
+        G.add_edges_from((v, u) for u, v in G.edges())
+    return G
+
+
+def grid_graph(dim, periodic=False):
+    """Returns the *n*-dimensional grid graph.
+
+    The dimension *n* is the length of the list `dim` and the size in
+    each dimension is the value of the corresponding list element.
+
+    Parameters
+    ----------
+    dim : list or tuple of numbers or iterables of nodes
+        'dim' is a tuple or list with, for each dimension, either a number
+        that is the size of that dimension or an iterable of nodes for
+        that dimension. The dimension of the grid_graph is the length
+        of `dim`.
+
+    periodic : bool
+        If `periodic is True` the nodes on the grid boundaries are joined
+        to the corresponding nodes on the opposite grid boundaries.
+
+    Returns
+    -------
+    NetworkX graph
+        The (possibly periodic) grid graph of the specified dimensions.
+
+    Examples
+    --------
+    To produce a 2 by 3 by 4 grid graph, a graph on 24 nodes:
+
+    >>> from networkx import grid_graph
+    >>> G = grid_graph(dim=[2, 3, 4])
+    >>> len(G)
+    24
+    >>> G = grid_graph(dim=[range(7, 9), range(3, 6)])
+    >>> len(G)
+    6
+    """
+    dlabel = "%s" % dim
+    if not dim:
+        return empty_graph(0)
+
+    func = cycle_graph if periodic else path_graph
+    G = func(dim[0])
+    for current_dim in dim[1:]:
+        Gnew = func(current_dim)
+        G = cartesian_product(Gnew, G)
+    # graph G is done but has labels of the form (1, (2, (3, 1))) so relabel
+    H = relabel_nodes(G, flatten)
+    return H
+
+
+def hypercube_graph(n):
+    """Returns the *n*-dimensional hypercube graph.
+
+    The nodes are the integers between 0 and ``2 ** n - 1``, inclusive.
+
+    For more information on the hypercube graph, see the Wikipedia
+    article `Hypercube graph`_.
+
+    .. _Hypercube graph: https://en.wikipedia.org/wiki/Hypercube_graph
+
+    Parameters
+    ----------
+    n : int
+        The dimension of the hypercube.
+        The number of nodes in the graph will be ``2 ** n``.
+
+    Returns
+    -------
+    NetworkX graph
+        The hypercube graph of dimension *n*.
+    """
+    dim = n * [2]
+    G = grid_graph(dim)
+    return G
+
+
+def triangular_lattice_graph(m, n, periodic=False, with_positions=True,
+                             create_using=None):
+    r"""Returns the $m$ by $n$ triangular lattice graph.
+
+    The `triangular lattice graph`_ is a two-dimensional `grid graph`_ in
+    which each square unit has a diagonal edge (each grid unit has a chord).
+
+    The returned graph has $m$ rows and $n$ columns of triangles. Rows and
+    columns include both triangles pointing up and down. Rows form a strip
+    of constant height. Columns form a series of diamond shapes, staggered
+    with the columns on either side. Another way to state the size is that
+    the nodes form a grid of `m+1` rows and `(n + 1) // 2` columns.
+    The odd row nodes are shifted horizontally relative to the even rows.
+
+    Directed graph types have edges pointed up or right.
+
+    Positions of nodes are computed by default or `with_positions is True`.
+    The position of each node (embedded in a euclidean plane) is stored in
+    the graph using equilateral triangles with sidelength 1.
+    The height between rows of nodes is thus $\sqrt(3)/2$.
+    Nodes lie in the first quadrant with the node $(0, 0)$ at the origin.
+
+    .. _triangular lattice graph: http://mathworld.wolfram.com/TriangularGrid.html
+    .. _grid graph: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
+    .. _Triangular Tiling: https://en.wikipedia.org/wiki/Triangular_tiling
+
+    Parameters
+    ----------
+    m : int
+        The number of rows in the lattice.
+
+    n : int
+        The number of columns in the lattice.
+
+    periodic : bool (default: False)
+        If True, join the boundary vertices of the grid using periodic
+        boundary conditions. The join between boundaries is the final row
+        and column of triangles. This means there is one row and one column
+        fewer nodes for the periodic lattice. Periodic lattices require
+        `m >= 3`, `n >= 5` and are allowed but misaligned if `m` or `n` are odd
+
+    with_positions : bool (default: True)
+        Store the coordinates of each node in the graph node attribute 'pos'.
+        The coordinates provide a lattice with equilateral triangles.
+        Periodic positions shift the nodes vertically in a nonlinear way so
+        the edges don't overlap so much.
+
+    create_using : NetworkX graph constructor, optional (default=nx.Graph)
+        Graph type to create. If graph instance, then cleared before populated.
+
+    Returns
+    -------
+    NetworkX graph
+        The *m* by *n* triangular lattice graph.
+    """
+    H = empty_graph(0, create_using)
+    if n == 0 or m == 0:
+        return H
+    if periodic:
+        if n < 5 or m < 3:
+            msg = "m > 2 and n > 4 required for periodic. m={}, n={}"
+            raise NetworkXError(msg.format(m, n))
+
+    N = (n + 1) // 2  # number of nodes in row
+    rows = range(m + 1)
+    cols = range(N + 1)
+    # Make grid
+    H.add_edges_from(((i, j), (i + 1, j)) for j in rows for i in cols[:N])
+    H.add_edges_from(((i, j), (i, j + 1)) for j in rows[:m] for i in cols)
+    # add diagonals
+    H.add_edges_from(((i, j), (i + 1, j + 1))
+                     for j in rows[1:m:2] for i in cols[:N])
+    H.add_edges_from(((i + 1, j), (i, j + 1))
+                     for j in rows[:m:2] for i in cols[:N])
+    # identify boundary nodes if periodic
+    if periodic is True:
+        for i in cols:
+            H = contracted_nodes(H, (i, 0), (i, m))
+        for j in rows[:m]:
+            H = contracted_nodes(H, (0, j), (N, j))
+    elif n % 2:
+        # remove extra nodes
+        H.remove_nodes_from(((N, j) for j in rows[1::2]))
+
+    # Add position node attributes
+    if with_positions:
+        ii = (i for i in cols for j in rows)
+        jj = (j for i in cols for j in rows)
+        xx = (0.5 * (j % 2) + i for i in cols for j in rows)
+        h = sqrt(3) / 2
+        if periodic:
+            yy = (h * j + .01 * i * i for i in cols for j in rows)
+        else:
+            yy = (h * j for i in cols for j in rows)
+        pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy)
+               if (i, j) in H}
+        set_node_attributes(H, pos, 'pos')
+    return H
+
+
+def hexagonal_lattice_graph(m, n, periodic=False, with_positions=True,
+                            create_using=None):
+    """Returns an `m` by `n` hexagonal lattice graph.
+
+    The *hexagonal lattice graph* is a graph whose nodes and edges are
+    the `hexagonal tiling`_ of the plane.
+
+    The returned graph will have `m` rows and `n` columns of hexagons.
+    `Odd numbered columns`_ are shifted up relative to even numbered columns.
+
+    Positions of nodes are computed by default or `with_positions is True`.
+    Node positions creating the standard embedding in the plane
+    with sidelength 1 and are stored in the node attribute 'pos'.
+    `pos = nx.get_node_attributes(G, 'pos')` creates a dict ready for drawing.
+
+    .. _hexagonal tiling: https://en.wikipedia.org/wiki/Hexagonal_tiling
+    .. _Odd numbered columns: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
+
+    Parameters
+    ----------
+    m : int
+        The number of rows of hexagons in the lattice.
+
+    n : int
+        The number of columns of hexagons in the lattice.
+
+    periodic : bool
+        Whether to make a periodic grid by joining the boundary vertices.
+        For this to work `n` must be odd and both `n > 1` and `m > 1`.
+        The periodic connections create another row and column of hexagons
+        so these graphs have fewer nodes as boundary nodes are identified.
+
+    with_positions : bool (default: True)
+        Store the coordinates of each node in the graph node attribute 'pos'.
+        The coordinates provide a lattice with vertical columns of hexagons
+        offset to interleave and cover the plane.
+        Periodic positions shift the nodes vertically in a nonlinear way so
+        the edges don't overlap so much.
+
+    create_using : NetworkX graph constructor, optional (default=nx.Graph)
+        Graph type to create. If graph instance, then cleared before populated.
+        If graph is directed, edges will point up or right.
+
+    Returns
+    -------
+    NetworkX graph
+        The *m* by *n* hexagonal lattice graph.
+    """
+    G = empty_graph(0, create_using)
+    if m == 0 or n == 0:
+        return G
+    if periodic and (n % 2 == 1 or m < 2 or n < 2):
+        msg = "periodic hexagonal lattice needs m > 1, n > 1 and even n"
+        raise NetworkXError(msg)
+
+    M = 2 * m    # twice as many nodes as hexagons vertically
+    rows = range(M + 2)
+    cols = range(n + 1)
+    # make lattice
+    col_edges = (((i, j), (i, j + 1)) for i in cols for j in rows[:M + 1])
+    row_edges = (((i, j), (i + 1, j)) for i in cols[:n] for j in rows
+                 if i % 2 == j % 2)
+    G.add_edges_from(col_edges)
+    G.add_edges_from(row_edges)
+    # Remove corner nodes with one edge
+    G.remove_node((0, M + 1))
+    G.remove_node((n, (M + 1) * (n % 2)))
+
+    # identify boundary nodes if periodic
+    if periodic:
+        for i in cols[:n]:
+            G = contracted_nodes(G, (i, 0), (i, M))
+        for i in cols[1:]:
+            G = contracted_nodes(G, (i, 1), (i, M + 1))
+        for j in rows[1:M]:
+            G = contracted_nodes(G, (0, j), (n, j))
+        G.remove_node((n, M))
+
+    # calc position in embedded space
+    ii = (i for i in cols for j in rows)
+    jj = (j for i in cols for j in rows)
+    xx = (0.5 + i + i // 2 + (j % 2) * ((i % 2) - .5)
+          for i in cols for j in rows)
+    h = sqrt(3) / 2
+    if periodic:
+        yy = (h * j + .01 * i * i for i in cols for j in rows)
+    else:
+        yy = (h * j for i in cols for j in rows)
+    # exclude nodes not in G
+    pos = {(i, j): (x, y) for i, j, x, y in zip(ii, jj, xx, yy) if (i, j) in G}
+    set_node_attributes(G, pos, 'pos')
+    return G