Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Adjacency matrix and incidence matrix of graphs.
3"""
5import networkx as nx
7__all__ = ["incidence_matrix", "adjacency_matrix"]
10@nx._dispatchable(edge_attrs="weight")
11def incidence_matrix(
12 G, nodelist=None, edgelist=None, oriented=False, weight=None, *, dtype=None
13):
14 """Returns incidence matrix of G.
16 The incidence matrix assigns each row to a node and each column to an edge.
17 For a standard incidence matrix a 1 appears wherever a row's node is
18 incident on the column's edge. For an oriented incidence matrix each
19 edge is assigned an orientation (arbitrarily for undirected and aligning to
20 direction for directed). A -1 appears for the source (tail) of an edge and
21 1 for the destination (head) of the edge. The elements are zero otherwise.
23 Parameters
24 ----------
25 G : graph
26 A NetworkX graph
28 nodelist : list, optional (default= all nodes in G)
29 The rows are ordered according to the nodes in nodelist.
30 If nodelist is None, then the ordering is produced by G.nodes().
32 edgelist : list, optional (default= all edges in G)
33 The columns are ordered according to the edges in edgelist.
34 If edgelist is None, then the ordering is produced by G.edges().
36 oriented: bool, optional (default=False)
37 If True, matrix elements are +1 or -1 for the head or tail node
38 respectively of each edge. If False, +1 occurs at both nodes.
40 weight : string or None, optional (default=None)
41 The edge data key used to provide each value in the matrix.
42 If None, then each edge has weight 1. Edge weights, if used,
43 should be positive so that the orientation can provide the sign.
45 dtype : a NumPy dtype or None (default=None)
46 The dtype of the output sparse array. This type should be a compatible
47 type of the weight argument, eg. if weight would return a float this
48 argument should also be a float.
49 If None, then the default for SciPy is used.
51 Returns
52 -------
53 A : SciPy sparse array
54 The incidence matrix of G.
56 Notes
57 -----
58 For MultiGraph/MultiDiGraph, the edges in edgelist should be
59 (u,v,key) 3-tuples.
61 "Networks are the best discrete model for so many problems in
62 applied mathematics" [1]_.
64 References
65 ----------
66 .. [1] Gil Strang, Network applications: A = incidence matrix,
67 http://videolectures.net/mit18085f07_strang_lec03/
68 """
69 import scipy as sp
71 if nodelist is None:
72 nodelist = list(G)
73 if edgelist is None:
74 if G.is_multigraph():
75 edgelist = list(G.edges(keys=True))
76 else:
77 edgelist = list(G.edges())
78 A = sp.sparse.lil_array((len(nodelist), len(edgelist)), dtype=dtype)
79 node_index = {node: i for i, node in enumerate(nodelist)}
80 for ei, e in enumerate(edgelist):
81 (u, v) = e[:2]
82 if u == v:
83 continue # self loops give zero column
84 try:
85 ui = node_index[u]
86 vi = node_index[v]
87 except KeyError as err:
88 raise nx.NetworkXError(
89 f"node {u} or {v} in edgelist but not in nodelist"
90 ) from err
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")
108@nx._dispatchable(edge_attrs="weight")
109def adjacency_matrix(G, nodelist=None, dtype=None, weight="weight"):
110 """Returns adjacency matrix of `G`.
112 Parameters
113 ----------
114 G : graph
115 A NetworkX graph
117 nodelist : list, optional
118 The rows and columns are ordered according to the nodes in `nodelist`.
119 If ``nodelist=None`` (the default), then the ordering is produced by
120 ``G.nodes()``.
122 dtype : NumPy data-type, optional
123 The desired data-type for the array.
124 If `None`, then the NumPy default is used.
126 weight : string or None, optional (default='weight')
127 The edge data key used to provide each value in the matrix.
128 If None, then each edge has weight 1.
130 Returns
131 -------
132 A : SciPy sparse array
133 Adjacency matrix representation of G.
135 Notes
136 -----
137 For directed graphs, entry ``i, j`` corresponds to an edge from ``i`` to ``j``.
139 If you want a pure Python adjacency matrix representation try
140 :func:`~networkx.convert.to_dict_of_dicts` which will return a
141 dictionary-of-dictionaries format that can be addressed as a
142 sparse matrix.
144 For multigraphs with parallel edges the weights are summed.
145 See :func:`networkx.convert_matrix.to_numpy_array` for other options.
147 The convention used for self-loop edges in graphs is to assign the
148 diagonal matrix entry value to the edge weight attribute
149 (or the number 1 if the edge has no weight attribute). If the
150 alternate convention of doubling the edge weight is desired the
151 resulting SciPy sparse array can be modified as follows::
153 >>> G = nx.Graph([(1, 1)])
154 >>> A = nx.adjacency_matrix(G)
155 >>> A.toarray()
156 array([[1]])
157 >>> A.setdiag(A.diagonal() * 2)
158 >>> A.toarray()
159 array([[2]])
161 See Also
162 --------
163 to_numpy_array
164 to_scipy_sparse_array
165 to_dict_of_dicts
166 adjacency_spectrum
167 """
168 return nx.to_scipy_sparse_array(G, nodelist=nodelist, dtype=dtype, weight=weight)