1 | """ |
---|
2 | This module provides functions to convert |
---|
3 | NetworkX graphs to and from other formats. |
---|
4 | |
---|
5 | The preferred way of converting data to a NetworkX graph |
---|
6 | is through the graph constuctor. The constructor calls |
---|
7 | the to_networkx_graph() function which attempts to guess the |
---|
8 | input type and convert it automatically. |
---|
9 | |
---|
10 | Examples |
---|
11 | -------- |
---|
12 | |
---|
13 | Create a 10 node random graph from a numpy matrix |
---|
14 | |
---|
15 | >>> import numpy |
---|
16 | >>> a=numpy.reshape(numpy.random.random_integers(0,1,size=100),(10,10)) |
---|
17 | >>> D=nx.DiGraph(a) |
---|
18 | |
---|
19 | or equivalently |
---|
20 | |
---|
21 | >>> D=nx.to_networkx_graph(a,create_using=nx.DiGraph()) |
---|
22 | |
---|
23 | Create a graph with a single edge from a dictionary of dictionaries |
---|
24 | |
---|
25 | >>> d={0: {1: 1}} # dict-of-dicts single edge (0,1) |
---|
26 | >>> G=nx.Graph(d) |
---|
27 | |
---|
28 | |
---|
29 | See Also |
---|
30 | -------- |
---|
31 | nx_pygraphviz, nx_pydot |
---|
32 | |
---|
33 | """ |
---|
34 | __author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)', |
---|
35 | 'Pieter Swart (swart@lanl.gov)', |
---|
36 | 'Dan Schult(dschult@colgate.edu)']) |
---|
37 | # Copyright (C) 2006-2011 by |
---|
38 | # Aric Hagberg <hagberg@lanl.gov> |
---|
39 | # Dan Schult <dschult@colgate.edu> |
---|
40 | # Pieter Swart <swart@lanl.gov> |
---|
41 | # All rights reserved. |
---|
42 | # BSD license. |
---|
43 | |
---|
44 | import warnings |
---|
45 | import networkx as nx |
---|
46 | |
---|
47 | __all__ = ['to_networkx_graph', |
---|
48 | 'from_dict_of_dicts', 'to_dict_of_dicts', |
---|
49 | 'from_dict_of_lists', 'to_dict_of_lists', |
---|
50 | 'from_edgelist', 'to_edgelist', |
---|
51 | 'from_numpy_matrix', 'to_numpy_matrix', |
---|
52 | 'to_numpy_recarray', |
---|
53 | 'from_scipy_sparse_matrix', 'to_scipy_sparse_matrix'] |
---|
54 | |
---|
55 | def _prep_create_using(create_using): |
---|
56 | """Return a graph object ready to be populated. |
---|
57 | |
---|
58 | If create_using is None return the default (just networkx.Graph()) |
---|
59 | If create_using.clear() works, assume it returns a graph object. |
---|
60 | Otherwise raise an exception because create_using is not a networkx graph. |
---|
61 | |
---|
62 | """ |
---|
63 | if create_using is None: |
---|
64 | G=nx.Graph() |
---|
65 | else: |
---|
66 | G=create_using |
---|
67 | try: |
---|
68 | G.clear() |
---|
69 | except: |
---|
70 | raise TypeError("Input graph is not a networkx graph type") |
---|
71 | return G |
---|
72 | |
---|
73 | def to_networkx_graph(data,create_using=None,multigraph_input=False): |
---|
74 | """Make a NetworkX graph from a known data structure. |
---|
75 | |
---|
76 | The preferred way to call this is automatically |
---|
77 | from the class constructor |
---|
78 | |
---|
79 | >>> d={0: {1: {'weight':1}}} # dict-of-dicts single edge (0,1) |
---|
80 | >>> G=nx.Graph(d) |
---|
81 | |
---|
82 | instead of the equivalent |
---|
83 | |
---|
84 | >>> G=nx.from_dict_of_dicts(d) |
---|
85 | |
---|
86 | Parameters |
---|
87 | ---------- |
---|
88 | data : a object to be converted |
---|
89 | Current known types are: |
---|
90 | any NetworkX graph |
---|
91 | dict-of-dicts |
---|
92 | dist-of-lists |
---|
93 | list of edges |
---|
94 | numpy matrix |
---|
95 | numpy ndarray |
---|
96 | scipy sparse matrix |
---|
97 | pygraphviz agraph |
---|
98 | |
---|
99 | create_using : NetworkX graph |
---|
100 | Use specified graph for result. Otherwise a new graph is created. |
---|
101 | |
---|
102 | multigraph_input : bool (default False) |
---|
103 | If True and data is a dict_of_dicts, |
---|
104 | try to create a multigraph assuming dict_of_dict_of_lists. |
---|
105 | If data and create_using are both multigraphs then create |
---|
106 | a multigraph from a multigraph. |
---|
107 | |
---|
108 | """ |
---|
109 | # NX graph |
---|
110 | if hasattr(data,"adj"): |
---|
111 | try: |
---|
112 | result= from_dict_of_dicts(data.adj,\ |
---|
113 | create_using=create_using,\ |
---|
114 | multigraph_input=data.is_multigraph()) |
---|
115 | if hasattr(data,'graph') and isinstance(data.graph,dict): |
---|
116 | result.graph=data.graph.copy() |
---|
117 | if hasattr(data,'node') and isinstance(data.node,dict): |
---|
118 | result.node=dict( (n,dd.copy()) for n,dd in data.node.items() ) |
---|
119 | return result |
---|
120 | except: |
---|
121 | raise nx.NetworkXError("Input is not a correct NetworkX graph.") |
---|
122 | |
---|
123 | # pygraphviz agraph |
---|
124 | if hasattr(data,"is_strict"): |
---|
125 | try: |
---|
126 | return nx.from_agraph(data,create_using=create_using) |
---|
127 | except: |
---|
128 | raise nx.NetworkXError("Input is not a correct pygraphviz graph.") |
---|
129 | |
---|
130 | # dict of dicts/lists |
---|
131 | if isinstance(data,dict): |
---|
132 | try: |
---|
133 | return from_dict_of_dicts(data,create_using=create_using,\ |
---|
134 | multigraph_input=multigraph_input) |
---|
135 | except: |
---|
136 | try: |
---|
137 | return from_dict_of_lists(data,create_using=create_using) |
---|
138 | except: |
---|
139 | raise TypeError("Input is not known type.") |
---|
140 | |
---|
141 | # list or generator of edges |
---|
142 | if (isinstance(data,list) |
---|
143 | or hasattr(data,'next') |
---|
144 | or hasattr(data, '__next__')): |
---|
145 | try: |
---|
146 | return from_edgelist(data,create_using=create_using) |
---|
147 | except: |
---|
148 | raise nx.NetworkXError("Input is not a valid edge list") |
---|
149 | |
---|
150 | # numpy matrix or ndarray |
---|
151 | try: |
---|
152 | import numpy |
---|
153 | if isinstance(data,numpy.matrix) or \ |
---|
154 | isinstance(data,numpy.ndarray): |
---|
155 | try: |
---|
156 | return from_numpy_matrix(data,create_using=create_using) |
---|
157 | except: |
---|
158 | raise nx.NetworkXError(\ |
---|
159 | "Input is not a correct numpy matrix or array.") |
---|
160 | except ImportError: |
---|
161 | warnings.warn('numpy not found, skipping conversion test.', |
---|
162 | ImportWarning) |
---|
163 | |
---|
164 | # scipy sparse matrix - any format |
---|
165 | try: |
---|
166 | import scipy |
---|
167 | if hasattr(data,"format"): |
---|
168 | try: |
---|
169 | return from_scipy_sparse_matrix(data,create_using=create_using) |
---|
170 | except: |
---|
171 | raise nx.NetworkXError(\ |
---|
172 | "Input is not a correct scipy sparse matrix type.") |
---|
173 | except ImportError: |
---|
174 | warnings.warn('scipy not found, skipping conversion test.', |
---|
175 | ImportWarning) |
---|
176 | |
---|
177 | |
---|
178 | raise nx.NetworkXError(\ |
---|
179 | "Input is not a known data type for conversion.") |
---|
180 | |
---|
181 | return |
---|
182 | |
---|
183 | |
---|
184 | def convert_to_undirected(G): |
---|
185 | """Return a new undirected representation of the graph G.""" |
---|
186 | return G.to_undirected() |
---|
187 | |
---|
188 | |
---|
189 | def convert_to_directed(G): |
---|
190 | """Return a new directed representation of the graph G.""" |
---|
191 | return G.to_directed() |
---|
192 | |
---|
193 | |
---|
194 | def to_dict_of_lists(G,nodelist=None): |
---|
195 | """Return adjacency representation of graph as a dictionary of lists. |
---|
196 | |
---|
197 | Parameters |
---|
198 | ---------- |
---|
199 | G : graph |
---|
200 | A NetworkX graph |
---|
201 | |
---|
202 | nodelist : list |
---|
203 | Use only nodes specified in nodelist |
---|
204 | |
---|
205 | Notes |
---|
206 | ----- |
---|
207 | Completely ignores edge data for MultiGraph and MultiDiGraph. |
---|
208 | |
---|
209 | """ |
---|
210 | if nodelist is None: |
---|
211 | nodelist=G |
---|
212 | |
---|
213 | d = {} |
---|
214 | for n in nodelist: |
---|
215 | d[n]=[nbr for nbr in G.neighbors(n) if nbr in nodelist] |
---|
216 | return d |
---|
217 | |
---|
218 | def from_dict_of_lists(d,create_using=None): |
---|
219 | """Return a graph from a dictionary of lists. |
---|
220 | |
---|
221 | Parameters |
---|
222 | ---------- |
---|
223 | d : dictionary of lists |
---|
224 | A dictionary of lists adjacency representation. |
---|
225 | |
---|
226 | create_using : NetworkX graph |
---|
227 | Use specified graph for result. Otherwise a new graph is created. |
---|
228 | |
---|
229 | Examples |
---|
230 | -------- |
---|
231 | >>> dol= {0:[1]} # single edge (0,1) |
---|
232 | >>> G=nx.from_dict_of_lists(dol) |
---|
233 | |
---|
234 | or |
---|
235 | >>> G=nx.Graph(dol) # use Graph constructor |
---|
236 | |
---|
237 | """ |
---|
238 | G=_prep_create_using(create_using) |
---|
239 | G.add_nodes_from(d) |
---|
240 | if G.is_multigraph() and not G.is_directed(): |
---|
241 | # a dict_of_lists can't show multiedges. BUT for undirected graphs, |
---|
242 | # each edge shows up twice in the dict_of_lists. |
---|
243 | # So we need to treat this case separately. |
---|
244 | seen={} |
---|
245 | for node,nbrlist in d.items(): |
---|
246 | for nbr in nbrlist: |
---|
247 | if nbr not in seen: |
---|
248 | G.add_edge(node,nbr) |
---|
249 | seen[node]=1 # don't allow reverse edge to show up |
---|
250 | else: |
---|
251 | G.add_edges_from( ((node,nbr) for node,nbrlist in d.items() |
---|
252 | for nbr in nbrlist) ) |
---|
253 | return G |
---|
254 | |
---|
255 | |
---|
256 | def to_dict_of_dicts(G,nodelist=None,edge_data=None): |
---|
257 | """Return adjacency representation of graph as a dictionary of dictionaries. |
---|
258 | |
---|
259 | Parameters |
---|
260 | ---------- |
---|
261 | G : graph |
---|
262 | A NetworkX graph |
---|
263 | |
---|
264 | nodelist : list |
---|
265 | Use only nodes specified in nodelist |
---|
266 | |
---|
267 | edge_data : list, optional |
---|
268 | If provided, the value of the dictionary will be |
---|
269 | set to edge_data for all edges. This is useful to make |
---|
270 | an adjacency matrix type representation with 1 as the edge data. |
---|
271 | If edgedata is None, the edgedata in G is used to fill the values. |
---|
272 | If G is a multigraph, the edgedata is a dict for each pair (u,v). |
---|
273 | """ |
---|
274 | dod={} |
---|
275 | if nodelist is None: |
---|
276 | if edge_data is None: |
---|
277 | for u,nbrdict in G.adjacency_iter(): |
---|
278 | dod[u]=nbrdict.copy() |
---|
279 | else: # edge_data is not None |
---|
280 | for u,nbrdict in G.adjacency_iter(): |
---|
281 | dod[u]=dod.fromkeys(nbrdict, edge_data) |
---|
282 | else: # nodelist is not None |
---|
283 | if edge_data is None: |
---|
284 | for u in nodelist: |
---|
285 | dod[u]={} |
---|
286 | for v,data in ((v,data) for v,data in G[u].items() if v in nodelist): |
---|
287 | dod[u][v]=data |
---|
288 | else: # nodelist and edge_data are not None |
---|
289 | for u in nodelist: |
---|
290 | dod[u]={} |
---|
291 | for v in ( v for v in G[u] if v in nodelist): |
---|
292 | dod[u][v]=edge_data |
---|
293 | return dod |
---|
294 | |
---|
295 | def from_dict_of_dicts(d,create_using=None,multigraph_input=False): |
---|
296 | """Return a graph from a dictionary of dictionaries. |
---|
297 | |
---|
298 | Parameters |
---|
299 | ---------- |
---|
300 | d : dictionary of dictionaries |
---|
301 | A dictionary of dictionaries adjacency representation. |
---|
302 | |
---|
303 | create_using : NetworkX graph |
---|
304 | Use specified graph for result. Otherwise a new graph is created. |
---|
305 | |
---|
306 | multigraph_input : bool (default False) |
---|
307 | When True, the values of the inner dict are assumed |
---|
308 | to be containers of edge data for multiple edges. |
---|
309 | Otherwise this routine assumes the edge data are singletons. |
---|
310 | |
---|
311 | Examples |
---|
312 | -------- |
---|
313 | >>> dod= {0: {1:{'weight':1}}} # single edge (0,1) |
---|
314 | >>> G=nx.from_dict_of_dicts(dod) |
---|
315 | |
---|
316 | or |
---|
317 | >>> G=nx.Graph(dod) # use Graph constructor |
---|
318 | |
---|
319 | """ |
---|
320 | G=_prep_create_using(create_using) |
---|
321 | G.add_nodes_from(d) |
---|
322 | # is dict a MultiGraph or MultiDiGraph? |
---|
323 | if multigraph_input: |
---|
324 | # make a copy of the list of edge data (but not the edge data) |
---|
325 | if G.is_directed(): |
---|
326 | if G.is_multigraph(): |
---|
327 | G.add_edges_from( (u,v,key,data) |
---|
328 | for u,nbrs in d.items() |
---|
329 | for v,datadict in nbrs.items() |
---|
330 | for key,data in datadict.items() |
---|
331 | ) |
---|
332 | else: |
---|
333 | G.add_edges_from( (u,v,data) |
---|
334 | for u,nbrs in d.items() |
---|
335 | for v,datadict in nbrs.items() |
---|
336 | for key,data in datadict.items() |
---|
337 | ) |
---|
338 | else: # Undirected |
---|
339 | if G.is_multigraph(): |
---|
340 | seen=set() # don't add both directions of undirected graph |
---|
341 | for u,nbrs in d.items(): |
---|
342 | for v,datadict in nbrs.items(): |
---|
343 | if (u,v) not in seen: |
---|
344 | G.add_edges_from( (u,v,key,data) |
---|
345 | for key,data in datadict.items() |
---|
346 | ) |
---|
347 | seen.add((v,u)) |
---|
348 | else: |
---|
349 | seen=set() # don't add both directions of undirected graph |
---|
350 | for u,nbrs in d.items(): |
---|
351 | for v,datadict in nbrs.items(): |
---|
352 | if (u,v) not in seen: |
---|
353 | G.add_edges_from( (u,v,data) |
---|
354 | for key,data in datadict.items() ) |
---|
355 | seen.add((v,u)) |
---|
356 | |
---|
357 | else: # not a multigraph to multigraph transfer |
---|
358 | if G.is_multigraph() and not G.is_directed(): |
---|
359 | # d can have both representations u-v, v-u in dict. Only add one. |
---|
360 | # We don't need this check for digraphs since we add both directions, |
---|
361 | # or for Graph() since it is done implicitly (parallel edges not allowed) |
---|
362 | seen=set() |
---|
363 | for u,nbrs in d.items(): |
---|
364 | for v,data in nbrs.items(): |
---|
365 | if (u,v) not in seen: |
---|
366 | G.add_edge(u,v,attr_dict=data) |
---|
367 | seen.add((v,u)) |
---|
368 | else: |
---|
369 | G.add_edges_from( ( (u,v,data) |
---|
370 | for u,nbrs in d.items() |
---|
371 | for v,data in nbrs.items()) ) |
---|
372 | return G |
---|
373 | |
---|
374 | def to_edgelist(G,nodelist=None): |
---|
375 | """Return a list of edges in the graph. |
---|
376 | |
---|
377 | Parameters |
---|
378 | ---------- |
---|
379 | G : graph |
---|
380 | A NetworkX graph |
---|
381 | |
---|
382 | nodelist : list |
---|
383 | Use only nodes specified in nodelist |
---|
384 | |
---|
385 | """ |
---|
386 | if nodelist is None: |
---|
387 | return G.edges(data=True) |
---|
388 | else: |
---|
389 | return G.edges(nodelist,data=True) |
---|
390 | |
---|
391 | def from_edgelist(edgelist,create_using=None): |
---|
392 | """Return a graph from a list of edges. |
---|
393 | |
---|
394 | Parameters |
---|
395 | ---------- |
---|
396 | edgelist : list or iterator |
---|
397 | Edge tuples |
---|
398 | |
---|
399 | create_using : NetworkX graph |
---|
400 | Use specified graph for result. Otherwise a new graph is created. |
---|
401 | |
---|
402 | Examples |
---|
403 | -------- |
---|
404 | >>> edgelist= [(0,1)] # single edge (0,1) |
---|
405 | >>> G=nx.from_edgelist(edgelist) |
---|
406 | |
---|
407 | or |
---|
408 | >>> G=nx.Graph(edgelist) # use Graph constructor |
---|
409 | |
---|
410 | """ |
---|
411 | G=_prep_create_using(create_using) |
---|
412 | G.add_edges_from(edgelist) |
---|
413 | return G |
---|
414 | |
---|
415 | def to_numpy_matrix(G, nodelist=None, dtype=None, order=None, |
---|
416 | multigraph_weight=sum, weight='weight'): |
---|
417 | """Return the graph adjacency matrix as a NumPy matrix. |
---|
418 | |
---|
419 | Parameters |
---|
420 | ---------- |
---|
421 | G : graph |
---|
422 | The NetworkX graph used to construct the NumPy matrix. |
---|
423 | |
---|
424 | nodelist : list, optional |
---|
425 | The rows and columns are ordered according to the nodes in `nodelist`. |
---|
426 | If `nodelist` is None, then the ordering is produced by G.nodes(). |
---|
427 | |
---|
428 | dtype : NumPy data type, optional |
---|
429 | A valid single NumPy data type used to initialize the array. |
---|
430 | This must be a simple type such as int or numpy.float64 and |
---|
431 | not a compound data type (see to_numpy_recarray) |
---|
432 | If None, then the NumPy default is used. |
---|
433 | |
---|
434 | order : {'C', 'F'}, optional |
---|
435 | Whether to store multidimensional data in C- or Fortran-contiguous |
---|
436 | (row- or column-wise) order in memory. If None, then the NumPy default |
---|
437 | is used. |
---|
438 | |
---|
439 | multigraph_weight : {sum, min, max}, optional |
---|
440 | An operator that determines how weights in multigraphs are handled. |
---|
441 | The default is to sum the weights of the multiple edges. |
---|
442 | |
---|
443 | weight : string or None optional (default='weight') |
---|
444 | The edge attribute that holds the numerical value used for |
---|
445 | the edge weight. If None then all edge weights are 1. |
---|
446 | |
---|
447 | |
---|
448 | Returns |
---|
449 | ------- |
---|
450 | M : NumPy matrix |
---|
451 | Graph adjacency matrix. |
---|
452 | |
---|
453 | See Also |
---|
454 | -------- |
---|
455 | to_numpy_recarray, from_numpy_matrix |
---|
456 | |
---|
457 | Notes |
---|
458 | ----- |
---|
459 | The matrix entries are assigned with weight edge attribute. When |
---|
460 | an edge does not have the weight attribute, the value of the entry is 1. |
---|
461 | For multiple edges, the values of the entries are the sums of the edge |
---|
462 | attributes for each edge. |
---|
463 | |
---|
464 | When `nodelist` does not contain every node in `G`, the matrix is built |
---|
465 | from the subgraph of `G` that is induced by the nodes in `nodelist`. |
---|
466 | |
---|
467 | Examples |
---|
468 | -------- |
---|
469 | >>> G = nx.MultiDiGraph() |
---|
470 | >>> G.add_edge(0,1,weight=2) |
---|
471 | >>> G.add_edge(1,0) |
---|
472 | >>> G.add_edge(2,2,weight=3) |
---|
473 | >>> G.add_edge(2,2) |
---|
474 | >>> nx.to_numpy_matrix(G, nodelist=[0,1,2]) |
---|
475 | matrix([[ 0., 2., 0.], |
---|
476 | [ 1., 0., 0.], |
---|
477 | [ 0., 0., 4.]]) |
---|
478 | """ |
---|
479 | try: |
---|
480 | import numpy as np |
---|
481 | except ImportError: |
---|
482 | raise ImportError(\ |
---|
483 | "to_numpy_matrix() requires numpy: http://scipy.org/ ") |
---|
484 | |
---|
485 | if nodelist is None: |
---|
486 | nodelist = G.nodes() |
---|
487 | |
---|
488 | nodeset = set(nodelist) |
---|
489 | if len(nodelist) != len(nodeset): |
---|
490 | msg = "Ambiguous ordering: `nodelist` contained duplicates." |
---|
491 | raise nx.NetworkXError(msg) |
---|
492 | |
---|
493 | nlen=len(nodelist) |
---|
494 | undirected = not G.is_directed() |
---|
495 | index=dict(zip(nodelist,range(nlen))) |
---|
496 | |
---|
497 | if G.is_multigraph(): |
---|
498 | # Handle MultiGraphs and MultiDiGraphs |
---|
499 | # array of nan' to start with, any leftover nans will be converted to 0 |
---|
500 | # nans are used so we can use sum, min, max for multigraphs |
---|
501 | M = np.zeros((nlen,nlen), dtype=dtype, order=order)+np.nan |
---|
502 | # use numpy nan-aware operations |
---|
503 | operator={sum:np.nansum, min:np.nanmin, max:np.nanmax} |
---|
504 | try: |
---|
505 | op=operator[multigraph_weight] |
---|
506 | except: |
---|
507 | raise ValueError('multigraph_weight must be sum, min, or max') |
---|
508 | |
---|
509 | for u,v,attrs in G.edges_iter(data=True): |
---|
510 | if (u in nodeset) and (v in nodeset): |
---|
511 | i,j = index[u],index[v] |
---|
512 | e_weight = attrs.get(weight, 1) |
---|
513 | M[i,j] = op([e_weight,M[i,j]]) |
---|
514 | if undirected: |
---|
515 | M[j,i] = M[i,j] |
---|
516 | # convert any nans to zeros |
---|
517 | M = np.asmatrix(np.nan_to_num(M)) |
---|
518 | else: |
---|
519 | # Graph or DiGraph, this is much faster than above |
---|
520 | M = np.zeros((nlen,nlen), dtype=dtype, order=order) |
---|
521 | for u,nbrdict in G.adjacency_iter(): |
---|
522 | for v,d in nbrdict.items(): |
---|
523 | try: |
---|
524 | M[index[u],index[v]]=d.get(weight,1) |
---|
525 | except KeyError: |
---|
526 | pass |
---|
527 | M = np.asmatrix(M) |
---|
528 | return M |
---|
529 | |
---|
530 | |
---|
531 | def from_numpy_matrix(A,create_using=None): |
---|
532 | """Return a graph from numpy matrix. |
---|
533 | |
---|
534 | The numpy matrix is interpreted as an adjacency matrix for the graph. |
---|
535 | |
---|
536 | Parameters |
---|
537 | ---------- |
---|
538 | A : numpy matrix |
---|
539 | An adjacency matrix representation of a graph |
---|
540 | |
---|
541 | create_using : NetworkX graph |
---|
542 | Use specified graph for result. The default is Graph() |
---|
543 | |
---|
544 | Notes |
---|
545 | ----- |
---|
546 | If the numpy matrix has a single data type for each matrix entry it |
---|
547 | will be converted to an appropriate Python data type. |
---|
548 | |
---|
549 | If the numpy matrix has a user-specified compound data type the names |
---|
550 | of the data fields will be used as attribute keys in the resulting |
---|
551 | NetworkX graph. |
---|
552 | |
---|
553 | See Also |
---|
554 | -------- |
---|
555 | to_numpy_matrix, to_numpy_recarray |
---|
556 | |
---|
557 | Examples |
---|
558 | -------- |
---|
559 | Simple integer weights on edges: |
---|
560 | |
---|
561 | >>> import numpy |
---|
562 | >>> A=numpy.matrix([[1,1],[2,1]]) |
---|
563 | >>> G=nx.from_numpy_matrix(A) |
---|
564 | |
---|
565 | User defined compound data type on edges: |
---|
566 | |
---|
567 | >>> import numpy |
---|
568 | >>> dt=[('weight',float),('cost',int)] |
---|
569 | >>> A=numpy.matrix([[(1.0,2)]],dtype=dt) |
---|
570 | >>> G=nx.from_numpy_matrix(A) |
---|
571 | >>> G.edges(data=True) |
---|
572 | [(0, 0, {'cost': 2, 'weight': 1.0})] |
---|
573 | """ |
---|
574 | kind_to_python_type={'f':float, |
---|
575 | 'i':int, |
---|
576 | 'u':int, |
---|
577 | 'b':bool, |
---|
578 | 'c':complex, |
---|
579 | 'S':str, |
---|
580 | 'V':'void'} |
---|
581 | |
---|
582 | try: # Python 3.x |
---|
583 | blurb = chr(1245) # just to trigger the exception |
---|
584 | kind_to_python_type['U']=str |
---|
585 | except ValueError: # Python 2.6+ |
---|
586 | kind_to_python_type['U']=unicode |
---|
587 | |
---|
588 | # This should never fail if you have created a numpy matrix with numpy... |
---|
589 | try: |
---|
590 | import numpy as np |
---|
591 | except ImportError: |
---|
592 | raise ImportError(\ |
---|
593 | "from_numpy_matrix() requires numpy: http://scipy.org/ ") |
---|
594 | |
---|
595 | G=_prep_create_using(create_using) |
---|
596 | n,m=A.shape |
---|
597 | if n!=m: |
---|
598 | raise nx.NetworkXError("Adjacency matrix is not square.", |
---|
599 | "nx,ny=%s"%(A.shape,)) |
---|
600 | dt=A.dtype |
---|
601 | try: |
---|
602 | python_type=kind_to_python_type[dt.kind] |
---|
603 | except: |
---|
604 | raise TypeError("Unknown numpy data type: %s"%dt) |
---|
605 | |
---|
606 | # make sure we get isolated nodes |
---|
607 | G.add_nodes_from(range(n)) |
---|
608 | # get a list of edges |
---|
609 | x,y=np.asarray(A).nonzero() |
---|
610 | |
---|
611 | # handle numpy constructed data type |
---|
612 | if python_type is 'void': |
---|
613 | fields=sorted([(offset,dtype,name) for name,(dtype,offset) in |
---|
614 | A.dtype.fields.items()]) |
---|
615 | for (u,v) in zip(x,y): |
---|
616 | attr={} |
---|
617 | for (offset,dtype,name),val in zip(fields,A[u,v]): |
---|
618 | attr[name]=kind_to_python_type[dtype.kind](val) |
---|
619 | G.add_edge(u,v,attr) |
---|
620 | else: # basic data type |
---|
621 | G.add_edges_from( ((u,v,{'weight':python_type(A[u,v])}) |
---|
622 | for (u,v) in zip(x,y)) ) |
---|
623 | return G |
---|
624 | |
---|
625 | |
---|
626 | def to_numpy_recarray(G,nodelist=None, |
---|
627 | dtype=[('weight',float)], |
---|
628 | order=None): |
---|
629 | """Return the graph adjacency matrix as a NumPy recarray. |
---|
630 | |
---|
631 | Parameters |
---|
632 | ---------- |
---|
633 | G : graph |
---|
634 | The NetworkX graph used to construct the NumPy matrix. |
---|
635 | |
---|
636 | nodelist : list, optional |
---|
637 | The rows and columns are ordered according to the nodes in `nodelist`. |
---|
638 | If `nodelist` is None, then the ordering is produced by G.nodes(). |
---|
639 | |
---|
640 | dtype : NumPy data-type, optional |
---|
641 | A valid NumPy named dtype used to initialize the NumPy recarray. |
---|
642 | The data type names are assumed to be keys in the graph edge attribute |
---|
643 | dictionary. |
---|
644 | |
---|
645 | order : {'C', 'F'}, optional |
---|
646 | Whether to store multidimensional data in C- or Fortran-contiguous |
---|
647 | (row- or column-wise) order in memory. If None, then the NumPy default |
---|
648 | is used. |
---|
649 | |
---|
650 | Returns |
---|
651 | ------- |
---|
652 | M : NumPy recarray |
---|
653 | The graph with specified edge data as a Numpy recarray |
---|
654 | |
---|
655 | Notes |
---|
656 | ----- |
---|
657 | When `nodelist` does not contain every node in `G`, the matrix is built |
---|
658 | from the subgraph of `G` that is induced by the nodes in `nodelist`. |
---|
659 | |
---|
660 | Examples |
---|
661 | -------- |
---|
662 | >>> G = nx.Graph() |
---|
663 | >>> G.add_edge(1,2,weight=7.0,cost=5) |
---|
664 | >>> A=nx.to_numpy_recarray(G,dtype=[('weight',float),('cost',int)]) |
---|
665 | >>> print(A.weight) |
---|
666 | [[ 0. 7.] |
---|
667 | [ 7. 0.]] |
---|
668 | >>> print(A.cost) |
---|
669 | [[0 5] |
---|
670 | [5 0]] |
---|
671 | """ |
---|
672 | try: |
---|
673 | import numpy as np |
---|
674 | except ImportError: |
---|
675 | raise ImportError(\ |
---|
676 | "to_numpy_matrix() requires numpy: http://scipy.org/ ") |
---|
677 | |
---|
678 | if G.is_multigraph(): |
---|
679 | raise nx.NetworkXError("Not implemented for multigraphs.") |
---|
680 | |
---|
681 | if nodelist is None: |
---|
682 | nodelist = G.nodes() |
---|
683 | |
---|
684 | nodeset = set(nodelist) |
---|
685 | if len(nodelist) != len(nodeset): |
---|
686 | msg = "Ambiguous ordering: `nodelist` contained duplicates." |
---|
687 | raise nx.NetworkXError(msg) |
---|
688 | |
---|
689 | nlen=len(nodelist) |
---|
690 | undirected = not G.is_directed() |
---|
691 | index=dict(zip(nodelist,range(nlen))) |
---|
692 | M = np.zeros((nlen,nlen), dtype=dtype, order=order) |
---|
693 | |
---|
694 | names=M.dtype.names |
---|
695 | for u,v,attrs in G.edges_iter(data=True): |
---|
696 | if (u in nodeset) and (v in nodeset): |
---|
697 | i,j = index[u],index[v] |
---|
698 | values=tuple([attrs[n] for n in names]) |
---|
699 | M[i,j] = values |
---|
700 | if undirected: |
---|
701 | M[j,i] = M[i,j] |
---|
702 | |
---|
703 | return M.view(np.recarray) |
---|
704 | |
---|
705 | |
---|
706 | def to_scipy_sparse_matrix(G, nodelist=None, dtype=None, |
---|
707 | weight='weight', format='csr'): |
---|
708 | """Return the graph adjacency matrix as a SciPy sparse matrix. |
---|
709 | |
---|
710 | Parameters |
---|
711 | ---------- |
---|
712 | G : graph |
---|
713 | The NetworkX graph used to construct the NumPy matrix. |
---|
714 | |
---|
715 | nodelist : list, optional |
---|
716 | The rows and columns are ordered according to the nodes in `nodelist`. |
---|
717 | If `nodelist` is None, then the ordering is produced by G.nodes(). |
---|
718 | |
---|
719 | dtype : NumPy data-type, optional |
---|
720 | A valid NumPy dtype used to initialize the array. If None, then the |
---|
721 | NumPy default is used. |
---|
722 | |
---|
723 | weight : string or None optional (default='weight') |
---|
724 | The edge attribute that holds the numerical value used for |
---|
725 | the edge weight. If None then all edge weights are 1. |
---|
726 | |
---|
727 | format : str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'} |
---|
728 | The type of the matrix to be returned (default 'csr'). For |
---|
729 | some algorithms different implementations of sparse matrices |
---|
730 | can perform better. See [1]_ for details. |
---|
731 | |
---|
732 | Returns |
---|
733 | ------- |
---|
734 | M : SciPy sparse matrix |
---|
735 | Graph adjacency matrix. |
---|
736 | |
---|
737 | Notes |
---|
738 | ----- |
---|
739 | The matrix entries are populated using the edge attribute held in |
---|
740 | parameter weight. When an edge does not have that attribute, the |
---|
741 | value of the entry is 1. |
---|
742 | |
---|
743 | For multiple edges the matrix values are the sums of the edge weights. |
---|
744 | |
---|
745 | When `nodelist` does not contain every node in `G`, the matrix is built |
---|
746 | from the subgraph of `G` that is induced by the nodes in `nodelist`. |
---|
747 | |
---|
748 | Uses coo_matrix format. To convert to other formats specify the |
---|
749 | format= keyword. |
---|
750 | |
---|
751 | Examples |
---|
752 | -------- |
---|
753 | >>> G = nx.MultiDiGraph() |
---|
754 | >>> G.add_edge(0,1,weight=2) |
---|
755 | >>> G.add_edge(1,0) |
---|
756 | >>> G.add_edge(2,2,weight=3) |
---|
757 | >>> G.add_edge(2,2) |
---|
758 | >>> S = nx.to_scipy_sparse_matrix(G, nodelist=[0,1,2]) |
---|
759 | >>> print(S.todense()) |
---|
760 | [[0 2 0] |
---|
761 | [1 0 0] |
---|
762 | [0 0 4]] |
---|
763 | |
---|
764 | References |
---|
765 | ---------- |
---|
766 | .. [1] Scipy Dev. References, "Sparse Matrices", |
---|
767 | http://docs.scipy.org/doc/scipy/reference/sparse.html |
---|
768 | """ |
---|
769 | try: |
---|
770 | from scipy import sparse |
---|
771 | except ImportError: |
---|
772 | raise ImportError(\ |
---|
773 | "to_scipy_sparse_matrix() requires scipy: http://scipy.org/ ") |
---|
774 | |
---|
775 | if nodelist is None: |
---|
776 | nodelist = G |
---|
777 | nlen = len(nodelist) |
---|
778 | if nlen == 0: |
---|
779 | raise nx.NetworkXError("Graph has no nodes or edges") |
---|
780 | |
---|
781 | if len(nodelist) != len(set(nodelist)): |
---|
782 | msg = "Ambiguous ordering: `nodelist` contained duplicates." |
---|
783 | raise nx.NetworkXError(msg) |
---|
784 | |
---|
785 | index = dict(zip(nodelist,range(nlen))) |
---|
786 | if G.number_of_edges() == 0: |
---|
787 | row,col,data=[],[],[] |
---|
788 | else: |
---|
789 | row,col,data=zip(*((index[u],index[v],d.get(weight,1)) |
---|
790 | for u,v,d in G.edges_iter(nodelist, data=True) |
---|
791 | if u in index and v in index)) |
---|
792 | if G.is_directed(): |
---|
793 | M = sparse.coo_matrix((data,(row,col)),shape=(nlen,nlen), dtype=dtype) |
---|
794 | else: |
---|
795 | # symmetrize matrix |
---|
796 | M = sparse.coo_matrix((data+data,(row+col,col+row)),shape=(nlen,nlen), |
---|
797 | dtype=dtype) |
---|
798 | try: |
---|
799 | return M.asformat(format) |
---|
800 | except AttributeError: |
---|
801 | raise nx.NetworkXError("Unknown sparse matrix format: %s"%format) |
---|
802 | |
---|
803 | def from_scipy_sparse_matrix(A,create_using=None): |
---|
804 | """Return a graph from scipy sparse matrix adjacency list. |
---|
805 | |
---|
806 | Parameters |
---|
807 | ---------- |
---|
808 | A : scipy sparse matrix |
---|
809 | An adjacency matrix representation of a graph |
---|
810 | |
---|
811 | create_using : NetworkX graph |
---|
812 | Use specified graph for result. The default is Graph() |
---|
813 | |
---|
814 | Examples |
---|
815 | -------- |
---|
816 | >>> import scipy.sparse |
---|
817 | >>> A=scipy.sparse.eye(2,2,1) |
---|
818 | >>> G=nx.from_scipy_sparse_matrix(A) |
---|
819 | |
---|
820 | """ |
---|
821 | G=_prep_create_using(create_using) |
---|
822 | |
---|
823 | # convert all formats to lil - not the most efficient way |
---|
824 | AA=A.tolil() |
---|
825 | n,m=AA.shape |
---|
826 | |
---|
827 | if n!=m: |
---|
828 | raise nx.NetworkXError(\ |
---|
829 | "Adjacency matrix is not square. nx,ny=%s"%(A.shape,)) |
---|
830 | G.add_nodes_from(range(n)) # make sure we get isolated nodes |
---|
831 | |
---|
832 | for i,row in enumerate(AA.rows): |
---|
833 | for pos,j in enumerate(row): |
---|
834 | G.add_edge(i,j,**{'weight':AA.data[i][pos]}) |
---|
835 | return G |
---|
836 | |
---|
837 | # fixture for nose tests |
---|
838 | def setup_module(module): |
---|
839 | from nose import SkipTest |
---|
840 | try: |
---|
841 | import numpy |
---|
842 | except: |
---|
843 | raise SkipTest("NumPy not available") |
---|
844 | try: |
---|
845 | import scipy |
---|
846 | except: |
---|
847 | raise SkipTest("SciPy not available") |
---|