text: #    Copyright (C) 2004-2017 by
  #    Aric Hagberg <hagberg@lanl.gov>
  #    Dan Schult <dschult@colgate.edu>
  #    Pieter Swart <swart@lanl.gov>
  #    Richard Penney <rwpenney@users.sourceforge.net>
  #    All rights reserved.
  #    BSD license.
  #
  # Authors: Aric Hagberg <aric.hagberg@gmail.com>,
  #          Dan Schult <dschult@colgate.edu>
  """
  ******
  Layout
  ******
  
  Node positioning algorithms for graph drawing.
  
  For `random_layout()` the possible resulting shape
  is a square of side [0, scale] (default: [0, 1])
  Changing `center` shifts the layout by that amount.
  
  For the other layout routines, the extent is
  [center - scale, center + scale] (default: [-1, 1]).
  
  Warning: Most layout routines have only been tested in 2-dimensions.
  
  """
  from __future__ import division
  import collections
  import networkx as nx
  
  __all__ = ['circular_layout',
             'kamada_kawai_layout',
             'random_layout',
             'rescale_layout',
             'shell_layout',
             'spring_layout',
             'spectral_layout',
             'fruchterman_reingold_layout']
  
  
  def _process_params(G, center, dim):
      # Some boilerplate code.
      import numpy as np
  
      if not isinstance(G, nx.Graph):
          empty_graph = nx.Graph()
          empty_graph.add_nodes_from(G)
          G = empty_graph
  
      if center is None:
          center = np.zeros(dim)
      else:
          center = np.asarray(center)
  
      if len(center) != dim:
          msg = "length of center coordinates must match dimension of layout"
          raise ValueError(msg)
  
      return G, center
  
  
  def random_layout(G, center=None, dim=2):
      """Position nodes uniformly at random in the unit square.
  
      For every node, a position is generated by choosing each of dim
      coordinates uniformly at random on the interval [0.0, 1.0).
  
      NumPy (http://scipy.org) is required for this function.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
  
      dim : int
          Dimension of layout.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.lollipop_graph(4, 3)
      >>> pos = nx.random_layout(G)
  
      """
      import numpy as np
  
      G, center = _process_params(G, center, dim)
      shape = (len(G), dim)
      pos = np.random.random(shape) + center
      pos = pos.astype(np.float32)
      pos = dict(zip(G, pos))
  
      return pos
  
  
  def circular_layout(G, scale=1, center=None, dim=2):
      # dim=2 only
      """Position nodes on a circle.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      scale : number (default: 1)
          Scale factor for positions.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
  
      dim : int
          Dimension of layout.
          If dim>2, the remaining dimensions are set to zero
          in the returned positions.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.path_graph(4)
      >>> pos = nx.circular_layout(G)
  
      Notes
      -----
      This algorithm currently only works in two dimensions and does not
      try to minimize edge crossings.
  
      """
      import numpy as np
  
      G, center = _process_params(G, center, dim)
  
      paddims = max(0, (dim - 2))
  
      if len(G) == 0:
          pos = {}
      elif len(G) == 1:
          pos = {nx.utils.arbitrary_element(G): center}
      else:
          # Discard the extra angle since it matches 0 radians.
          theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
          theta = theta.astype(np.float32)
          pos = np.column_stack([np.cos(theta), np.sin(theta),
                                 np.zeros((len(G), paddims))])
          pos = rescale_layout(pos, scale=scale) + center
          pos = dict(zip(G, pos))
  
      return pos
  
  
  def shell_layout(G, nlist=None, scale=1, center=None, dim=2):
      """Position nodes in concentric circles.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      nlist : list of lists
         List of node lists for each shell.
  
      scale : number (default: 1)
          Scale factor for positions.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
  
      dim : int
          Dimension of layout, currently only dim=2 is supported.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.path_graph(4)
      >>> shells = [[0], [1, 2, 3]]
      >>> pos = nx.shell_layout(G, shells)
  
      Notes
      -----
      This algorithm currently only works in two dimensions and does not
      try to minimize edge crossings.
  
      """
      import numpy as np
  
      G, center = _process_params(G, center, dim)
  
      if len(G) == 0:
          return {}
      if len(G) == 1:
          return {nx.utils.arbitrary_element(G): center}
  
      if nlist is None:
          # draw the whole graph in one shell
          nlist = [list(G)]
  
      if len(nlist[0]) == 1:
          # single node at center
          radius = 0.0
      else:
          # else start at r=1
          radius = 1.0
  
      npos = {}
      for nodes in nlist:
          # Discard the extra angle since it matches 0 radians.
          theta = np.linspace(0, 1, len(nodes) + 1)[:-1] * 2 * np.pi
          theta = theta.astype(np.float32)
          pos = np.column_stack([np.cos(theta), np.sin(theta)])
          pos = rescale_layout(pos, scale=scale * radius / len(nlist)) + center
          npos.update(zip(nodes, pos))
          radius += 1.0
  
      return npos
  
  
  def fruchterman_reingold_layout(G, k=None,
                                  pos=None,
                                  fixed=None,
                                  iterations=50,
                                  weight='weight',
                                  scale=1,
                                  center=None,
                                  dim=2):
      """Position nodes using Fruchterman-Reingold force-directed algorithm.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      k : float (default=None)
          Optimal distance between nodes.  If None the distance is set to
          1/sqrt(n) where n is the number of nodes.  Increase this value
          to move nodes farther apart.
  
      pos : dict or None  optional (default=None)
          Initial positions for nodes as a dictionary with node as keys
          and values as a coordinate list or tuple.  If None, then use
          random initial positions.
  
      fixed : list or None  optional (default=None)
          Nodes to keep fixed at initial position.
  
      iterations : int  optional (default=50)
          Number of iterations of spring-force relaxation
  
      weight : string or None   optional (default='weight')
          The edge attribute that holds the numerical value used for
          the edge weight.  If None, then all edge weights are 1.
  
      scale : number (default: 1)
          Scale factor for positions. Not used unless `fixed is None`.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
          Not used unless `fixed is None`.
  
      dim : int
          Dimension of layout.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.path_graph(4)
      >>> pos = nx.spring_layout(G)
  
      # The same using longer but equivalent function name
      >>> pos = nx.fruchterman_reingold_layout(G)
      """
      import numpy as np
  
      G, center = _process_params(G, center, dim)
  
      if fixed is not None:
          nfixed = dict(zip(G, range(len(G))))
          fixed = np.asarray([nfixed[v] for v in fixed])
  
      if pos is not None:
          # Determine size of existing domain to adjust initial positions
          dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
          if dom_size == 0:
              dom_size = 1
          shape = (len(G), dim)
          pos_arr = np.random.random(shape) * dom_size + center
          for i, n in enumerate(G):
              if n in pos:
                  pos_arr[i] = np.asarray(pos[n])
      else:
          pos_arr = None
  
      if len(G) == 0:
          return {}
      if len(G) == 1:
          return {nx.utils.arbitrary_element(G.nodes()): center}
  
      try:
          # Sparse matrix
          if len(G) < 500:  # sparse solver for large graphs
              raise ValueError
          A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='f')
          if k is None and fixed is not None:
              # We must adjust k by domain size for layouts not near 1x1
              nnodes, _ = A.shape
              k = dom_size / np.sqrt(nnodes)
          pos = _sparse_fruchterman_reingold(A, k, pos_arr, fixed,
                                             iterations, dim)
      except:
          A = nx.to_numpy_matrix(G, weight=weight)
          if k is None and fixed is not None:
              # We must adjust k by domain size for layouts not near 1x1
              nnodes, _ = A.shape
              k = dom_size / np.sqrt(nnodes)
          pos = _fruchterman_reingold(A, k, pos_arr, fixed, iterations, dim)
      if fixed is None:
          pos = rescale_layout(pos, scale=scale) + center
      pos = dict(zip(G, pos))
      return pos
  
  
  spring_layout = fruchterman_reingold_layout
  
  
  def _fruchterman_reingold(A, k=None, pos=None, fixed=None,
                            iterations=50, dim=2):
      # Position nodes in adjacency matrix A using Fruchterman-Reingold
      # Entry point for NetworkX graph is fruchterman_reingold_layout()
      try:
          import numpy as np
      except ImportError:
          msg = "_fruchterman_reingold() requires numpy: http://scipy.org/ "
          raise ImportError(msg)
  
      try:
          nnodes, _ = A.shape
      except AttributeError:
          msg = "fruchterman_reingold() takes an adjacency matrix as input"
          raise nx.NetworkXError(msg)
  
      # make sure we have an array instead of a matrix
      A = np.asarray(A)
  
      if pos is None:
          # random initial positions
          pos = np.asarray(np.random.random((nnodes, dim)), dtype=A.dtype)
      else:
          # make sure positions are of same type as matrix
          pos = pos.astype(A.dtype)
  
      # optimal distance between nodes
      if k is None:
          k = np.sqrt(1.0/nnodes)
      # the initial "temperature"  is about .1 of domain area (=1x1)
      # this is the largest step allowed in the dynamics.
      # We need to calculate this in case our fixed positions force our domain
      # to be much bigger than 1x1
      t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1]))*0.1
      # simple cooling scheme.
      # linearly step down by dt on each iteration so last iteration is size dt.
      dt = t/float(iterations+1)
      delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)
      # the inscrutable (but fast) version
      # this is still O(V^2)
      # could use multilevel methods to speed this up significantly
      for iteration in range(iterations):
          # matrix of difference between points
          delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]
          # distance between points
          distance = np.linalg.norm(delta, axis=-1)
          # enforce minimum distance of 0.01
          np.clip(distance, 0.01, None, out=distance)
          # displacement "force"
          displacement = np.einsum('ijk,ij->ik',
                                   delta,
                                   (k * k / distance**2 - A * distance / k))
          # update positions
          length = np.linalg.norm(displacement, axis=-1)
          length = np.where(length < 0.01, 0.1, length)
          delta_pos = np.einsum('ij,i->ij', displacement, t / length)
          if fixed is not None:
              # don't change positions of fixed nodes
              delta_pos[fixed] = 0.0
          pos += delta_pos
          # cool temperature
          t -= dt
      return pos
  
  
  def _sparse_fruchterman_reingold(A, k=None, pos=None, fixed=None,
                                   iterations=50, dim=2):
      # Position nodes in adjacency matrix A using Fruchterman-Reingold
      # Entry point for NetworkX graph is fruchterman_reingold_layout()
      # Sparse version
      try:
          import numpy as np
      except ImportError:
          m = "_sparse_fruchterman_reingold() requires numpy: http://scipy.org/"
          raise ImportError(m)
      try:
          nnodes, _ = A.shape
      except AttributeError:
          msg = "fruchterman_reingold() takes an adjacency matrix as input"
          raise nx.NetworkXError(msg)
      try:
          from scipy.sparse import spdiags, coo_matrix
      except ImportError:
          msg = "_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ "
          raise ImportError(msg)
      # make sure we have a LIst of Lists representation
      try:
          A = A.tolil()
      except:
          A = (coo_matrix(A)).tolil()
  
      if pos is None:
          # random initial positions
          pos = np.asarray(np.random.random((nnodes, dim)), dtype=A.dtype)
      else:
          # make sure positions are of same type as matrix
          pos = pos.astype(A.dtype)
  
      # no fixed nodes
      if fixed is None:
          fixed = []
  
      # optimal distance between nodes
      if k is None:
          k = np.sqrt(1.0/nnodes)
      # the initial "temperature"  is about .1 of domain area (=1x1)
      # this is the largest step allowed in the dynamics.
      t = 0.1
      # simple cooling scheme.
      # linearly step down by dt on each iteration so last iteration is size dt.
      dt = t / float(iterations+1)
  
      displacement = np.zeros((dim, nnodes))
      for iteration in range(iterations):
          displacement *= 0
          # loop over rows
          for i in range(A.shape[0]):
              if i in fixed:
                  continue
              # difference between this row's node position and all others
              delta = (pos[i] - pos).T
              # distance between points
              distance = np.sqrt((delta**2).sum(axis=0))
              # enforce minimum distance of 0.01
              distance = np.where(distance < 0.01, 0.01, distance)
              # the adjacency matrix row
              Ai = np.asarray(A.getrowview(i).toarray())
              # displacement "force"
              displacement[:, i] +=\
                  (delta * (k * k / distance**2 - Ai * distance / k)).sum(axis=1)
          # update positions
          length = np.sqrt((displacement**2).sum(axis=0))
          length = np.where(length < 0.01, 0.1, length)
          pos += (displacement * t / length).T
          # cool temperature
          t -= dt
      return pos
  
  
  def kamada_kawai_layout(G, dist=None,
                          pos=None,
                          weight='weight',
                          scale=1,
                          center=None,
                          dim=2):
      """Position nodes using Kamada-Kawai path-length cost-function.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      dist : float (default=None)
          A two-level dictionary of optimal distances between nodes,
          indexed by source and destination node.
          If None, the distance is computed using shortest_path_length().
  
      pos : dict or None  optional (default=None)
          Initial positions for nodes as a dictionary with node as keys
          and values as a coordinate list or tuple.  If None, then use
          circular_layout().
  
      weight : string or None   optional (default='weight')
          The edge attribute that holds the numerical value used for
          the edge weight.  If None, then all edge weights are 1.
  
      scale : number (default: 1)
          Scale factor for positions.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
  
      dim : int
          Dimension of layout.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.path_graph(4)
      >>> pos = nx.kamada_kawai_layout(G)
      """
      try:
          import numpy as np
      except ImportError:
          msg = 'Kamada-Kawai layout requires numpy: http://scipy.org'
          raise ImportError(msg)
  
      G, center = _process_params(G, center, dim)
      nNodes = len(G)
  
      if dist is None:
          dist = dict(nx.shortest_path_length(G, weight=weight))
      dist_mtx = 1e6 * np.ones((nNodes, nNodes))
      for row, nr in enumerate(G):
          if nr not in dist:
              continue
          rdist = dist[nr]
          for col, nc in enumerate(G):
              if nc not in rdist:
                  continue
              dist_mtx[row][col] = rdist[nc]
  
      if pos is None:
          pos = circular_layout(G, dim=dim)
      pos_arr = np.array([pos[n] for n in G])
  
      pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)
  
      pos = rescale_layout(pos, scale=scale) + center
      return dict(zip(G, pos))
  
  
  def _kamada_kawai_solve(dist_mtx, pos_arr, dim):
      # Anneal node locations based on the Kamada-Kawai cost-function,
      # using the supplied matrix of preferred inter-node distances,
      # and starting locations.
  
      import numpy as np
      try:
          from scipy.optimize import minimize
      except ImportError:
          msg = 'Kamada-Kawai layout requires scipy: http://scipy.org'
          raise ImportError(msg)
  
      meanwt = 1e-3
      costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3),
                  meanwt, dim)
  
      optresult = minimize(_kamada_kawai_costfn, pos_arr.ravel(),
                           method='L-BFGS-B', args=costargs, jac=True)
  
      return optresult.x.reshape((-1, dim))
  
  
  def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):
      # Cost-function and gradient for Kamada-Kawai layout algorithm
      nNodes = invdist.shape[0]
      pos_arr = pos_vec.reshape((nNodes, dim))
  
      delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]
      nodesep = np.linalg.norm(delta, axis=-1)
      direction = np.einsum('ijk,ij->ijk',
                            delta,
                            1 / (nodesep + np.eye(nNodes) * 1e-3))
  
      offset = nodesep * invdist - 1.0
      offset[np.diag_indices(nNodes)] = 0
  
      cost = 0.5 * np.sum(offset ** 2)
      grad = (np.einsum('ij,ij,ijk->ik', invdist, offset, direction) -
              np.einsum('ij,ij,ijk->jk', invdist, offset, direction))
  
      # Additional parabolic term to encourage mean position to be near origin:
      sumpos = np.sum(pos_arr, axis=0)
      cost += 0.5 * meanweight * np.sum(sumpos ** 2)
      grad += meanweight * sumpos
  
      return (cost, grad.ravel())
  
  
  def spectral_layout(G, weight='weight', scale=1, center=None, dim=2):
      """Position nodes using the eigenvectors of the graph Laplacian.
  
      Parameters
      ----------
      G : NetworkX graph or list of nodes
          A position will be assigned to every node in G.
  
      weight : string or None   optional (default='weight')
          The edge attribute that holds the numerical value used for
          the edge weight.  If None, then all edge weights are 1.
  
      scale : number (default: 1)
          Scale factor for positions.
  
      center : array-like or None
          Coordinate pair around which to center the layout.
  
      dim : int
          Dimension of layout.
  
      Returns
      -------
      pos : dict
          A dictionary of positions keyed by node
  
      Examples
      --------
      >>> G = nx.path_graph(4)
      >>> pos = nx.spectral_layout(G)
  
      Notes
      -----
      Directed graphs will be considered as undirected graphs when
      positioning the nodes.
  
      For larger graphs (>500 nodes) this will use the SciPy sparse
      eigenvalue solver (ARPACK).
      """
      # handle some special cases that break the eigensolvers
      import numpy as np
  
      G, center = _process_params(G, center, dim)
  
      if len(G) <= 2:
          if len(G) == 0:
              pos = np.array([])
          elif len(G) == 1:
              pos = np.array([center])
          else:
              pos = np.array([np.zeros(dim), np.array(center)*2.0])
          return dict(zip(G, pos))
      try:
          # Sparse matrix
          if len(G) < 500:  # dense solver is faster for small graphs
              raise ValueError
          A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='d')
          # Symmetrize directed graphs
          if G.is_directed():
              A = A + np.transpose(A)
          pos = _sparse_spectral(A, dim)
      except (ImportError, ValueError):
          # Dense matrix
          A = nx.to_numpy_matrix(G, weight=weight)
          # Symmetrize directed graphs
          if G.is_directed():
              A = A + np.transpose(A)
          pos = _spectral(A, dim)
  
      pos = rescale_layout(pos, scale) + center
      pos = dict(zip(G, pos))
      return pos
  
  
  def _spectral(A, dim=2):
      # Input adjacency matrix A
      # Uses dense eigenvalue solver from numpy
      try:
          import numpy as np
      except ImportError:
          msg = "spectral_layout() requires numpy: http://scipy.org/ "
          raise ImportError(msg)
      try:
          nnodes, _ = A.shape
      except AttributeError:
          msg = "spectral() takes an adjacency matrix as input"
          raise nx.NetworkXError(msg)
  
      # form Laplacian matrix
      # make sure we have an array instead of a matrix
      A = np.asarray(A)
      I = np.identity(nnodes, dtype=A.dtype)
      D = I * np.sum(A, axis=1)  # diagonal of degrees
      L = D - A
  
      eigenvalues, eigenvectors = np.linalg.eig(L)
      # sort and keep smallest nonzero
      index = np.argsort(eigenvalues)[1:dim + 1]  # 0 index is zero eigenvalue
      return np.real(eigenvectors[:, index])
  
  
  def _sparse_spectral(A, dim=2):
      # Input adjacency matrix A
      # Uses sparse eigenvalue solver from scipy
      # Could use multilevel methods here, see Koren "On spectral graph drawing"
      try:
          import numpy as np
          from scipy.sparse import spdiags
          from scipy.sparse.linalg.eigen import eigsh
      except ImportError:
          msg = "_sparse_spectral() requires scipy & numpy: http://scipy.org/ "
          raise ImportError(msg)
      try:
          nnodes, _ = A.shape
      except AttributeError:
          msg = "sparse_spectral() takes an adjacency matrix as input"
          raise nx.NetworkXError(msg)
  
      # form Laplacian matrix
      data = np.asarray(A.sum(axis=1).T)
      D = spdiags(data, 0, nnodes, nnodes)
      L = D - A
  
      k = dim + 1
      # number of Lanczos vectors for ARPACK solver.What is the right scaling?
      ncv = max(2 * k + 1, int(np.sqrt(nnodes)))
      # return smallest k eigenvalues and eigenvectors
      eigenvalues, eigenvectors = eigsh(L, k, which='SM', ncv=ncv)
      index = np.argsort(eigenvalues)[1:k]  # 0 index is zero eigenvalue
      return np.real(eigenvectors[:, index])
  
  
  def rescale_layout(pos, scale=1):
      """Return scaled position array to (-scale, scale) in all axes.
  
      The function acts on NumPy arrays which hold position information.
      Each position is one row of the array. The dimension of the space
      equals the number of columns. Each coordinate in one column.
  
      To rescale, the mean (center) is subtracted from each axis separately.
      Then all values are scaled so that the largest magnitude value
      from all axes equals `scale` (thus, the aspect ratio is preserved).
      The resulting NumPy Array is returned (order of rows unchanged).
  
      Parameters
      ----------
      pos : numpy array
          positions to be scaled. Each row is a position.
  
      scale : number (default: 1)
          The size of the resulting extent in all directions.
  
      Returns
      -------
      pos : numpy array
          scaled positions. Each row is a position.
  
      """
      # Find max length over all dimensions
      lim = 0  # max coordinate for all axes
      for i in range(pos.shape[1]):
          pos[:, i] -= pos[:, i].mean()
          lim = max(abs(pos[:, i]).max(), lim)
      # rescale to (-scale, scale) in all directions, preserves aspect
      if lim > 0:
          for i in range(pos.shape[1]):
              pos[:, i] *= scale / lim
      return pos
  
  
  # fixture for nose tests
  def setup_module(module):
      from nose import SkipTest
      try:
          import numpy
      except:
          raise SkipTest("NumPy not available")
      try:
          import scipy
      except:
          raise SkipTest("SciPy not available")
  