Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/linalg/attrmatrix.py: 9%
87 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2 Functions for constructing matrix-like objects from graph attributes.
3"""
4import networkx as nx
6__all__ = ["attr_matrix", "attr_sparse_matrix"]
9def _node_value(G, node_attr):
10 """Returns a function that returns a value from G.nodes[u].
12 We return a function expecting a node as its sole argument. Then, in the
13 simplest scenario, the returned function will return G.nodes[u][node_attr].
14 However, we also handle the case when `node_attr` is None or when it is a
15 function itself.
17 Parameters
18 ----------
19 G : graph
20 A NetworkX graph
22 node_attr : {None, str, callable}
23 Specification of how the value of the node attribute should be obtained
24 from the node attribute dictionary.
26 Returns
27 -------
28 value : function
29 A function expecting a node as its sole argument. The function will
30 returns a value from G.nodes[u] that depends on `edge_attr`.
32 """
33 if node_attr is None:
35 def value(u):
36 return u
38 elif not callable(node_attr):
39 # assume it is a key for the node attribute dictionary
40 def value(u):
41 return G.nodes[u][node_attr]
43 else:
44 # Advanced: Allow users to specify something else.
45 #
46 # For example,
47 # node_attr = lambda u: G.nodes[u].get('size', .5) * 3
48 #
49 value = node_attr
51 return value
54def _edge_value(G, edge_attr):
55 """Returns a function that returns a value from G[u][v].
57 Suppose there exists an edge between u and v. Then we return a function
58 expecting u and v as arguments. For Graph and DiGraph, G[u][v] is
59 the edge attribute dictionary, and the function (essentially) returns
60 G[u][v][edge_attr]. However, we also handle cases when `edge_attr` is None
61 and when it is a function itself. For MultiGraph and MultiDiGraph, G[u][v]
62 is a dictionary of all edges between u and v. In this case, the returned
63 function sums the value of `edge_attr` for every edge between u and v.
65 Parameters
66 ----------
67 G : graph
68 A NetworkX graph
70 edge_attr : {None, str, callable}
71 Specification of how the value of the edge attribute should be obtained
72 from the edge attribute dictionary, G[u][v]. For multigraphs, G[u][v]
73 is a dictionary of all the edges between u and v. This allows for
74 special treatment of multiedges.
76 Returns
77 -------
78 value : function
79 A function expecting two nodes as parameters. The nodes should
80 represent the from- and to- node of an edge. The function will
81 return a value from G[u][v] that depends on `edge_attr`.
83 """
85 if edge_attr is None:
86 # topological count of edges
88 if G.is_multigraph():
90 def value(u, v):
91 return len(G[u][v])
93 else:
95 def value(u, v):
96 return 1
98 elif not callable(edge_attr):
99 # assume it is a key for the edge attribute dictionary
101 if edge_attr == "weight":
102 # provide a default value
103 if G.is_multigraph():
105 def value(u, v):
106 return sum(d.get(edge_attr, 1) for d in G[u][v].values())
108 else:
110 def value(u, v):
111 return G[u][v].get(edge_attr, 1)
113 else:
114 # otherwise, the edge attribute MUST exist for each edge
115 if G.is_multigraph():
117 def value(u, v):
118 return sum(d[edge_attr] for d in G[u][v].values())
120 else:
122 def value(u, v):
123 return G[u][v][edge_attr]
125 else:
126 # Advanced: Allow users to specify something else.
127 #
128 # Alternative default value:
129 # edge_attr = lambda u,v: G[u][v].get('thickness', .5)
130 #
131 # Function on an attribute:
132 # edge_attr = lambda u,v: abs(G[u][v]['weight'])
133 #
134 # Handle Multi(Di)Graphs differently:
135 # edge_attr = lambda u,v: numpy.prod([d['size'] for d in G[u][v].values()])
136 #
137 # Ignore multiple edges
138 # edge_attr = lambda u,v: 1 if len(G[u][v]) else 0
139 #
140 value = edge_attr
142 return value
145@nx._dispatch(edge_attrs={"edge_attr": None}, node_attrs="node_attr")
146def attr_matrix(
147 G,
148 edge_attr=None,
149 node_attr=None,
150 normalized=False,
151 rc_order=None,
152 dtype=None,
153 order=None,
154):
155 """Returns the attribute matrix using attributes from `G` as a numpy array.
157 If only `G` is passed in, then the adjacency matrix is constructed.
159 Let A be a discrete set of values for the node attribute `node_attr`. Then
160 the elements of A represent the rows and columns of the constructed matrix.
161 Now, iterate through every edge e=(u,v) in `G` and consider the value
162 of the edge attribute `edge_attr`. If ua and va are the values of the
163 node attribute `node_attr` for u and v, respectively, then the value of
164 the edge attribute is added to the matrix element at (ua, va).
166 Parameters
167 ----------
168 G : graph
169 The NetworkX graph used to construct the attribute matrix.
171 edge_attr : str, optional
172 Each element of the matrix represents a running total of the
173 specified edge attribute for edges whose node attributes correspond
174 to the rows/cols of the matrix. The attribute must be present for
175 all edges in the graph. If no attribute is specified, then we
176 just count the number of edges whose node attributes correspond
177 to the matrix element.
179 node_attr : str, optional
180 Each row and column in the matrix represents a particular value
181 of the node attribute. The attribute must be present for all nodes
182 in the graph. Note, the values of this attribute should be reliably
183 hashable. So, float values are not recommended. If no attribute is
184 specified, then the rows and columns will be the nodes of the graph.
186 normalized : bool, optional
187 If True, then each row is normalized by the summation of its values.
189 rc_order : list, optional
190 A list of the node attribute values. This list specifies the ordering
191 of rows and columns of the array. If no ordering is provided, then
192 the ordering will be random (and also, a return value).
194 Other Parameters
195 ----------------
196 dtype : NumPy data-type, optional
197 A valid NumPy dtype used to initialize the array. Keep in mind certain
198 dtypes can yield unexpected results if the array is to be normalized.
199 The parameter is passed to numpy.zeros(). If unspecified, the NumPy
200 default is used.
202 order : {'C', 'F'}, optional
203 Whether to store multidimensional data in C- or Fortran-contiguous
204 (row- or column-wise) order in memory. This parameter is passed to
205 numpy.zeros(). If unspecified, the NumPy default is used.
207 Returns
208 -------
209 M : 2D NumPy ndarray
210 The attribute matrix.
212 ordering : list
213 If `rc_order` was specified, then only the attribute matrix is returned.
214 However, if `rc_order` was None, then the ordering used to construct
215 the matrix is returned as well.
217 Examples
218 --------
219 Construct an adjacency matrix:
221 >>> G = nx.Graph()
222 >>> G.add_edge(0, 1, thickness=1, weight=3)
223 >>> G.add_edge(0, 2, thickness=2)
224 >>> G.add_edge(1, 2, thickness=3)
225 >>> nx.attr_matrix(G, rc_order=[0, 1, 2])
226 array([[0., 1., 1.],
227 [1., 0., 1.],
228 [1., 1., 0.]])
230 Alternatively, we can obtain the matrix describing edge thickness.
232 >>> nx.attr_matrix(G, edge_attr="thickness", rc_order=[0, 1, 2])
233 array([[0., 1., 2.],
234 [1., 0., 3.],
235 [2., 3., 0.]])
237 We can also color the nodes and ask for the probability distribution over
238 all edges (u,v) describing:
240 Pr(v has color Y | u has color X)
242 >>> G.nodes[0]["color"] = "red"
243 >>> G.nodes[1]["color"] = "red"
244 >>> G.nodes[2]["color"] = "blue"
245 >>> rc = ["red", "blue"]
246 >>> nx.attr_matrix(G, node_attr="color", normalized=True, rc_order=rc)
247 array([[0.33333333, 0.66666667],
248 [1. , 0. ]])
250 For example, the above tells us that for all edges (u,v):
252 Pr( v is red | u is red) = 1/3
253 Pr( v is blue | u is red) = 2/3
255 Pr( v is red | u is blue) = 1
256 Pr( v is blue | u is blue) = 0
258 Finally, we can obtain the total weights listed by the node colors.
260 >>> nx.attr_matrix(G, edge_attr="weight", node_attr="color", rc_order=rc)
261 array([[3., 2.],
262 [2., 0.]])
264 Thus, the total weight over all edges (u,v) with u and v having colors:
266 (red, red) is 3 # the sole contribution is from edge (0,1)
267 (red, blue) is 2 # contributions from edges (0,2) and (1,2)
268 (blue, red) is 2 # same as (red, blue) since graph is undirected
269 (blue, blue) is 0 # there are no edges with blue endpoints
271 """
272 import numpy as np
274 edge_value = _edge_value(G, edge_attr)
275 node_value = _node_value(G, node_attr)
277 if rc_order is None:
278 ordering = list({node_value(n) for n in G})
279 else:
280 ordering = rc_order
282 N = len(ordering)
283 undirected = not G.is_directed()
284 index = dict(zip(ordering, range(N)))
285 M = np.zeros((N, N), dtype=dtype, order=order)
287 seen = set()
288 for u, nbrdict in G.adjacency():
289 for v in nbrdict:
290 # Obtain the node attribute values.
291 i, j = index[node_value(u)], index[node_value(v)]
292 if v not in seen:
293 M[i, j] += edge_value(u, v)
294 if undirected:
295 M[j, i] = M[i, j]
297 if undirected:
298 seen.add(u)
300 if normalized:
301 M /= M.sum(axis=1).reshape((N, 1))
303 if rc_order is None:
304 return M, ordering
305 else:
306 return M
309@nx._dispatch(edge_attrs={"edge_attr": None}, node_attrs="node_attr")
310def attr_sparse_matrix(
311 G, edge_attr=None, node_attr=None, normalized=False, rc_order=None, dtype=None
312):
313 """Returns a SciPy sparse array using attributes from G.
315 If only `G` is passed in, then the adjacency matrix is constructed.
317 Let A be a discrete set of values for the node attribute `node_attr`. Then
318 the elements of A represent the rows and columns of the constructed matrix.
319 Now, iterate through every edge e=(u,v) in `G` and consider the value
320 of the edge attribute `edge_attr`. If ua and va are the values of the
321 node attribute `node_attr` for u and v, respectively, then the value of
322 the edge attribute is added to the matrix element at (ua, va).
324 Parameters
325 ----------
326 G : graph
327 The NetworkX graph used to construct the NumPy matrix.
329 edge_attr : str, optional
330 Each element of the matrix represents a running total of the
331 specified edge attribute for edges whose node attributes correspond
332 to the rows/cols of the matrix. The attribute must be present for
333 all edges in the graph. If no attribute is specified, then we
334 just count the number of edges whose node attributes correspond
335 to the matrix element.
337 node_attr : str, optional
338 Each row and column in the matrix represents a particular value
339 of the node attribute. The attribute must be present for all nodes
340 in the graph. Note, the values of this attribute should be reliably
341 hashable. So, float values are not recommended. If no attribute is
342 specified, then the rows and columns will be the nodes of the graph.
344 normalized : bool, optional
345 If True, then each row is normalized by the summation of its values.
347 rc_order : list, optional
348 A list of the node attribute values. This list specifies the ordering
349 of rows and columns of the array. If no ordering is provided, then
350 the ordering will be random (and also, a return value).
352 Other Parameters
353 ----------------
354 dtype : NumPy data-type, optional
355 A valid NumPy dtype used to initialize the array. Keep in mind certain
356 dtypes can yield unexpected results if the array is to be normalized.
357 The parameter is passed to numpy.zeros(). If unspecified, the NumPy
358 default is used.
360 Returns
361 -------
362 M : SciPy sparse array
363 The attribute matrix.
365 ordering : list
366 If `rc_order` was specified, then only the matrix is returned.
367 However, if `rc_order` was None, then the ordering used to construct
368 the matrix is returned as well.
370 Examples
371 --------
372 Construct an adjacency matrix:
374 >>> G = nx.Graph()
375 >>> G.add_edge(0, 1, thickness=1, weight=3)
376 >>> G.add_edge(0, 2, thickness=2)
377 >>> G.add_edge(1, 2, thickness=3)
378 >>> M = nx.attr_sparse_matrix(G, rc_order=[0, 1, 2])
379 >>> M.toarray()
380 array([[0., 1., 1.],
381 [1., 0., 1.],
382 [1., 1., 0.]])
384 Alternatively, we can obtain the matrix describing edge thickness.
386 >>> M = nx.attr_sparse_matrix(G, edge_attr="thickness", rc_order=[0, 1, 2])
387 >>> M.toarray()
388 array([[0., 1., 2.],
389 [1., 0., 3.],
390 [2., 3., 0.]])
392 We can also color the nodes and ask for the probability distribution over
393 all edges (u,v) describing:
395 Pr(v has color Y | u has color X)
397 >>> G.nodes[0]["color"] = "red"
398 >>> G.nodes[1]["color"] = "red"
399 >>> G.nodes[2]["color"] = "blue"
400 >>> rc = ["red", "blue"]
401 >>> M = nx.attr_sparse_matrix(G, node_attr="color", normalized=True, rc_order=rc)
402 >>> M.toarray()
403 array([[0.33333333, 0.66666667],
404 [1. , 0. ]])
406 For example, the above tells us that for all edges (u,v):
408 Pr( v is red | u is red) = 1/3
409 Pr( v is blue | u is red) = 2/3
411 Pr( v is red | u is blue) = 1
412 Pr( v is blue | u is blue) = 0
414 Finally, we can obtain the total weights listed by the node colors.
416 >>> M = nx.attr_sparse_matrix(G, edge_attr="weight", node_attr="color", rc_order=rc)
417 >>> M.toarray()
418 array([[3., 2.],
419 [2., 0.]])
421 Thus, the total weight over all edges (u,v) with u and v having colors:
423 (red, red) is 3 # the sole contribution is from edge (0,1)
424 (red, blue) is 2 # contributions from edges (0,2) and (1,2)
425 (blue, red) is 2 # same as (red, blue) since graph is undirected
426 (blue, blue) is 0 # there are no edges with blue endpoints
428 """
429 import numpy as np
430 import scipy as sp
432 edge_value = _edge_value(G, edge_attr)
433 node_value = _node_value(G, node_attr)
435 if rc_order is None:
436 ordering = list({node_value(n) for n in G})
437 else:
438 ordering = rc_order
440 N = len(ordering)
441 undirected = not G.is_directed()
442 index = dict(zip(ordering, range(N)))
443 M = sp.sparse.lil_array((N, N), dtype=dtype)
445 seen = set()
446 for u, nbrdict in G.adjacency():
447 for v in nbrdict:
448 # Obtain the node attribute values.
449 i, j = index[node_value(u)], index[node_value(v)]
450 if v not in seen:
451 M[i, j] += edge_value(u, v)
452 if undirected:
453 M[j, i] = M[i, j]
455 if undirected:
456 seen.add(u)
458 if normalized:
459 M *= 1 / M.sum(axis=1)[:, np.newaxis] # in-place mult preserves sparse
461 if rc_order is None:
462 return M, ordering
463 else:
464 return M