Advertisement
Guest User

layout.py

a guest
Jan 13th, 2018
512
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 24.43 KB | None | 0 0
  1. #    Copyright (C) 2004-2017 by
  2. #    Aric Hagberg <hagberg@lanl.gov>
  3. #    Dan Schult <dschult@colgate.edu>
  4. #    Pieter Swart <swart@lanl.gov>
  5. #    Richard Penney <rwpenney@users.sourceforge.net>
  6. #    All rights reserved.
  7. #    BSD license.
  8. #
  9. # Authors: Aric Hagberg <aric.hagberg@gmail.com>,
  10. #          Dan Schult <dschult@colgate.edu>
  11. """
  12. ******
  13. Layout
  14. ******
  15.  
  16. Node positioning algorithms for graph drawing.
  17.  
  18. For `random_layout()` the possible resulting shape
  19. is a square of side [0, scale] (default: [0, 1])
  20. Changing `center` shifts the layout by that amount.
  21.  
  22. For the other layout routines, the extent is
  23. [center - scale, center + scale] (default: [-1, 1]).
  24.  
  25. Warning: Most layout routines have only been tested in 2-dimensions.
  26.  
  27. """
  28. from __future__ import division
  29. import collections
  30. import networkx as nx
  31.  
  32. __all__ = ['circular_layout',
  33.            'kamada_kawai_layout',
  34.            'random_layout',
  35.            'rescale_layout',
  36.            'shell_layout',
  37.            'spring_layout',
  38.            'spectral_layout',
  39.            'fruchterman_reingold_layout']
  40.  
  41.  
  42. def _process_params(G, center, dim):
  43.     # Some boilerplate code.
  44.     import numpy as np
  45.  
  46.     if not isinstance(G, nx.Graph):
  47.         empty_graph = nx.Graph()
  48.         empty_graph.add_nodes_from(G)
  49.         G = empty_graph
  50.  
  51.     if center is None:
  52.         center = np.zeros(dim)
  53.     else:
  54.         center = np.asarray(center)
  55.  
  56.     if len(center) != dim:
  57.         msg = "length of center coordinates must match dimension of layout"
  58.         raise ValueError(msg)
  59.  
  60.     return G, center
  61.  
  62.  
  63. def random_layout(G, center=None, dim=2):
  64.     """Position nodes uniformly at random in the unit square.
  65.  
  66.    For every node, a position is generated by choosing each of dim
  67.    coordinates uniformly at random on the interval [0.0, 1.0).
  68.  
  69.    NumPy (http://scipy.org) is required for this function.
  70.  
  71.    Parameters
  72.    ----------
  73.    G : NetworkX graph or list of nodes
  74.        A position will be assigned to every node in G.
  75.  
  76.    center : array-like or None
  77.        Coordinate pair around which to center the layout.
  78.  
  79.    dim : int
  80.        Dimension of layout.
  81.  
  82.    Returns
  83.    -------
  84.    pos : dict
  85.        A dictionary of positions keyed by node
  86.  
  87.    Examples
  88.    --------
  89.    >>> G = nx.lollipop_graph(4, 3)
  90.    >>> pos = nx.random_layout(G)
  91.  
  92.    """
  93.     import numpy as np
  94.  
  95.     G, center = _process_params(G, center, dim)
  96.     shape = (len(G), dim)
  97.     pos = np.random.random(shape) + center
  98.     pos = pos.astype(np.float32)
  99.     pos = dict(zip(G, pos))
  100.  
  101.     return pos
  102.  
  103.  
  104. def circular_layout(G, scale=1, center=None, dim=2):
  105.     # dim=2 only
  106.     """Position nodes on a circle.
  107.  
  108.    Parameters
  109.    ----------
  110.    G : NetworkX graph or list of nodes
  111.        A position will be assigned to every node in G.
  112.  
  113.    scale : number (default: 1)
  114.        Scale factor for positions.
  115.  
  116.    center : array-like or None
  117.        Coordinate pair around which to center the layout.
  118.  
  119.    dim : int
  120.        Dimension of layout.
  121.        If dim>2, the remaining dimensions are set to zero
  122.        in the returned positions.
  123.  
  124.    Returns
  125.    -------
  126.    pos : dict
  127.        A dictionary of positions keyed by node
  128.  
  129.    Examples
  130.    --------
  131.    >>> G = nx.path_graph(4)
  132.    >>> pos = nx.circular_layout(G)
  133.  
  134.    Notes
  135.    -----
  136.    This algorithm currently only works in two dimensions and does not
  137.    try to minimize edge crossings.
  138.  
  139.    """
  140.     import numpy as np
  141.  
  142.     G, center = _process_params(G, center, dim)
  143.  
  144.     paddims = max(0, (dim - 2))
  145.  
  146.     if len(G) == 0:
  147.         pos = {}
  148.     elif len(G) == 1:
  149.         pos = {nx.utils.arbitrary_element(G): center}
  150.     else:
  151.         # Discard the extra angle since it matches 0 radians.
  152.         theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
  153.         theta = theta.astype(np.float32)
  154.         pos = np.column_stack([np.cos(theta), np.sin(theta),
  155.                                np.zeros((len(G), paddims))])
  156.         pos = rescale_layout(pos, scale=scale) + center
  157.         pos = dict(zip(G, pos))
  158.  
  159.     return pos
  160.  
  161.  
  162. def shell_layout(G, nlist=None, scale=1, center=None, dim=2):
  163.     """Position nodes in concentric circles.
  164.  
  165.    Parameters
  166.    ----------
  167.    G : NetworkX graph or list of nodes
  168.        A position will be assigned to every node in G.
  169.  
  170.    nlist : list of lists
  171.       List of node lists for each shell.
  172.  
  173.    scale : number (default: 1)
  174.        Scale factor for positions.
  175.  
  176.    center : array-like or None
  177.        Coordinate pair around which to center the layout.
  178.  
  179.    dim : int
  180.        Dimension of layout, currently only dim=2 is supported.
  181.  
  182.    Returns
  183.    -------
  184.    pos : dict
  185.        A dictionary of positions keyed by node
  186.  
  187.    Examples
  188.    --------
  189.    >>> G = nx.path_graph(4)
  190.    >>> shells = [[0], [1, 2, 3]]
  191.    >>> pos = nx.shell_layout(G, shells)
  192.  
  193.    Notes
  194.    -----
  195.    This algorithm currently only works in two dimensions and does not
  196.    try to minimize edge crossings.
  197.  
  198.    """
  199.     import numpy as np
  200.  
  201.     G, center = _process_params(G, center, dim)
  202.  
  203.     if len(G) == 0:
  204.         return {}
  205.     if len(G) == 1:
  206.         return {nx.utils.arbitrary_element(G): center}
  207.  
  208.     if nlist is None:
  209.         # draw the whole graph in one shell
  210.         nlist = [list(G)]
  211.  
  212.     if len(nlist[0]) == 1:
  213.         # single node at center
  214.         radius = 0.0
  215.     else:
  216.         # else start at r=1
  217.         radius = 1.0
  218.  
  219.     npos = {}
  220.     for nodes in nlist:
  221.         # Discard the extra angle since it matches 0 radians.
  222.         theta = np.linspace(0, 1, len(nodes) + 1)[:-1] * 2 * np.pi
  223.         theta = theta.astype(np.float32)
  224.         pos = np.column_stack([np.cos(theta), np.sin(theta)])
  225.         pos = rescale_layout(pos, scale=scale * radius / len(nlist)) + center
  226.         npos.update(zip(nodes, pos))
  227.         radius += 1.0
  228.  
  229.     return npos
  230.  
  231.  
  232. def fruchterman_reingold_layout(G, k=None,
  233.                                 pos=None,
  234.                                 fixed=None,
  235.                                 iterations=50,
  236.                                 weight='weight',
  237.                                 scale=1,
  238.                                 center=None,
  239.                                 dim=2):
  240.     """Position nodes using Fruchterman-Reingold force-directed algorithm.
  241.  
  242.    Parameters
  243.    ----------
  244.    G : NetworkX graph or list of nodes
  245.        A position will be assigned to every node in G.
  246.  
  247.    k : float (default=None)
  248.        Optimal distance between nodes.  If None the distance is set to
  249.        1/sqrt(n) where n is the number of nodes.  Increase this value
  250.        to move nodes farther apart.
  251.  
  252.    pos : dict or None  optional (default=None)
  253.        Initial positions for nodes as a dictionary with node as keys
  254.        and values as a coordinate list or tuple.  If None, then use
  255.        random initial positions.
  256.  
  257.    fixed : list or None  optional (default=None)
  258.        Nodes to keep fixed at initial position.
  259.  
  260.    iterations : int  optional (default=50)
  261.        Number of iterations of spring-force relaxation
  262.  
  263.    weight : string or None   optional (default='weight')
  264.        The edge attribute that holds the numerical value used for
  265.        the edge weight.  If None, then all edge weights are 1.
  266.  
  267.    scale : number (default: 1)
  268.        Scale factor for positions. Not used unless `fixed is None`.
  269.  
  270.    center : array-like or None
  271.        Coordinate pair around which to center the layout.
  272.        Not used unless `fixed is None`.
  273.  
  274.    dim : int
  275.        Dimension of layout.
  276.  
  277.    Returns
  278.    -------
  279.    pos : dict
  280.        A dictionary of positions keyed by node
  281.  
  282.    Examples
  283.    --------
  284.    >>> G = nx.path_graph(4)
  285.    >>> pos = nx.spring_layout(G)
  286.  
  287.    # The same using longer but equivalent function name
  288.    >>> pos = nx.fruchterman_reingold_layout(G)
  289.    """
  290.     import numpy as np
  291.  
  292.     G, center = _process_params(G, center, dim)
  293.  
  294.     if fixed is not None:
  295.         nfixed = dict(zip(G, range(len(G))))
  296.         fixed = np.asarray([nfixed[v] for v in fixed])
  297.  
  298.     if pos is not None:
  299.         # Determine size of existing domain to adjust initial positions
  300.         dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
  301.         if dom_size == 0:
  302.             dom_size = 1
  303.         shape = (len(G), dim)
  304.         pos_arr = np.random.random(shape) * dom_size + center
  305.         for i, n in enumerate(G):
  306.             if n in pos:
  307.                 pos_arr[i] = np.asarray(pos[n])
  308.     else:
  309.         pos_arr = None
  310.  
  311.     if len(G) == 0:
  312.         return {}
  313.     if len(G) == 1:
  314.         return {nx.utils.arbitrary_element(G.nodes()): center}
  315.  
  316.     try:
  317.         # Sparse matrix
  318.         if len(G) < 500:  # sparse solver for large graphs
  319.             raise ValueError
  320.         A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='f')
  321.         if k is None and fixed is not None:
  322.             # We must adjust k by domain size for layouts not near 1x1
  323.             nnodes, _ = A.shape
  324.             k = dom_size / np.sqrt(nnodes)
  325.         pos = _sparse_fruchterman_reingold(A, k, pos_arr, fixed,
  326.                                            iterations, dim)
  327.     except:
  328.         A = nx.to_numpy_matrix(G, weight=weight)
  329.         if k is None and fixed is not None:
  330.             # We must adjust k by domain size for layouts not near 1x1
  331.             nnodes, _ = A.shape
  332.             k = dom_size / np.sqrt(nnodes)
  333.         pos = _fruchterman_reingold(A, k, pos_arr, fixed, iterations, dim)
  334.     if fixed is None:
  335.         pos = rescale_layout(pos, scale=scale) + center
  336.     pos = dict(zip(G, pos))
  337.     return pos
  338.  
  339.  
  340. spring_layout = fruchterman_reingold_layout
  341.  
  342.  
  343. def _fruchterman_reingold(A, k=None, pos=None, fixed=None,
  344.                           iterations=50, dim=2):
  345.     # Position nodes in adjacency matrix A using Fruchterman-Reingold
  346.     # Entry point for NetworkX graph is fruchterman_reingold_layout()
  347.     try:
  348.         import numpy as np
  349.     except ImportError:
  350.         msg = "_fruchterman_reingold() requires numpy: http://scipy.org/ "
  351.         raise ImportError(msg)
  352.  
  353.     try:
  354.         nnodes, _ = A.shape
  355.     except AttributeError:
  356.         msg = "fruchterman_reingold() takes an adjacency matrix as input"
  357.         raise nx.NetworkXError(msg)
  358.  
  359.     # make sure we have an array instead of a matrix
  360.     A = np.asarray(A)
  361.  
  362.     if pos is None:
  363.         # random initial positions
  364.         pos = np.asarray(np.random.random((nnodes, dim)), dtype=A.dtype)
  365.     else:
  366.         # make sure positions are of same type as matrix
  367.         pos = pos.astype(A.dtype)
  368.  
  369.     # optimal distance between nodes
  370.     if k is None:
  371.         k = np.sqrt(1.0/nnodes)
  372.     # the initial "temperature"  is about .1 of domain area (=1x1)
  373.     # this is the largest step allowed in the dynamics.
  374.     # We need to calculate this in case our fixed positions force our domain
  375.     # to be much bigger than 1x1
  376.     t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1]))*0.1
  377.     # simple cooling scheme.
  378.     # linearly step down by dt on each iteration so last iteration is size dt.
  379.     dt = t/float(iterations+1)
  380.     delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)
  381.     # the inscrutable (but fast) version
  382.     # this is still O(V^2)
  383.     # could use multilevel methods to speed this up significantly
  384.     for iteration in range(iterations):
  385.         # matrix of difference between points
  386.         delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]
  387.         # distance between points
  388.         distance = np.linalg.norm(delta, axis=-1)
  389.         # enforce minimum distance of 0.01
  390.         np.clip(distance, 0.01, None, out=distance)
  391.         # displacement "force"
  392.         displacement = np.einsum('ijk,ij->ik',
  393.                                  delta,
  394.                                  (k * k / distance**2 - A * distance / k))
  395.         # update positions
  396.         length = np.linalg.norm(displacement, axis=-1)
  397.         length = np.where(length < 0.01, 0.1, length)
  398.         delta_pos = np.einsum('ij,i->ij', displacement, t / length)
  399.         if fixed is not None:
  400.             # don't change positions of fixed nodes
  401.             delta_pos[fixed] = 0.0
  402.         pos += delta_pos
  403.         # cool temperature
  404.         t -= dt
  405.     return pos
  406.  
  407.  
  408. def _sparse_fruchterman_reingold(A, k=None, pos=None, fixed=None,
  409.                                  iterations=50, dim=2):
  410.     # Position nodes in adjacency matrix A using Fruchterman-Reingold
  411.     # Entry point for NetworkX graph is fruchterman_reingold_layout()
  412.     # Sparse version
  413.     try:
  414.         import numpy as np
  415.     except ImportError:
  416.         m = "_sparse_fruchterman_reingold() requires numpy: http://scipy.org/"
  417.         raise ImportError(m)
  418.     try:
  419.         nnodes, _ = A.shape
  420.     except AttributeError:
  421.         msg = "fruchterman_reingold() takes an adjacency matrix as input"
  422.         raise nx.NetworkXError(msg)
  423.     try:
  424.         from scipy.sparse import spdiags, coo_matrix
  425.     except ImportError:
  426.         msg = "_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ "
  427.         raise ImportError(msg)
  428.     # make sure we have a LIst of Lists representation
  429.     try:
  430.         A = A.tolil()
  431.     except:
  432.         A = (coo_matrix(A)).tolil()
  433.  
  434.     if pos is None:
  435.         # random initial positions
  436.         pos = np.asarray(np.random.random((nnodes, dim)), dtype=A.dtype)
  437.     else:
  438.         # make sure positions are of same type as matrix
  439.         pos = pos.astype(A.dtype)
  440.  
  441.     # no fixed nodes
  442.     if fixed is None:
  443.         fixed = []
  444.  
  445.     # optimal distance between nodes
  446.     if k is None:
  447.         k = np.sqrt(1.0/nnodes)
  448.     # the initial "temperature"  is about .1 of domain area (=1x1)
  449.     # this is the largest step allowed in the dynamics.
  450.     t = 0.1
  451.     # simple cooling scheme.
  452.     # linearly step down by dt on each iteration so last iteration is size dt.
  453.     dt = t / float(iterations+1)
  454.  
  455.     displacement = np.zeros((dim, nnodes))
  456.     for iteration in range(iterations):
  457.         displacement *= 0
  458.         # loop over rows
  459.         for i in range(A.shape[0]):
  460.             if i in fixed:
  461.                 continue
  462.             # difference between this row's node position and all others
  463.             delta = (pos[i] - pos).T
  464.             # distance between points
  465.             distance = np.sqrt((delta**2).sum(axis=0))
  466.             # enforce minimum distance of 0.01
  467.             distance = np.where(distance < 0.01, 0.01, distance)
  468.             # the adjacency matrix row
  469.             Ai = np.asarray(A.getrowview(i).toarray())
  470.             # displacement "force"
  471.             displacement[:, i] +=\
  472.                 (delta * (k * k / distance**2 - Ai * distance / k)).sum(axis=1)
  473.         # update positions
  474.         length = np.sqrt((displacement**2).sum(axis=0))
  475.         length = np.where(length < 0.01, 0.1, length)
  476.         pos += (displacement * t / length).T
  477.         # cool temperature
  478.         t -= dt
  479.     return pos
  480.  
  481.  
  482. def kamada_kawai_layout(G, dist=None,
  483.                         pos=None,
  484.                         weight='weight',
  485.                         scale=1,
  486.                         center=None,
  487.                         dim=2):
  488.     """Position nodes using Kamada-Kawai path-length cost-function.
  489.  
  490.    Parameters
  491.    ----------
  492.    G : NetworkX graph or list of nodes
  493.        A position will be assigned to every node in G.
  494.  
  495.    dist : float (default=None)
  496.        A two-level dictionary of optimal distances between nodes,
  497.        indexed by source and destination node.
  498.        If None, the distance is computed using shortest_path_length().
  499.  
  500.    pos : dict or None  optional (default=None)
  501.        Initial positions for nodes as a dictionary with node as keys
  502.        and values as a coordinate list or tuple.  If None, then use
  503.        circular_layout().
  504.  
  505.    weight : string or None   optional (default='weight')
  506.        The edge attribute that holds the numerical value used for
  507.        the edge weight.  If None, then all edge weights are 1.
  508.  
  509.    scale : number (default: 1)
  510.        Scale factor for positions.
  511.  
  512.    center : array-like or None
  513.        Coordinate pair around which to center the layout.
  514.  
  515.    dim : int
  516.        Dimension of layout.
  517.  
  518.    Returns
  519.    -------
  520.    pos : dict
  521.        A dictionary of positions keyed by node
  522.  
  523.    Examples
  524.    --------
  525.    >>> G = nx.path_graph(4)
  526.    >>> pos = nx.kamada_kawai_layout(G)
  527.    """
  528.     try:
  529.         import numpy as np
  530.     except ImportError:
  531.         msg = 'Kamada-Kawai layout requires numpy: http://scipy.org'
  532.         raise ImportError(msg)
  533.  
  534.     G, center = _process_params(G, center, dim)
  535.     nNodes = len(G)
  536.  
  537.     if dist is None:
  538.         dist = dict(nx.shortest_path_length(G, weight=weight))
  539.     dist_mtx = 1e6 * np.ones((nNodes, nNodes))
  540.     for row, nr in enumerate(G):
  541.         if nr not in dist:
  542.             continue
  543.         rdist = dist[nr]
  544.         for col, nc in enumerate(G):
  545.             if nc not in rdist:
  546.                 continue
  547.             dist_mtx[row][col] = rdist[nc]
  548.  
  549.     if pos is None:
  550.         pos = circular_layout(G, dim=dim)
  551.     pos_arr = np.array([pos[n] for n in G])
  552.  
  553.     pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)
  554.  
  555.     pos = rescale_layout(pos, scale=scale) + center
  556.     return dict(zip(G, pos))
  557.  
  558.  
  559. def _kamada_kawai_solve(dist_mtx, pos_arr, dim):
  560.     # Anneal node locations based on the Kamada-Kawai cost-function,
  561.     # using the supplied matrix of preferred inter-node distances,
  562.     # and starting locations.
  563.  
  564.     import numpy as np
  565.     try:
  566.         from scipy.optimize import minimize
  567.     except ImportError:
  568.         msg = 'Kamada-Kawai layout requires scipy: http://scipy.org'
  569.         raise ImportError(msg)
  570.  
  571.     meanwt = 1e-3
  572.     costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3),
  573.                 meanwt, dim)
  574.  
  575.     optresult = minimize(_kamada_kawai_costfn, pos_arr.ravel(),
  576.                          method='L-BFGS-B', args=costargs, jac=True)
  577.  
  578.     return optresult.x.reshape((-1, dim))
  579.  
  580.  
  581. def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):
  582.     # Cost-function and gradient for Kamada-Kawai layout algorithm
  583.     nNodes = invdist.shape[0]
  584.     pos_arr = pos_vec.reshape((nNodes, dim))
  585.  
  586.     delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]
  587.     nodesep = np.linalg.norm(delta, axis=-1)
  588.     direction = np.einsum('ijk,ij->ijk',
  589.                           delta,
  590.                           1 / (nodesep + np.eye(nNodes) * 1e-3))
  591.  
  592.     offset = nodesep * invdist - 1.0
  593.     offset[np.diag_indices(nNodes)] = 0
  594.  
  595.     cost = 0.5 * np.sum(offset ** 2)
  596.     grad = (np.einsum('ij,ij,ijk->ik', invdist, offset, direction) -
  597.             np.einsum('ij,ij,ijk->jk', invdist, offset, direction))
  598.  
  599.     # Additional parabolic term to encourage mean position to be near origin:
  600.     sumpos = np.sum(pos_arr, axis=0)
  601.     cost += 0.5 * meanweight * np.sum(sumpos ** 2)
  602.     grad += meanweight * sumpos
  603.  
  604.     return (cost, grad.ravel())
  605.  
  606.  
  607. def spectral_layout(G, weight='weight', scale=1, center=None, dim=2):
  608.     """Position nodes using the eigenvectors of the graph Laplacian.
  609.  
  610.    Parameters
  611.    ----------
  612.    G : NetworkX graph or list of nodes
  613.        A position will be assigned to every node in G.
  614.  
  615.    weight : string or None   optional (default='weight')
  616.        The edge attribute that holds the numerical value used for
  617.        the edge weight.  If None, then all edge weights are 1.
  618.  
  619.    scale : number (default: 1)
  620.        Scale factor for positions.
  621.  
  622.    center : array-like or None
  623.        Coordinate pair around which to center the layout.
  624.  
  625.    dim : int
  626.        Dimension of layout.
  627.  
  628.    Returns
  629.    -------
  630.    pos : dict
  631.        A dictionary of positions keyed by node
  632.  
  633.    Examples
  634.    --------
  635.    >>> G = nx.path_graph(4)
  636.    >>> pos = nx.spectral_layout(G)
  637.  
  638.    Notes
  639.    -----
  640.    Directed graphs will be considered as undirected graphs when
  641.    positioning the nodes.
  642.  
  643.    For larger graphs (>500 nodes) this will use the SciPy sparse
  644.    eigenvalue solver (ARPACK).
  645.    """
  646.     # handle some special cases that break the eigensolvers
  647.     import numpy as np
  648.  
  649.     G, center = _process_params(G, center, dim)
  650.  
  651.     if len(G) <= 2:
  652.         if len(G) == 0:
  653.             pos = np.array([])
  654.         elif len(G) == 1:
  655.             pos = np.array([center])
  656.         else:
  657.             pos = np.array([np.zeros(dim), np.array(center)*2.0])
  658.         return dict(zip(G, pos))
  659.     try:
  660.         # Sparse matrix
  661.         if len(G) < 500:  # dense solver is faster for small graphs
  662.             raise ValueError
  663.         A = nx.to_scipy_sparse_matrix(G, weight=weight, dtype='d')
  664.         # Symmetrize directed graphs
  665.         if G.is_directed():
  666.             A = A + np.transpose(A)
  667.         pos = _sparse_spectral(A, dim)
  668.     except (ImportError, ValueError):
  669.         # Dense matrix
  670.         A = nx.to_numpy_matrix(G, weight=weight)
  671.         # Symmetrize directed graphs
  672.         if G.is_directed():
  673.             A = A + np.transpose(A)
  674.         pos = _spectral(A, dim)
  675.  
  676.     pos = rescale_layout(pos, scale) + center
  677.     pos = dict(zip(G, pos))
  678.     return pos
  679.  
  680.  
  681. def _spectral(A, dim=2):
  682.     # Input adjacency matrix A
  683.     # Uses dense eigenvalue solver from numpy
  684.     try:
  685.         import numpy as np
  686.     except ImportError:
  687.         msg = "spectral_layout() requires numpy: http://scipy.org/ "
  688.         raise ImportError(msg)
  689.     try:
  690.         nnodes, _ = A.shape
  691.     except AttributeError:
  692.         msg = "spectral() takes an adjacency matrix as input"
  693.         raise nx.NetworkXError(msg)
  694.  
  695.     # form Laplacian matrix
  696.     # make sure we have an array instead of a matrix
  697.     A = np.asarray(A)
  698.     I = np.identity(nnodes, dtype=A.dtype)
  699.     D = I * np.sum(A, axis=1)  # diagonal of degrees
  700.     L = D - A
  701.  
  702.     eigenvalues, eigenvectors = np.linalg.eig(L)
  703.     # sort and keep smallest nonzero
  704.     index = np.argsort(eigenvalues)[1:dim + 1]  # 0 index is zero eigenvalue
  705.     return np.real(eigenvectors[:, index])
  706.  
  707.  
  708. def _sparse_spectral(A, dim=2):
  709.     # Input adjacency matrix A
  710.     # Uses sparse eigenvalue solver from scipy
  711.     # Could use multilevel methods here, see Koren "On spectral graph drawing"
  712.     try:
  713.         import numpy as np
  714.         from scipy.sparse import spdiags
  715.         from scipy.sparse.linalg.eigen import eigsh
  716.     except ImportError:
  717.         msg = "_sparse_spectral() requires scipy & numpy: http://scipy.org/ "
  718.         raise ImportError(msg)
  719.     try:
  720.         nnodes, _ = A.shape
  721.     except AttributeError:
  722.         msg = "sparse_spectral() takes an adjacency matrix as input"
  723.         raise nx.NetworkXError(msg)
  724.  
  725.     # form Laplacian matrix
  726.     data = np.asarray(A.sum(axis=1).T)
  727.     D = spdiags(data, 0, nnodes, nnodes)
  728.     L = D - A
  729.  
  730.     k = dim + 1
  731.     # number of Lanczos vectors for ARPACK solver.What is the right scaling?
  732.     ncv = max(2 * k + 1, int(np.sqrt(nnodes)))
  733.     # return smallest k eigenvalues and eigenvectors
  734.     eigenvalues, eigenvectors = eigsh(L, k, which='SM', ncv=ncv)
  735.     index = np.argsort(eigenvalues)[1:k]  # 0 index is zero eigenvalue
  736.     return np.real(eigenvectors[:, index])
  737.  
  738.  
  739. def rescale_layout(pos, scale=1):
  740.     """Return scaled position array to (-scale, scale) in all axes.
  741.  
  742.    The function acts on NumPy arrays which hold position information.
  743.    Each position is one row of the array. The dimension of the space
  744.    equals the number of columns. Each coordinate in one column.
  745.  
  746.    To rescale, the mean (center) is subtracted from each axis separately.
  747.    Then all values are scaled so that the largest magnitude value
  748.    from all axes equals `scale` (thus, the aspect ratio is preserved).
  749.    The resulting NumPy Array is returned (order of rows unchanged).
  750.  
  751.    Parameters
  752.    ----------
  753.    pos : numpy array
  754.        positions to be scaled. Each row is a position.
  755.  
  756.    scale : number (default: 1)
  757.        The size of the resulting extent in all directions.
  758.  
  759.    Returns
  760.    -------
  761.    pos : numpy array
  762.        scaled positions. Each row is a position.
  763.  
  764.    """
  765.     # Find max length over all dimensions
  766.     lim = 0  # max coordinate for all axes
  767.     for i in range(pos.shape[1]):
  768.         pos[:, i] -= pos[:, i].mean()
  769.         lim = max(abs(pos[:, i]).max(), lim)
  770.     # rescale to (-scale, scale) in all directions, preserves aspect
  771.     if lim > 0:
  772.         for i in range(pos.shape[1]):
  773.             pos[:, i] *= scale / lim
  774.     return pos
  775.  
  776.  
  777. # fixture for nose tests
  778. def setup_module(module):
  779.     from nose import SkipTest
  780.     try:
  781.         import numpy
  782.     except:
  783.         raise SkipTest("NumPy not available")
  784.     try:
  785.         import scipy
  786.     except:
  787.         raise SkipTest("SciPy not available")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement