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
9
10
11
12
13
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
28 """
29 Circular layout.
30
31 Crude version that doesn't try to minimize edge crossings.
32
33 """
34 vpos={}
35 r=1.0
36 t=0
37 dt=2.0*pi/G.order()
38
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
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()]
59
60 nshells=len(nlist)
61 vpos={}
62 if len(nlist[0])==1:
63 initial_radius=0.0
64 else:
65 initial_radius=1.0
66
67 for s in range(nshells):
68 r=float(s+initial_radius)
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
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
89 """Spring force model layout"""
90 if node_pos==None :
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())
100 disp={}
101
102
103
104
105
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
115 deltaf=delta*k**2/dn**2
116 disp[v]=disp[v]+deltaf
117
118 if G.has_edge(v,u):
119 deltaf=-delta*dn**2/(k*dn)
120 disp[v]=disp[v]+deltaf
121
122
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
131 """
132 Return the position vectors for drawing G using spectral layout.
133 """
134
135 n=G.order()
136 if iterations==0 or n==0:
137 return vpos or {}
138
139 if vpos is None:
140
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
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
154 vhat=graph_low_ev_pi(uhat,G,eps,iterations)
155
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
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
174 constant=1.0/G.order()
175
176 gg_data=_gershgorin_setup(G)
177
178 v=[]
179 p=len(uhat)
180 for i in xrange(p):
181 vv=uhat[i]
182
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
193 while difference>eps:
194 vhat=v[i]
195
196 dotprod=constant*sum(vhat.itervalues())
197 for (k,val) in vhat.iteritems():
198 vhat[k]-=dotprod
199
200 for j in range(i):
201
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
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
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
222
223 iii += 1
224 if iii==iterations:
225
226 break
227 raise NetworkXError, "Maximum number of iterations exceeded."
228
229 return v
230
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
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
260 r[n]=rn+v.get(n,0)*diag[n]
261 return r
262
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
276 nxbase=sys.path[0]+os.sep+os.pardir
277 sys.path.insert(0,nxbase)
278 unittest.TextTestRunner().run(_test_suite())
279