networkx.convert

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 # Copyright (C) 2006 by 20 # Aric Hagberg <hagberg@lanl.gov> 21 # Dan Schult <dschult@colgate.edu> 22 # Pieter Swart <swart@lanl.gov> 23 # Distributed under the terms of the GNU Lesser General Public License 24 # http://www.gnu.org/copyleft/lesser.html 25 26 import networkx 27

28 -def _prep_create_using(create_using):

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

48 -def from_whatever(thing,create_using=None):

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 # pygraphviz agraph 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 # NX graph 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 # dict of dicts/lists 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 # numpy matrix or ndarray 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 # fail silently 101 102 # scipy sparse matrix - any format 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 # fail silently 113 114 115 raise networkx.NetworkXError, \ 116 "Input is not a known data type for conversion." 117 118 return

119 120

121 -def to_dict_of_lists(G,nodelist=None):

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

137 -def from_dict_of_lists(d,create_using=None):

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 # a dict_of_lists can't show multiedges. BUT for undirected graphs, 146 # each edge shows up twice in the dict_of_lists. 147 # So we need to treat this case separately. 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 # don't allow reverse edge to show up 154 else: 155 for node in d: 156 for nbr in d[node]: 157 G.add_edge(node,nbr) 158 return G

159 160

161 -def to_dict_of_dicts(G,nodelist=None,edge_data=None):

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

187 -def from_dict_of_dicts(d,create_using=None):

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 # is this a XGraph or XDiGraph? 201 # FIXME 202 # This is a bad way to check for whether edge data exists... 203 # If someone ever creates a graph class with edge data and 204 # without an allow_multiedges method, it won't work. 205 if hasattr(G,'allow_multiedges'): # assume edge data 206 if G.multiedges: 207 # this is a NetworkX graph with multiedges=True 208 # make a copy of the list of edge data (but not the edge data) 209 if G.is_directed(): 210 for u,nbrs in d.iteritems(): 211 for v,datalist in nbrs.iteritems(): 212 dl=datalist[:] # copy of the edge_data list 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[:] # copy of the edge_data list 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: # no edge data 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

234 -def to_numpy_matrix(G,nodelist=None):

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)))# dict mapping vertex name to position 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 # None would be a nan in numpy, use 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

285 -def from_numpy_matrix(A,create_using=None):

286 """Return networkx graph G from numpy matrix adjacency list. 287 288 >>> G=from_numpy_matrix(A) 289 290 """ 291 # This should never fail if you have created a numpy matrix with numpy... 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)) # make sure we get isolated nodes 307 308 # get a list of edges 309 x,y=numpy.asarray(A).nonzero() 310 # is this a XGraph or XDiGraph? 311 # FIXME 312 # This is a bad way to check for whether edge data exists... 313 # If someone ever creates a graph class with edge data and 314 # without an allow_multiedges method, it won't work. 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

324 -def to_scipy_sparse_matrix(G,nodelist=None):

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)))# dict mapping vertex name to position 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 # None would be a nan, use 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

382 -def from_scipy_sparse_matrix(A,create_using=None):

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 # is this a XGraph or XDiGraph? 392 # FIXME 393 # This is a bad way to check for whether edge data exists... 394 # If someone ever creates a graph class with edge data and 395 # without an allow_multiedges method, it won't work. 396 if hasattr(G,'allow_multiedges'): 397 xgraph=True 398 else: 399 xgraph=False 400 401 # convert everything to coo - not the most efficient 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)) # make sure we get isolated nodes 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

419 -def _test_suite():

420 import doctest 421 suite = doctest.DocFileSuite('tests/convert.txt', 422 package='networkx') 423 return suite

424

425 -def _test_suite_numpy():

426 import doctest 427 suite = doctest.DocFileSuite('tests/convert_numpy.txt', 428 package='networkx') 429 return suite

430

431 -def _test_suite_scipy():

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 # directory of networkx package (relative to this) 448 nxbase=sys.path[0]+os.sep+os.pardir 449 sys.path.insert(0,nxbase) # prepend to search path 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

Source Code for Module networkx.convert