networkx.drawing.layout

1 """ 2 Layout (positioning) algorithms for graph drawing. 3 """ 4 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 5 __date__ = "$Date: 2005-06-15 08:53:26 -0600 (Wed, 15 Jun 2005) $" 6 __credits__ = """""" 7 __revision__ = "$Revision: 1033 $" 8 # Copyright (C) 2004,2005 by 9 # Aric Hagberg <hagberg@lanl.gov> 10 # Dan Schult <dschult@colgate.edu> 11 # Pieter Swart <swart@lanl.gov> 12 # Distributed under the terms of the GNU Lesser General Public License 13 # http://www.gnu.org/copyleft/lesser.html 14 from math import pi,sin,cos,sqrt 15 import sys 16 from networkx.utils import uniform_sequence 17 18 try: 19 import Numeric as N 20 except: 21 try: 22 import numpy as N 23 except: 24 raise ImportError,"numpy and/or Numeric can not be imported." 25 26

27 -def circular_layout(G, dim=2):

28 """ 29 Circular layout. 30 31 Crude version that doesn't try to minimize edge crossings. 32 33 """ 34 vpos={} 35 r=1.0 # radius of circle 36 t=0 37 dt=2.0*pi/G.order() 38 # should test for dim < 2 here 39 for v in G: 40 p=dim*[0.0] 41 p[0]=r*cos(t) 42 p[1]=r*sin(t) 43 vpos[v]=N.array(p) 44 t=t+dt 45 return vpos

46

47 -def shell_layout(G, nlist=None, dim=2 ):

48 """ 49 Shell layout. 50 Crude version that doesn't try to minimize edge crossings. 51 52 nlist is an optional list of lists of nodes to be drawn 53 at each shell level. Only one shell with all nodes will 54 be drawn if not specified. 55 56 """ 57 if nlist==None: 58 nlist=[G.nodes()] # draw the whole graph in one shell 59 60 nshells=len(nlist) 61 vpos={} 62 if len(nlist[0])==1: 63 initial_radius=0.0 # single node at center 64 else: 65 initial_radius=1.0 66 67 for s in range(nshells): 68 r=float(s+initial_radius) # radius of circle 69 t=0 70 slist=[n for n in nlist[s] if G.has_node(n)] 71 dt=2.0*pi/len(slist) 72 for n in slist: 73 p=dim*[0.0] 74 p[0]=r*cos(t) 75 p[1]=r*sin(t) 76 vpos[n]=N.array(p) 77 t=t+dt 78 return vpos

79

80 -def random_layout(G, dim=2):

81 """ Random layout.""" 82 import random 83 vpos={} 84 for v in G.nodes(): 85 vpos[v]=N.array([random.random() for i in range(dim)]) 86 return vpos

87

88 -def spring_layout(G, iterations=50, dim=2, node_pos=None):

89 """Spring force model layout""" 90 if node_pos==None : # set the initial positions randomly in 1x1 box 91 vpos=random_layout(G, dim=dim) 92 else: 93 vpos=node_pos 94 if iterations==0: 95 return vpos 96 if G.order()==0: 97 k=1.0 98 else: 99 k=N.sqrt(1.0/G.order()) # optimal distance between nodes 100 disp={} # displacements 101 102 # initial "temperature" (about .1 of domain area) 103 # this is the largest step allowed in the dynamics 104 # linearly step down by dt on each iteration so 105 # on last iteration it is size dt. 106 t=0.1 107 dt=0.1/float(iterations+1) 108 for i in range(0,iterations): 109 for v in G: 110 disp[v]=N.zeros(dim) 111 for u in G: 112 delta=vpos[v]-vpos[u] 113 dn=max(sqrt(N.dot(delta,delta)),0.01) 114 # repulsive force between all 115 deltaf=delta*k**2/dn**2 116 disp[v]=disp[v]+deltaf 117 # attractive force between neighbors 118 if G.has_edge(v,u): 119 deltaf=-delta*dn**2/(k*dn) 120 disp[v]=disp[v]+deltaf 121 122 # update positions 123 for v in G: 124 l=max(sqrt(N.dot(disp[v],disp[v])),0.01) 125 vpos[v]=vpos[v]+ disp[v]*t/l 126 t-=dt 127 return vpos

128 129

130 -def spectral_layout(G, dim=2, vpos=None, iterations=1000, eps=1.e-3):

131 """ 132 Return the position vectors for drawing G using spectral layout. 133 """ 134 # check silly cases 135 n=G.order() 136 if iterations==0 or n==0: 137 return vpos or {} 138 # create initial guesses for positions 139 if vpos is None: 140 # start with random positions 141 nodes=G.nodes() 142 uhat=[ ] 143 for p in range(dim): 144 rx=uniform_sequence(n) 145 uhat.append( dict( zip(nodes,rx) ) ) 146 else: 147 # use given positions 148 uhat=[] 149 nodes = vpos.keys() 150 for p in range(dim): 151 rx=[(v,pos[p]) for (v,pos) in vpos.iteritems()] 152 uhat.append( dict(rx) ) 153 # Find lowest eigenvectors 154 vhat=graph_low_ev_pi(uhat,G,eps,iterations) 155 # form position dict 156 vpos={} 157 for n in nodes: 158 poslist=[ vhat[p].get(n,0) for p in range(dim) ] 159 vpos[n]=N.array( poslist ) 160 return vpos

