1 """
2 Convert NetworkX graphs to and from other formats.
3
4 from_whatever attemps to guess the input format
5
6 Create a 10 node random digraph
7
8 >>> from networkx import *
9 >>> import numpy
10 >>> a=numpy.reshape(numpy.random.random_integers(0,1,size=100),(10,10))
11 >>> D=from_whatever(a,create_using=DiGraph()) # or D=DiGraph(a)
12
13 For graphviz formats see networkx.drawing.nx_pygraphviz
14 or networkx.drawing.nx_pydot.
15
16 $Id: convert.py 701 2007-11-08 05:08:53Z aric $
17 """
18 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
19
20
21
22
23
24
25
26 import networkx
27
29 """
30 Returns a graph object ready to be populated.
31
32 If create_using is None return the default (just networkx.Graph())
33 If create_using.clear() works, assume it returns a graph object.
34 Otherwise raise an exception because create_using is not a networkx graph.
35
36 """
37 if create_using is None:
38 G=networkx.Graph()
39 else:
40 try:
41 G=create_using
42 G.clear()
43 except:
44 raise TypeError("Input graph is not a networkx graph type")
45 return G
46
47
49 """Attempt to make a NetworkX graph from an known type.
50
51 Current known types are:
52
53 any NetworkX graph
54 dict-of-dicts
55 dist-of-lists
56 numpy matrix
57 numpy ndarray
58 scipy sparse matrix
59 pygraphviz agraph
60
61 """
62
63 if hasattr(thing,"is_strict"):
64 try:
65 return networkx.from_agraph(thing,create_using=create_using)
66 except:
67 raise networkx.NetworkXError,\
68 "Input is not a correct pygraphviz graph."
69
70
71 if hasattr(thing,"add_node"):
72 try:
73 return from_dict_of_dicts(thing.adj,create_using=create_using)
74 except:
75 raise networkx.NetworkXError,\
76 "Input is not a correct NetworkX graph."
77
78
79 if isinstance(thing,dict):
80 try:
81 return from_dict_of_dicts(thing,create_using=create_using)
82 except:
83 try:
84 return from_dict_of_lists(thing,create_using=create_using)
85 except:
86 raise TypeError("Input is not known type.")
87
88
89
90 try:
91 import numpy
92 if isinstance(thing,numpy.core.defmatrix.matrix) or \
93 isinstance(thing,numpy.ndarray):
94 try:
95 return from_numpy_matrix(thing,create_using=create_using)
96 except:
97 raise networkx.NetworkXError,\
98 "Input is not a correct numpy matrix or array."
99 except ImportError:
100 pass
101
102
103 try:
104 import scipy
105 if hasattr(thing,"format"):
106 try:
107 return from_scipy_sparse_matrix(thing,create_using=create_using)
108 except:
109 raise networkx.NetworkXError, \
110 "Input is not a correct scipy sparse matrix type."
111 except ImportError:
112 pass
113
114
115 raise networkx.NetworkXError, \
116 "Input is not a known data type for conversion."
117
118 return
119
120
122 """Return graph G as a Python dict of lists.
123
124 If nodelist is defined return a dict of lists with only those nodes.
125
126 Completely ignores edge data for XGraph and XDiGraph.
127
128 """
129 if nodelist is None:
130 nodelist=G
131
132 d = {}
133 for n in nodelist:
134 d[n]=[nbr for nbr in G.neighbors(n) if nbr in nodelist]
135 return d
136
138 """Return a NetworkX graph G from a Python dict of lists.
139
140 """
141 G=_prep_create_using(create_using)
142 G.add_nodes_from(d)
143
144 if hasattr(G,"allow_multiedges") and G.multiedges and not G.is_directed():
145
146
147
148 seen={}
149 for node in d:
150 for nbr in d[node]:
151 if (node,nbr) not in seen:
152 G.add_edge(node,nbr)
153 seen[(nbr,node)]=1
154 else:
155 for node in d:
156 for nbr in d[node]:
157 G.add_edge(node,nbr)
158 return G
159
160
162 """Return graph G as a Python dictionary of dictionaries.
163
164 If nodelist is defined return a dict of dicts with only those nodes.
165
166 If edge_data is given, the value of the dictionary will be
167 set to edge_data for all edges. This is useful to make
168 an adjacency matrix type representation with 1 as the edge data.
169
170 """
171 if nodelist is None:
172 nodelist=G.nodes()
173 if edge_data is not None:
174 get_edge=lambda x,y:edge_data
175 else:
176 get_edge=G.get_edge
177
178 d = {}
179 for u in nodelist:
180 d[u]={}
181 for v in G.neighbors(u):
182 if v in nodelist:
183 d[u][v]=get_edge(u,v)
184 return d
185
186
188 """Return a NetworkX graph G from a Python dictionary of dictionaries.
189
190 The value of the inner dict becomes the edge_data for the NetworkX graph
191 EVEN if create_using is a NetworkX Graph which doesn't ever use this data.
192
193 If create_using is an XGraph/XDiGraph with multiedges==True, the edge_data
194 should be a list, though this routine does not check for that.
195
196 """
197 G=_prep_create_using(create_using)
198 G.add_nodes_from(d)
199
200
201
202
203
204
205 if hasattr(G,'allow_multiedges'):
206 if G.multiedges:
207
208
209 if G.is_directed():
210 for u,nbrs in d.iteritems():
211 for v,datalist in nbrs.iteritems():
212 dl=datalist[:]
213 G.pred[u][v]=dl
214 G.succ[u][v]=dl
215 else:
216 for u,nbrs in d.iteritems():
217 for v,datalist in nbrs.iteritems():
218 dl=datalist[:]
219 G.adj[u][v]=dl
220 G.adj[v][u]=dl
221 else:
222 for u,nbrs in d.iteritems():
223 for v,data in nbrs.iteritems():
224 G.add_edge(u,v,data)
225 else:
226 for u,nbrs in d.iteritems():
227 for v in nbrs:
228 G.add_edge(u,v)
229
230 return G
231
232
233
235 """Return adjacency matrix of graph as a numpy matrix.
236
237 If nodelist is defined return adjacency matrix with nodes in nodelist
238 in the order specified. If not the ordering is whatever order
239 the method G.nodes() produces.
240
241 For Graph/DiGraph types which have no edge data
242 The value of the entry A[u,v] is one if there is an edge u-v
243 and zero otherwise.
244
245 For XGraph/XDiGraph the edge data is assumed to be a weight and be
246 able to be converted to a valid numpy type (e.g. an int or a
247 float). The value of the entry A[u,v] is the weight given by
248 get_edge(u,v) one if there is an edge u-v and zero otherwise.
249
250 Graphs with multi-edges are not handled.
251
252 """
253 try:
254 import numpy
255 except ImportError:
256 raise ImportError, \
257 "Import Error: not able to import numpy: http://numpy.scipy.org "
258
259 if hasattr(G,"multiedges"):
260 if G.multiedges:
261 raise TypeError, \
262 "Conversion to numpy_matrix not allowed with for graphs with multiedges."
263
264 if nodelist is None:
265 nodelist=G.nodes()
266 nlen=len(nodelist)
267 index=dict(zip(nodelist,range(nlen)))
268 A = numpy.asmatrix(numpy.zeros((nlen,nlen)))
269 directed=G.is_directed()
270 for e in G.edges_iter(nodelist):
271 u=e[0]
272 v=e[1]
273 if len(e)==2:
274 d=1
275 else:
276 d=e[2]
277 if d is None: d=1
278 if u not in nodelist or v not in nodelist:
279 continue
280 A[index[u],index[v]]=d
281 if not directed:
282 A[index[v],index[u]]=d
283 return A
284
286 """Return networkx graph G from numpy matrix adjacency list.
287
288 >>> G=from_numpy_matrix(A)
289
290 """
291
292 try:
293 import numpy
294 except ImportError:
295 raise ImportError, \
296 "Import Error: not able to import numpy: http://numpy.scipy.org "
297
298 G=_prep_create_using(create_using)
299
300 nx,ny=A.shape
301
302 if nx!=ny:
303 raise networkx.NetworkXError, \
304 "Adjacency matrix is not square. nx,ny=%s"%(A.shape,)
305
306 G.add_nodes_from(range(nx))
307
308
309 x,y=numpy.asarray(A).nonzero()
310
311
312
313
314
315 if hasattr(G,'allow_multiedges'):
316 for (u,v) in zip(x,y):
317 G.add_edge(u,v,A[u,v])
318 else:
319 for (u,v) in zip(x,y):
320 G.add_edge(u,v)
321 return G
322
323
325 """Return adjacency matrix of graph as a scipy sparse matrix.
326
327 Uses lil_matrix format. To convert to other formats see
328 scipy.sparse documentation.
329
330 If nodelist is defined return adjacency matrix with nodes in nodelist
331 in the order specified. If not the ordering is whatever order
332 the method G.nodes() produces.
333
334 For Graph/DiGraph types which have no edge data
335 The value of the entry A[u,v] is one if there is an edge u-v
336 and zero otherwise.
337
338 For XGraph/XDiGraph the edge data is assumed to be a weight and be
339 able to be converted to a valid numpy type (e.g. an int or a
340 float). The value of the entry A[u,v] is the weight given by
341 get_edge(u,v) one if there is an edge u-v and zero otherwise.
342
343 Graphs with multi-edges are not handled.
344
345 >>> A=scipy_sparse_matrix(G)
346 >>> A.tocsr() # convert to compressed row storage
347
348 """
349 try:
350 from scipy import sparse
351 except ImportError:
352 raise ImportError, \
353 """Import Error: not able to import scipy sparse:
354 see http://scipy.org"""
355
356 if hasattr(G,"multiedges"):
357 if G.multiedges:
358 raise TypeError, \
359 "Conversion to scipy_sparse_matrix not allowed with for graphs with multiedges."
360
361 if nodelist is None:
362 nodelist=G.nodes()
363 nlen=len(nodelist)
364 index=dict(zip(nodelist,range(nlen)))
365 A = sparse.lil_matrix((nlen,nlen))
366 for e in G.edges_iter(nodelist):
367 u=e[0]
368 v=e[1]
369 if len(e)==2:
370 d=1
371 else:
372 d=e[2]
373 if d is None: d=1
374 if u not in nodelist or v not in nodelist:
375 continue
376 A[index[u],index[v]]=d
377 if not G.is_directed():
378 A[index[v],index[u]]=d
379 return A
380
381
383 """Return networkx graph G from scipy scipy sparse matrix
384 adjacency list.
385
386 >>> G=from_scipy_sparse_matrix(A)
387
388 """
389 G=_prep_create_using(create_using)
390
391
392
393
394
395
396 if hasattr(G,'allow_multiedges'):
397 xgraph=True
398 else:
399 xgraph=False
400
401
402 AA=A.tocoo()
403 nx,ny=AA.shape
404
405 if nx!=ny:
406 raise networkx.NetworkXError, \
407 "Adjacency matrix is not square. nx,ny=%s"%(A.shape,)
408
409
410 G.add_nodes_from(range(nx))
411 for i in range(AA.nnz):
412 e=AA.rowcol(i)
413 if xgraph:
414 e=(e[0],e[1],AA.getdata(i))
415 G.add_edge(e)
416 return G
417
418
420 import doctest
421 suite = doctest.DocFileSuite('tests/convert.txt',
422 package='networkx')
423 return suite
424
426 import doctest
427 suite = doctest.DocFileSuite('tests/convert_numpy.txt',
428 package='networkx')
429 return suite
430
432 import doctest
433 suite = doctest.DocFileSuite('tests/convert_scipy.txt',
434 package='networkx')
435 return suite
436
437
438
439
440 if __name__ == "__main__":
441 import os
442 import sys
443 import unittest
444 if sys.version_info[:2] < (2, 4):
445 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
446 sys.exit(-1)
447
448 nxbase=sys.path[0]+os.sep+os.pardir
449 sys.path.insert(0,nxbase)
450 unittest.TextTestRunner().run(_test_suite())
451 try:
452 import numpy
453 unittest.TextTestRunner().run(_test_suite_numpy())
454 except ImportError:
455 pass
456 try:
457 import scipy
458 unittest.TextTestRunner().run(_test_suite_scipy())
459 except ImportError:
460 pass
461