Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / linalg / graphmatrix.py @ 5cef0f13

History | View | Annotate | Download (5.48 KB)

1
"""
2
Adjacency matrix and incidence matrix of graphs.
3
"""
4
#    Copyright (C) 2004-2019 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
import networkx as nx
11
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
12
                        'Pieter Swart (swart@lanl.gov)',
13
                        'Dan Schult(dschult@colgate.edu)'])
14

    
15
__all__ = ['incidence_matrix',
16
           'adj_matrix', 'adjacency_matrix',
17
           ]
18

    
19

    
20
def incidence_matrix(G, nodelist=None, edgelist=None,
21
                     oriented=False, weight=None):
22
    """Returns incidence matrix of G.
23

24
    The incidence matrix assigns each row to a node and each column to an edge.
25
    For a standard incidence matrix a 1 appears wherever a row's node is
26
    incident on the column's edge.  For an oriented incidence matrix each
27
    edge is assigned an orientation (arbitrarily for undirected and aligning to
28
    direction for directed).  A -1 appears for the tail of an edge and 1
29
    for the head of the edge.  The elements are zero otherwise.
30

31
    Parameters
32
    ----------
33
    G : graph
34
       A NetworkX graph
35

36
    nodelist : list, optional   (default= all nodes in G)
37
       The rows are ordered according to the nodes in nodelist.
38
       If nodelist is None, then the ordering is produced by G.nodes().
39

40
    edgelist : list, optional (default= all edges in G)
41
       The columns are ordered according to the edges in edgelist.
42
       If edgelist is None, then the ordering is produced by G.edges().
43

44
    oriented: bool, optional (default=False)
45
       If True, matrix elements are +1 or -1 for the head or tail node
46
       respectively of each edge.  If False, +1 occurs at both nodes.
47

48
    weight : string or None, optional (default=None)
49
       The edge data key used to provide each value in the matrix.
50
       If None, then each edge has weight 1.  Edge weights, if used,
51
       should be positive so that the orientation can provide the sign.
52

53
    Returns
54
    -------
55
    A : SciPy sparse matrix
56
      The incidence matrix of G.
57

58
    Notes
59
    -----
60
    For MultiGraph/MultiDiGraph, the edges in edgelist should be
61
    (u,v,key) 3-tuples.
62

63
    "Networks are the best discrete model for so many problems in
64
    applied mathematics" [1]_.
65

66
    References
67
    ----------
68
    .. [1] Gil Strang, Network applications: A = incidence matrix,
69
       http://academicearth.org/lectures/network-applications-incidence-matrix
70
    """
71
    import scipy.sparse
72
    if nodelist is None:
73
        nodelist = list(G)
74
    if edgelist is None:
75
        if G.is_multigraph():
76
            edgelist = list(G.edges(keys=True))
77
        else:
78
            edgelist = list(G.edges())
79
    A = scipy.sparse.lil_matrix((len(nodelist), len(edgelist)))
80
    node_index = dict((node, i) for i, node in enumerate(nodelist))
81
    for ei, e in enumerate(edgelist):
82
        (u, v) = e[:2]
83
        if u == v:
84
            continue  # self loops give zero column
85
        try:
86
            ui = node_index[u]
87
            vi = node_index[v]
88
        except KeyError:
89
            raise nx.NetworkXError('node %s or %s in edgelist '
90
                                   'but not in nodelist' % (u, v))
91
        if weight is None:
92
            wt = 1
93
        else:
94
            if G.is_multigraph():
95
                ekey = e[2]
96
                wt = G[u][v][ekey].get(weight, 1)
97
            else:
98
                wt = G[u][v].get(weight, 1)
99
        if oriented:
100
            A[ui, ei] = -wt
101
            A[vi, ei] = wt
102
        else:
103
            A[ui, ei] = wt
104
            A[vi, ei] = wt
105
    return A.asformat('csc')
106

    
107

    
108
def adjacency_matrix(G, nodelist=None, weight='weight'):
109
    """Returns adjacency matrix of G.
110

111
    Parameters
112
    ----------
113
    G : graph
114
       A NetworkX graph
115

116
    nodelist : list, optional
117
       The rows and columns are ordered according to the nodes in nodelist.
118
       If nodelist is None, then the ordering is produced by G.nodes().
119

120
    weight : string or None, optional (default='weight')
121
       The edge data key used to provide each value in the matrix.
122
       If None, then each edge has weight 1.
123

124
    Returns
125
    -------
126
    A : SciPy sparse matrix
127
      Adjacency matrix representation of G.
128

129
    Notes
130
    -----
131
    For directed graphs, entry i,j corresponds to an edge from i to j.
132

133
    If you want a pure Python adjacency matrix representation try
134
    networkx.convert.to_dict_of_dicts which will return a
135
    dictionary-of-dictionaries format that can be addressed as a
136
    sparse matrix.
137

138
    For MultiGraph/MultiDiGraph with parallel edges the weights are summed.
139
    See to_numpy_matrix for other options.
140

141
    The convention used for self-loop edges in graphs is to assign the
142
    diagonal matrix entry value to the edge weight attribute
143
    (or the number 1 if the edge has no weight attribute).  If the
144
    alternate convention of doubling the edge weight is desired the
145
    resulting Scipy sparse matrix can be modified as follows:
146

147
    >>> import scipy as sp
148
    >>> G = nx.Graph([(1,1)])
149
    >>> A = nx.adjacency_matrix(G)
150
    >>> print(A.todense())
151
    [[1]]
152
    >>> A.setdiag(A.diagonal()*2)
153
    >>> print(A.todense())
154
    [[2]]
155

156
    See Also
157
    --------
158
    to_numpy_matrix
159
    to_scipy_sparse_matrix
160
    to_dict_of_dicts
161
    adjacency_spectrum
162
    """
163
    return nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight)
164

    
165

    
166
adj_matrix = adjacency_matrix
167

    
168
# fixture for nose tests
169

    
170

    
171
def setup_module(module):
172
    from nose import SkipTest
173
    try:
174
        import scipy
175
    except:
176
        raise SkipTest("SciPy not available")