Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # 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")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement