NetworkX

Source code for networkx.drawing.layout

"""
******
Layout
******

Node positioning algorithms for graph drawing.
"""
#    Copyright (C) 2004-2012 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
import networkx as nx
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)"""
__all__ = ['circular_layout',
           'random_layout',
           'shell_layout',
           'spring_layout',
           'spectral_layout',
           'fruchterman_reingold_layout']

[docs]def random_layout(G,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 A position will be assigned to every node in G. dim : int Dimension of layout. Returns ------- dict : A dictionary of positions keyed by node Examples -------- >>> G = nx.lollipop_graph(4, 3) >>> pos = nx.random_layout(G) """ try: import numpy as np except ImportError: raise ImportError("random_layout() requires numpy: http://scipy.org/ ") n=len(G) pos=np.asarray(np.random.random((n,dim)),dtype=np.float32) return dict(zip(G,pos))
[docs]def circular_layout(G, dim=2, scale=1): # dim=2 only """Position nodes on a circle. Parameters ---------- G : NetworkX graph dim : int Dimension of layout, currently only dim=2 is supported scale : float Scale factor for positions Returns ------- 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. """ try: import numpy as np except ImportError: raise ImportError("circular_layout() requires numpy: http://scipy.org/ ") if len(G)==0: return {} if len(G)==1: return {G.nodes()[0]:(1,)*dim} t=np.arange(0,2.0*np.pi,2.0*np.pi/len(G),dtype=np.float32) pos=np.transpose(np.array([np.cos(t),np.sin(t)])) pos=_rescale_layout(pos,scale=scale) return dict(zip(G,pos))
[docs]def shell_layout(G,nlist=None,dim=2,scale=1): """Position nodes in concentric circles. Parameters ---------- G : NetworkX graph nlist : list of lists List of node lists for each shell. dim : int Dimension of layout, currently only dim=2 is supported scale : float Scale factor for positions Returns ------- 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. """ try: import numpy as np except ImportError: raise ImportError("shell_layout() requires numpy: http://scipy.org/ ") if len(G)==0: return {} if len(G)==1: return {G.nodes()[0]:(1,)*dim} if nlist==None: nlist=[G.nodes()] # draw the whole graph in one shell if len(nlist[0])==1: radius=0.0 # single node at center else: radius=1.0 # else start at r=1 npos={} for nodes in nlist: t=np.arange(0,2.0*np.pi,2.0*np.pi/len(nodes),dtype=np.float32) pos=np.transpose(np.array([radius*np.cos(t),radius*np.sin(t)])) npos.update(zip(nodes,pos)) radius+=1.0 # FIXME: rescale return npos
def fruchterman_reingold_layout(G,dim=2,k=None, pos=None, fixed=None, iterations=50, weight='weight', scale=1.0): """Position nodes using Fruchterman-Reingold force-directed algorithm. Parameters ---------- G : NetworkX graph dim : int Dimension of layout 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 list or tuple. If None, then nuse 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 : float (default=1.0) Scale factor for positions. The nodes are positioned in a box of size [0,scale] x [0,scale]. Returns ------- dict : A dictionary of positions keyed by node Examples -------- >>> G=nx.path_graph(4) >>> pos=nx.spring_layout(G) # The same using longer function name >>> pos=nx.fruchterman_reingold_layout(G) """ try: import numpy as np except ImportError: raise ImportError("fruchterman_reingold_layout() requires numpy: http://scipy.org/ ") 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: pos_arr=np.asarray(np.random.random((len(G),dim))) 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 {G.nodes()[0]:(1,)*dim} 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') pos=_sparse_fruchterman_reingold(A,dim,k,pos_arr,fixed,iterations) except: A=nx.to_numpy_matrix(G,weight=weight) pos=_fruchterman_reingold(A,dim,k,pos_arr,fixed,iterations) if fixed is None: pos=_rescale_layout(pos,scale=scale) return dict(zip(G,pos)) spring_layout=fruchterman_reingold_layout def _fruchterman_reingold(A, dim=2, k=None, pos=None, fixed=None, iterations=50): # 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: raise ImportError("_fruchterman_reingold() requires numpy: http://scipy.org/ ") try: nnodes,_=A.shape except AttributeError: raise nx.NetworkXError( "fruchterman_reingold() takes an adjacency matrix as input") A=np.asarray(A) # make sure we have an array instead of a matrix if pos==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. 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) 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 for i in range(pos.shape[1]): delta[:,:,i]= pos[:,i,None]-pos[:,i] # distance between points distance=np.sqrt((delta**2).sum(axis=-1)) # enforce minimum distance of 0.01 distance=np.where(distance<0.01,0.01,distance) # displacement "force" displacement=np.transpose(np.transpose(delta)*\ (k*k/distance**2-A*distance/k))\ .sum(axis=1) # update positions length=np.sqrt((displacement**2).sum(axis=1)) length=np.where(length<0.01,0.1,length) delta_pos=np.transpose(np.transpose(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 pos=_rescale_layout(pos) return pos def _sparse_fruchterman_reingold(A, dim=2, k=None, pos=None, fixed=None, iterations=50): # 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: raise ImportError("_sparse_fruchterman_reingold() requires numpy: http://scipy.org/ ") try: nnodes,_=A.shape except AttributeError: raise nx.NetworkXError( "fruchterman_reingold() takes an adjacency matrix as input") try: from scipy.sparse import spdiags,coo_matrix except ImportError: raise ImportError("_sparse_fruchterman_reingold() scipy numpy: http://scipy.org/ ") # make sure we have a LIst of Lists representation try: A=A.tolil() except: A=(coo_matrix(A)).tolil() if pos==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==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 pos=_rescale_layout(pos) return pos
[docs]def spectral_layout(G, dim=2, weight='weight', scale=1): """Position nodes using the eigenvectors of the graph Laplacian. Parameters ---------- G : NetworkX graph dim : int Dimension of 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 : float Scale factor for positions Returns ------- 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 unidrected 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 try: import numpy as np except ImportError: raise ImportError("spectral_layout() requires numpy: http://scipy.org/ ") if len(G)<=2: if len(G)==0: pos=np.array([]) elif len(G)==1: pos=np.array([[1,1]]) else: pos=np.array([[0,0.5],[1,0.5]]) 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='f') # 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) return dict(zip(G,pos))
def _spectral(A, dim=2): # Input adjacency matrix A # Uses dense eigenvalue solver from numpy try: import numpy as np except ImportError: raise ImportError("spectral_layout() requires numpy: http://scipy.org/ ") try: nnodes,_=A.shape except AttributeError: raise nx.NetworkXError(\ "spectral() takes an adjacency matrix as input") # 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 except ImportError: raise ImportError("_sparse_spectral() requires scipy & numpy: http://scipy.org/ ") try: from scipy.sparse.linalg.eigen import eigsh except ImportError: # scipy <0.9.0 names eigsh differently from scipy.sparse.linalg import eigen_symmetric as eigsh try: nnodes,_=A.shape except AttributeError: raise nx.NetworkXError(\ "sparse_spectral() takes an adjacency matrix as input") # 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): # rescale to (0,pscale) in all axes # shift origin to (0,0) lim=0 # max coordinate for all axes for i in range(pos.shape[1]): pos[:,i]-=pos[:,i].min() lim=max(pos[:,i].max(),lim) # rescale to (0,scale) in all directions, preserves aspect 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")