161

162 -def graph_low_ev_pi(uhat,G,eps=1.e-3,iterations=10000):

163 """ 164 Power Iteration method to find smallest eigenvectors of Laplacian(G). 165 Note: constant eigenvector has eigenvalue=0 but is not included 166 in the count of smallest eigenvalues. 167 168 uhat -- list of p initial guesses (dicts) for the p eigenvectors. 169 G -- The Graph from which Laplacian is calculated. 170 eps -- tolerance for norm of change in eigenvalue estimate. 171 iterations -- maximum number of iterations to use. 172 """ 173 # set up element value for constant eigenvector (squared) 174 constant=1.0/G.order() 175 # set up data for faster iteration 176 gg_data=_gershgorin_setup(G) 177 # 178 v=[] # setup v to hold eigenvectors 179 p=len(uhat) # number of guesses is number of vectors to return 180 for i in xrange(p): 181 vv=uhat[i] # get initial guess 182 ##normalize(vv) 183 norm=sqrt(N.sum([vals**2 for vals in vv.itervalues()])) 184 nn=1.0/norm 185 for k in vv: 186 vv[k] *= nn 187 ## 188 v.append(vv) 189 190 difference=eps+1 191 iii=0 192 # sys.stderr.write("drawing") 193 while difference>eps: 194 vhat=v[i] 195 ## Orthogonal to constant vector 196 dotprod=constant*sum(vhat.itervalues()) 197 for (k,val) in vhat.iteritems(): 198 vhat[k]-=dotprod 199 ## Orthogonal to other already found eigenvectors 200 for j in range(i): 201 ## vhat= vhat- <vhat,v[j]> * v[j] 202 s_d=sum([vhat.get(k,0)*val for (k,val) in v[j].iteritems()]) 203 for (k,value) in v[j].iteritems(): 204 vhat[k]=vhat.get(k,0)-value*s_d 205 ## 206 vv=_graph_gershgorin_dot_v(gg_data,vhat) 207 ##normalize(vv) vv=vv/|vv| 208 norm=sqrt(sum([vals**2 for vals in vv.itervalues()])) 209 if norm==0: 210 raise networkx.NetworkXError,"Eigenvector with zero eigenvalue given as input." 211 nn=1.0/norm 212 for k in vv: 213 vv[k] *= nn 214 ## 215 v[i]=vv 216 ##difference = |vhat-vv| 217 result=vhat.copy() 218 for (k,value) in vv.iteritems(): 219 result[k]=result.get(k,0)-value 220 difference=sqrt(sum([vals**2 for vals in result.itervalues()])) 221 #print "difference on iteration %s is %s"%(iii,difference) 222 ## 223 iii += 1 224 if iii==iterations: 225 #print "Maximum iterations achieved." 226 break 227 raise NetworkXError, "Maximum number of iterations exceeded." 228 # if iii%20==0: sys.stderr.write(".") 229 return v

230

231 -def _gershgorin_setup(G):

232 """ 233 Return a list of matrix properties to be used 234 to iteratively multiply B*v where v is a vector 235 and B=g*I-L and g is the Gershgorin estimate of 236 the largest eigenvalue of L=Laplacian(G). 237 238 Used as input to graph_gershgorin_dot_v() 239 """ 240 diag=G.degree(with_labels=True) 241 adj={} 242 g=max(diag.itervalues()) 243 for (n,degree) in diag.iteritems(): 244 diag[n]=g-degree 245 adj[n]=G.neighbors(n) 246 return [diag,adj]

247

248 -def _graph_gershgorin_dot_v(gg_data,v):

249 """ 250 Returns B*v where B=g*I-L and g is the Gershgorin estimate of the 251 largest eigenvalue of L. (g=max( deg(n) + sum_u(\|w_(n,u)\|) 252 253 We use this to iterate and find the smallest eigenvectors of L. 254 """ 255 (diag,adj)=gg_data 256 r={} 257 for (n,nbrs) in adj.iteritems(): 258 rn=sum([ v.get(u,0) for u in nbrs ]) 259 #rn=sum([ v.get(u,0)*w for (u,w) in nbrs.iteritems() ])#weighted adj matrix 260 r[n]=rn+v.get(n,0)*diag[n] 261 return r

262

263 -def _test_suite():

264 import doctest 265 suite = doctest.DocFileSuite('tests/drawing/layout.txt',package='networkx') 266 return suite

267 268 if __name__ == "__main__": 269 import os 270 import sys 271 import unittest 272 if sys.version_info[:2] < (2, 4): 273 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 274 sys.exit(-1) 275 # directory of networkx package (relative to this) 276 nxbase=sys.path[0]+os.sep+os.pardir 277 sys.path.insert(0,nxbase) # prepend to search path 278 unittest.TextTestRunner().run(_test_suite()) 279

Source Code for Module networkx.drawing.layout