source: networkx/networkx/convert.py @ 2216:a9622fe911ce

Revision 2216:a9622fe911ce, 26.3 KB checked in by Aric Hagberg <aric.hagberg@…>, 22 months ago (diff)

Preserver order in G.nodes() or given in nodelist when converting to scipy sparse matrix. Update docs to reflect use of COO matrix.
Addresses #737

Line 
1"""
2This module provides functions to convert
3NetworkX graphs to and from other formats.
4
5The preferred way of converting data to a NetworkX graph
6is through the graph constuctor.  The constructor calls
7the to_networkx_graph() function which attempts to guess the
8input type and convert it automatically.
9
10Examples
11--------
12
13Create 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
19or equivalently
20
21>>> D=nx.to_networkx_graph(a,create_using=nx.DiGraph())
22
23Create 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
29See Also
30--------
31nx_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
44import warnings
45import 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
55def _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
73def 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
184def convert_to_undirected(G):
185    """Return a new undirected representation of the graph G."""
186    return G.to_undirected()
187
188
189def convert_to_directed(G):
190    """Return a new directed representation of the graph G."""
191    return G.to_directed()
192
193
194def 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
218def 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
256def 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
295def 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
374def 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
391def 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
415def 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
531def 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
626def 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
706def 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
803def 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
838def 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")
Note: See TracBrowser for help on using the repository browser.