Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/classes/reportviews.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 View Classes provide node, edge and degree "views" of a graph. | |
3 | |
4 Views for nodes, edges and degree are provided for all base graph classes. | |
5 A view means a read-only object that is quick to create, automatically | |
6 updated when the graph changes, and provides basic access like `n in V`, | |
7 `for n in V`, `V[n]` and sometimes set operations. | |
8 | |
9 The views are read-only iterable containers that are updated as the | |
10 graph is updated. As with dicts, the graph should not be updated | |
11 while iterating through the view. Views can be iterated multiple times. | |
12 | |
13 Edge and Node views also allow data attribute lookup. | |
14 The resulting attribute dict is writable as `G.edges[3, 4]['color']='red'` | |
15 Degree views allow lookup of degree values for single nodes. | |
16 Weighted degree is supported with the `weight` argument. | |
17 | |
18 NodeView | |
19 ======== | |
20 | |
21 `V = G.nodes` (or `V = G.nodes()`) allows `len(V)`, `n in V`, set | |
22 operations e.g. "G.nodes & H.nodes", and `dd = G.nodes[n]`, where | |
23 `dd` is the node data dict. Iteration is over the nodes by default. | |
24 | |
25 NodeDataView | |
26 ============ | |
27 | |
28 To iterate over (node, data) pairs, use arguments to `G.nodes()` | |
29 to create a DataView e.g. `DV = G.nodes(data='color', default='red')`. | |
30 The DataView iterates as `for n, color in DV` and allows | |
31 `(n, 'red') in DV`. Using `DV = G.nodes(data=True)`, the DataViews | |
32 use the full datadict in writeable form also allowing contain testing as | |
33 `(n, {'color': 'red'}) in VD`. DataViews allow set operations when | |
34 data attributes are hashable. | |
35 | |
36 DegreeView | |
37 ========== | |
38 | |
39 `V = G.degree` allows iteration over (node, degree) pairs as well | |
40 as lookup: `deg=V[n]`. There are many flavors of DegreeView | |
41 for In/Out/Directed/Multi. For Directed Graphs, `G.degree` | |
42 counts both in and out going edges. `G.out_degree` and | |
43 `G.in_degree` count only specific directions. | |
44 Weighted degree using edge data attributes is provide via | |
45 `V = G.degree(weight='attr_name')` where any string with the | |
46 attribute name can be used. `weight=None` is the default. | |
47 No set operations are implemented for degrees, use NodeView. | |
48 | |
49 The argument `nbunch` restricts iteration to nodes in nbunch. | |
50 The DegreeView can still lookup any node even if nbunch is specified. | |
51 | |
52 EdgeView | |
53 ======== | |
54 | |
55 `V = G.edges` or `V = G.edges()` allows iteration over edges as well as | |
56 `e in V`, set operations and edge data lookup `dd = G.edges[2, 3]`. | |
57 Iteration is over 2-tuples `(u, v)` for Graph/DiGraph. For multigraphs | |
58 edges 3-tuples `(u, v, key)` are the default but 2-tuples can be obtained | |
59 via `V = G.edges(keys=False)`. | |
60 | |
61 Set operations for directed graphs treat the edges as a set of 2-tuples. | |
62 For undirected graphs, 2-tuples are not a unique representation of edges. | |
63 So long as the set being compared to contains unique representations | |
64 of its edges, the set operations will act as expected. If the other | |
65 set contains both `(0, 1)` and `(1, 0)` however, the result of set | |
66 operations may contain both representations of the same edge. | |
67 | |
68 EdgeDataView | |
69 ============ | |
70 | |
71 Edge data can be reported using an EdgeDataView typically created | |
72 by calling an EdgeView: `DV = G.edges(data='weight', default=1)`. | |
73 The EdgeDataView allows iteration over edge tuples, membership checking | |
74 but no set operations. | |
75 | |
76 Iteration depends on `data` and `default` and for multigraph `keys` | |
77 If `data is False` (the default) then iterate over 2-tuples `(u, v)`. | |
78 If `data is True` iterate over 3-tuples `(u, v, datadict)`. | |
79 Otherwise iterate over `(u, v, datadict.get(data, default))`. | |
80 For Multigraphs, if `keys is True`, replace `u, v` with `u, v, key` | |
81 to create 3-tuples and 4-tuples. | |
82 | |
83 The argument `nbunch` restricts edges to those incident to nodes in nbunch. | |
84 """ | |
85 from collections.abc import Mapping, Set | |
86 | |
87 __all__ = [ | |
88 "NodeView", | |
89 "NodeDataView", | |
90 "EdgeView", | |
91 "OutEdgeView", | |
92 "InEdgeView", | |
93 "EdgeDataView", | |
94 "OutEdgeDataView", | |
95 "InEdgeDataView", | |
96 "MultiEdgeView", | |
97 "OutMultiEdgeView", | |
98 "InMultiEdgeView", | |
99 "MultiEdgeDataView", | |
100 "OutMultiEdgeDataView", | |
101 "InMultiEdgeDataView", | |
102 "DegreeView", | |
103 "DiDegreeView", | |
104 "InDegreeView", | |
105 "OutDegreeView", | |
106 "MultiDegreeView", | |
107 "DiMultiDegreeView", | |
108 "InMultiDegreeView", | |
109 "OutMultiDegreeView", | |
110 ] | |
111 | |
112 | |
113 # NodeViews | |
114 class NodeView(Mapping, Set): | |
115 """A NodeView class to act as G.nodes for a NetworkX Graph | |
116 | |
117 Set operations act on the nodes without considering data. | |
118 Iteration is over nodes. Node data can be looked up like a dict. | |
119 Use NodeDataView to iterate over node data or to specify a data | |
120 attribute for lookup. NodeDataView is created by calling the NodeView. | |
121 | |
122 Parameters | |
123 ---------- | |
124 graph : NetworkX graph-like class | |
125 | |
126 Examples | |
127 -------- | |
128 >>> G = nx.path_graph(3) | |
129 >>> NV = G.nodes() | |
130 >>> 2 in NV | |
131 True | |
132 >>> for n in NV: | |
133 ... print(n) | |
134 0 | |
135 1 | |
136 2 | |
137 >>> assert NV & {1, 2, 3} == {1, 2} | |
138 | |
139 >>> G.add_node(2, color="blue") | |
140 >>> NV[2] | |
141 {'color': 'blue'} | |
142 >>> G.add_node(8, color="red") | |
143 >>> NDV = G.nodes(data=True) | |
144 >>> (2, NV[2]) in NDV | |
145 True | |
146 >>> for n, dd in NDV: | |
147 ... print((n, dd.get("color", "aqua"))) | |
148 (0, 'aqua') | |
149 (1, 'aqua') | |
150 (2, 'blue') | |
151 (8, 'red') | |
152 >>> NDV[2] == NV[2] | |
153 True | |
154 | |
155 >>> NVdata = G.nodes(data="color", default="aqua") | |
156 >>> (2, NVdata[2]) in NVdata | |
157 True | |
158 >>> for n, dd in NVdata: | |
159 ... print((n, dd)) | |
160 (0, 'aqua') | |
161 (1, 'aqua') | |
162 (2, 'blue') | |
163 (8, 'red') | |
164 >>> NVdata[2] == NV[2] # NVdata gets 'color', NV gets datadict | |
165 False | |
166 """ | |
167 | |
168 __slots__ = ("_nodes",) | |
169 | |
170 def __getstate__(self): | |
171 return {"_nodes": self._nodes} | |
172 | |
173 def __setstate__(self, state): | |
174 self._nodes = state["_nodes"] | |
175 | |
176 def __init__(self, graph): | |
177 self._nodes = graph._node | |
178 | |
179 # Mapping methods | |
180 def __len__(self): | |
181 return len(self._nodes) | |
182 | |
183 def __iter__(self): | |
184 return iter(self._nodes) | |
185 | |
186 def __getitem__(self, n): | |
187 return self._nodes[n] | |
188 | |
189 # Set methods | |
190 def __contains__(self, n): | |
191 return n in self._nodes | |
192 | |
193 @classmethod | |
194 def _from_iterable(cls, it): | |
195 return set(it) | |
196 | |
197 # DataView method | |
198 def __call__(self, data=False, default=None): | |
199 if data is False: | |
200 return self | |
201 return NodeDataView(self._nodes, data, default) | |
202 | |
203 def data(self, data=True, default=None): | |
204 if data is False: | |
205 return self | |
206 return NodeDataView(self._nodes, data, default) | |
207 | |
208 def __str__(self): | |
209 return str(list(self)) | |
210 | |
211 def __repr__(self): | |
212 return f"{self.__class__.__name__}({tuple(self)})" | |
213 | |
214 | |
215 class NodeDataView(Set): | |
216 """A DataView class for nodes of a NetworkX Graph | |
217 | |
218 The main use for this class is to iterate through node-data pairs. | |
219 The data can be the entire data-dictionary for each node, or it | |
220 can be a specific attribute (with default) for each node. | |
221 Set operations are enabled with NodeDataView, but don't work in | |
222 cases where the data is not hashable. Use with caution. | |
223 Typically, set operations on nodes use NodeView, not NodeDataView. | |
224 That is, they use `G.nodes` instead of `G.nodes(data='foo')`. | |
225 | |
226 Parameters | |
227 ========== | |
228 graph : NetworkX graph-like class | |
229 data : bool or string (default=False) | |
230 default : object (default=None) | |
231 """ | |
232 | |
233 __slots__ = ("_nodes", "_data", "_default") | |
234 | |
235 def __getstate__(self): | |
236 return {"_nodes": self._nodes, "_data": self._data, "_default": self._default} | |
237 | |
238 def __setstate__(self, state): | |
239 self._nodes = state["_nodes"] | |
240 self._data = state["_data"] | |
241 self._default = state["_default"] | |
242 | |
243 def __init__(self, nodedict, data=False, default=None): | |
244 self._nodes = nodedict | |
245 self._data = data | |
246 self._default = default | |
247 | |
248 @classmethod | |
249 def _from_iterable(cls, it): | |
250 try: | |
251 return set(it) | |
252 except TypeError as err: | |
253 if "unhashable" in str(err): | |
254 msg = " : Could be b/c data=True or your values are unhashable" | |
255 raise TypeError(str(err) + msg) from err | |
256 raise | |
257 | |
258 def __len__(self): | |
259 return len(self._nodes) | |
260 | |
261 def __iter__(self): | |
262 data = self._data | |
263 if data is False: | |
264 return iter(self._nodes) | |
265 if data is True: | |
266 return iter(self._nodes.items()) | |
267 return ( | |
268 (n, dd[data] if data in dd else self._default) | |
269 for n, dd in self._nodes.items() | |
270 ) | |
271 | |
272 def __contains__(self, n): | |
273 try: | |
274 node_in = n in self._nodes | |
275 except TypeError: | |
276 n, d = n | |
277 return n in self._nodes and self[n] == d | |
278 if node_in is True: | |
279 return node_in | |
280 try: | |
281 n, d = n | |
282 except (TypeError, ValueError): | |
283 return False | |
284 return n in self._nodes and self[n] == d | |
285 | |
286 def __getitem__(self, n): | |
287 ddict = self._nodes[n] | |
288 data = self._data | |
289 if data is False or data is True: | |
290 return ddict | |
291 return ddict[data] if data in ddict else self._default | |
292 | |
293 def __str__(self): | |
294 return str(list(self)) | |
295 | |
296 def __repr__(self): | |
297 name = self.__class__.__name__ | |
298 if self._data is False: | |
299 return f"{name}({tuple(self)})" | |
300 if self._data is True: | |
301 return f"{name}({dict(self)})" | |
302 return f"{name}({dict(self)}, data={self._data!r})" | |
303 | |
304 | |
305 # DegreeViews | |
306 class DiDegreeView: | |
307 """A View class for degree of nodes in a NetworkX Graph | |
308 | |
309 The functionality is like dict.items() with (node, degree) pairs. | |
310 Additional functionality includes read-only lookup of node degree, | |
311 and calling with optional features nbunch (for only a subset of nodes) | |
312 and weight (use edge weights to compute degree). | |
313 | |
314 Parameters | |
315 ========== | |
316 graph : NetworkX graph-like class | |
317 nbunch : node, container of nodes, or None meaning all nodes (default=None) | |
318 weight : bool or string (default=None) | |
319 | |
320 Notes | |
321 ----- | |
322 DegreeView can still lookup any node even if nbunch is specified. | |
323 | |
324 Examples | |
325 -------- | |
326 >>> G = nx.path_graph(3) | |
327 >>> DV = G.degree() | |
328 >>> assert DV[2] == 1 | |
329 >>> assert sum(deg for n, deg in DV) == 4 | |
330 | |
331 >>> DVweight = G.degree(weight="span") | |
332 >>> G.add_edge(1, 2, span=34) | |
333 >>> DVweight[2] | |
334 34 | |
335 >>> DVweight[0] # default edge weight is 1 | |
336 1 | |
337 >>> sum(span for n, span in DVweight) # sum weighted degrees | |
338 70 | |
339 | |
340 >>> DVnbunch = G.degree(nbunch=(1, 2)) | |
341 >>> assert len(list(DVnbunch)) == 2 # iteration over nbunch only | |
342 """ | |
343 | |
344 def __init__(self, G, nbunch=None, weight=None): | |
345 self._graph = G | |
346 self._succ = G._succ if hasattr(G, "_succ") else G._adj | |
347 self._pred = G._pred if hasattr(G, "_pred") else G._adj | |
348 self._nodes = self._succ if nbunch is None else list(G.nbunch_iter(nbunch)) | |
349 self._weight = weight | |
350 | |
351 def __call__(self, nbunch=None, weight=None): | |
352 if nbunch is None: | |
353 if weight == self._weight: | |
354 return self | |
355 return self.__class__(self._graph, None, weight) | |
356 try: | |
357 if nbunch in self._nodes: | |
358 if weight == self._weight: | |
359 return self[nbunch] | |
360 return self.__class__(self._graph, None, weight)[nbunch] | |
361 except TypeError: | |
362 pass | |
363 return self.__class__(self._graph, nbunch, weight) | |
364 | |
365 def __getitem__(self, n): | |
366 weight = self._weight | |
367 succs = self._succ[n] | |
368 preds = self._pred[n] | |
369 if weight is None: | |
370 return len(succs) + len(preds) | |
371 return sum(dd.get(weight, 1) for dd in succs.values()) + sum( | |
372 dd.get(weight, 1) for dd in preds.values() | |
373 ) | |
374 | |
375 def __iter__(self): | |
376 weight = self._weight | |
377 if weight is None: | |
378 for n in self._nodes: | |
379 succs = self._succ[n] | |
380 preds = self._pred[n] | |
381 yield (n, len(succs) + len(preds)) | |
382 else: | |
383 for n in self._nodes: | |
384 succs = self._succ[n] | |
385 preds = self._pred[n] | |
386 deg = sum(dd.get(weight, 1) for dd in succs.values()) + sum( | |
387 dd.get(weight, 1) for dd in preds.values() | |
388 ) | |
389 yield (n, deg) | |
390 | |
391 def __len__(self): | |
392 return len(self._nodes) | |
393 | |
394 def __str__(self): | |
395 return str(list(self)) | |
396 | |
397 def __repr__(self): | |
398 return f"{self.__class__.__name__}({dict(self)})" | |
399 | |
400 | |
401 class DegreeView(DiDegreeView): | |
402 """A DegreeView class to act as G.degree for a NetworkX Graph | |
403 | |
404 Typical usage focuses on iteration over `(node, degree)` pairs. | |
405 The degree is by default the number of edges incident to the node. | |
406 Optional argument `weight` enables weighted degree using the edge | |
407 attribute named in the `weight` argument. Reporting and iteration | |
408 can also be restricted to a subset of nodes using `nbunch`. | |
409 | |
410 Additional functionality include node lookup so that `G.degree[n]` | |
411 reported the (possibly weighted) degree of node `n`. Calling the | |
412 view creates a view with different arguments `nbunch` or `weight`. | |
413 | |
414 Parameters | |
415 ========== | |
416 graph : NetworkX graph-like class | |
417 nbunch : node, container of nodes, or None meaning all nodes (default=None) | |
418 weight : string or None (default=None) | |
419 | |
420 Notes | |
421 ----- | |
422 DegreeView can still lookup any node even if nbunch is specified. | |
423 | |
424 Examples | |
425 -------- | |
426 >>> G = nx.path_graph(3) | |
427 >>> DV = G.degree() | |
428 >>> assert DV[2] == 1 | |
429 >>> assert G.degree[2] == 1 | |
430 >>> assert sum(deg for n, deg in DV) == 4 | |
431 | |
432 >>> DVweight = G.degree(weight="span") | |
433 >>> G.add_edge(1, 2, span=34) | |
434 >>> DVweight[2] | |
435 34 | |
436 >>> DVweight[0] # default edge weight is 1 | |
437 1 | |
438 >>> sum(span for n, span in DVweight) # sum weighted degrees | |
439 70 | |
440 | |
441 >>> DVnbunch = G.degree(nbunch=(1, 2)) | |
442 >>> assert len(list(DVnbunch)) == 2 # iteration over nbunch only | |
443 """ | |
444 | |
445 def __getitem__(self, n): | |
446 weight = self._weight | |
447 nbrs = self._succ[n] | |
448 if weight is None: | |
449 return len(nbrs) + (n in nbrs) | |
450 return sum(dd.get(weight, 1) for dd in nbrs.values()) + ( | |
451 n in nbrs and nbrs[n].get(weight, 1) | |
452 ) | |
453 | |
454 def __iter__(self): | |
455 weight = self._weight | |
456 if weight is None: | |
457 for n in self._nodes: | |
458 nbrs = self._succ[n] | |
459 yield (n, len(nbrs) + (n in nbrs)) | |
460 else: | |
461 for n in self._nodes: | |
462 nbrs = self._succ[n] | |
463 deg = sum(dd.get(weight, 1) for dd in nbrs.values()) + ( | |
464 n in nbrs and nbrs[n].get(weight, 1) | |
465 ) | |
466 yield (n, deg) | |
467 | |
468 | |
469 class OutDegreeView(DiDegreeView): | |
470 """A DegreeView class to report out_degree for a DiGraph; See DegreeView""" | |
471 | |
472 def __getitem__(self, n): | |
473 weight = self._weight | |
474 nbrs = self._succ[n] | |
475 if self._weight is None: | |
476 return len(nbrs) | |
477 return sum(dd.get(self._weight, 1) for dd in nbrs.values()) | |
478 | |
479 def __iter__(self): | |
480 weight = self._weight | |
481 if weight is None: | |
482 for n in self._nodes: | |
483 succs = self._succ[n] | |
484 yield (n, len(succs)) | |
485 else: | |
486 for n in self._nodes: | |
487 succs = self._succ[n] | |
488 deg = sum(dd.get(weight, 1) for dd in succs.values()) | |
489 yield (n, deg) | |
490 | |
491 | |
492 class InDegreeView(DiDegreeView): | |
493 """A DegreeView class to report in_degree for a DiGraph; See DegreeView""" | |
494 | |
495 def __getitem__(self, n): | |
496 weight = self._weight | |
497 nbrs = self._pred[n] | |
498 if weight is None: | |
499 return len(nbrs) | |
500 return sum(dd.get(weight, 1) for dd in nbrs.values()) | |
501 | |
502 def __iter__(self): | |
503 weight = self._weight | |
504 if weight is None: | |
505 for n in self._nodes: | |
506 preds = self._pred[n] | |
507 yield (n, len(preds)) | |
508 else: | |
509 for n in self._nodes: | |
510 preds = self._pred[n] | |
511 deg = sum(dd.get(weight, 1) for dd in preds.values()) | |
512 yield (n, deg) | |
513 | |
514 | |
515 class MultiDegreeView(DiDegreeView): | |
516 """A DegreeView class for undirected multigraphs; See DegreeView""" | |
517 | |
518 def __getitem__(self, n): | |
519 weight = self._weight | |
520 nbrs = self._succ[n] | |
521 if weight is None: | |
522 return sum(len(keys) for keys in nbrs.values()) + ( | |
523 n in nbrs and len(nbrs[n]) | |
524 ) | |
525 # edge weighted graph - degree is sum of nbr edge weights | |
526 deg = sum( | |
527 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values() | |
528 ) | |
529 if n in nbrs: | |
530 deg += sum(d.get(weight, 1) for d in nbrs[n].values()) | |
531 return deg | |
532 | |
533 def __iter__(self): | |
534 weight = self._weight | |
535 if weight is None: | |
536 for n in self._nodes: | |
537 nbrs = self._succ[n] | |
538 deg = sum(len(keys) for keys in nbrs.values()) + ( | |
539 n in nbrs and len(nbrs[n]) | |
540 ) | |
541 yield (n, deg) | |
542 else: | |
543 for n in self._nodes: | |
544 nbrs = self._succ[n] | |
545 deg = sum( | |
546 d.get(weight, 1) | |
547 for key_dict in nbrs.values() | |
548 for d in key_dict.values() | |
549 ) | |
550 if n in nbrs: | |
551 deg += sum(d.get(weight, 1) for d in nbrs[n].values()) | |
552 yield (n, deg) | |
553 | |
554 | |
555 class DiMultiDegreeView(DiDegreeView): | |
556 """A DegreeView class for MultiDiGraph; See DegreeView""" | |
557 | |
558 def __getitem__(self, n): | |
559 weight = self._weight | |
560 succs = self._succ[n] | |
561 preds = self._pred[n] | |
562 if weight is None: | |
563 return sum(len(keys) for keys in succs.values()) + sum( | |
564 len(keys) for keys in preds.values() | |
565 ) | |
566 # edge weighted graph - degree is sum of nbr edge weights | |
567 deg = sum( | |
568 d.get(weight, 1) for key_dict in succs.values() for d in key_dict.values() | |
569 ) + sum( | |
570 d.get(weight, 1) for key_dict in preds.values() for d in key_dict.values() | |
571 ) | |
572 return deg | |
573 | |
574 def __iter__(self): | |
575 weight = self._weight | |
576 if weight is None: | |
577 for n in self._nodes: | |
578 succs = self._succ[n] | |
579 preds = self._pred[n] | |
580 deg = sum(len(keys) for keys in succs.values()) + sum( | |
581 len(keys) for keys in preds.values() | |
582 ) | |
583 yield (n, deg) | |
584 else: | |
585 for n in self._nodes: | |
586 succs = self._succ[n] | |
587 preds = self._pred[n] | |
588 deg = sum( | |
589 d.get(weight, 1) | |
590 for key_dict in succs.values() | |
591 for d in key_dict.values() | |
592 ) + sum( | |
593 d.get(weight, 1) | |
594 for key_dict in preds.values() | |
595 for d in key_dict.values() | |
596 ) | |
597 yield (n, deg) | |
598 | |
599 | |
600 class InMultiDegreeView(DiDegreeView): | |
601 """A DegreeView class for inward degree of MultiDiGraph; See DegreeView""" | |
602 | |
603 def __getitem__(self, n): | |
604 weight = self._weight | |
605 nbrs = self._pred[n] | |
606 if weight is None: | |
607 return sum(len(data) for data in nbrs.values()) | |
608 # edge weighted graph - degree is sum of nbr edge weights | |
609 return sum( | |
610 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values() | |
611 ) | |
612 | |
613 def __iter__(self): | |
614 weight = self._weight | |
615 if weight is None: | |
616 for n in self._nodes: | |
617 nbrs = self._pred[n] | |
618 deg = sum(len(data) for data in nbrs.values()) | |
619 yield (n, deg) | |
620 else: | |
621 for n in self._nodes: | |
622 nbrs = self._pred[n] | |
623 deg = sum( | |
624 d.get(weight, 1) | |
625 for key_dict in nbrs.values() | |
626 for d in key_dict.values() | |
627 ) | |
628 yield (n, deg) | |
629 | |
630 | |
631 class OutMultiDegreeView(DiDegreeView): | |
632 """A DegreeView class for outward degree of MultiDiGraph; See DegreeView""" | |
633 | |
634 def __getitem__(self, n): | |
635 weight = self._weight | |
636 nbrs = self._succ[n] | |
637 if weight is None: | |
638 return sum(len(data) for data in nbrs.values()) | |
639 # edge weighted graph - degree is sum of nbr edge weights | |
640 return sum( | |
641 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values() | |
642 ) | |
643 | |
644 def __iter__(self): | |
645 weight = self._weight | |
646 if weight is None: | |
647 for n in self._nodes: | |
648 nbrs = self._succ[n] | |
649 deg = sum(len(data) for data in nbrs.values()) | |
650 yield (n, deg) | |
651 else: | |
652 for n in self._nodes: | |
653 nbrs = self._succ[n] | |
654 deg = sum( | |
655 d.get(weight, 1) | |
656 for key_dict in nbrs.values() | |
657 for d in key_dict.values() | |
658 ) | |
659 yield (n, deg) | |
660 | |
661 | |
662 # EdgeDataViews | |
663 class OutEdgeDataView: | |
664 """EdgeDataView for outward edges of DiGraph; See EdgeDataView""" | |
665 | |
666 __slots__ = ( | |
667 "_viewer", | |
668 "_nbunch", | |
669 "_data", | |
670 "_default", | |
671 "_adjdict", | |
672 "_nodes_nbrs", | |
673 "_report", | |
674 ) | |
675 | |
676 def __getstate__(self): | |
677 return { | |
678 "viewer": self._viewer, | |
679 "nbunch": self._nbunch, | |
680 "data": self._data, | |
681 "default": self._default, | |
682 } | |
683 | |
684 def __setstate__(self, state): | |
685 self.__init__(**state) | |
686 | |
687 def __init__(self, viewer, nbunch=None, data=False, default=None): | |
688 self._viewer = viewer | |
689 adjdict = self._adjdict = viewer._adjdict | |
690 if nbunch is None: | |
691 self._nodes_nbrs = adjdict.items | |
692 else: | |
693 # dict retains order of nodes but acts like a set | |
694 nbunch = dict.fromkeys(viewer._graph.nbunch_iter(nbunch)) | |
695 self._nodes_nbrs = lambda: [(n, adjdict[n]) for n in nbunch] | |
696 self._nbunch = nbunch | |
697 self._data = data | |
698 self._default = default | |
699 # Set _report based on data and default | |
700 if data is True: | |
701 self._report = lambda n, nbr, dd: (n, nbr, dd) | |
702 elif data is False: | |
703 self._report = lambda n, nbr, dd: (n, nbr) | |
704 else: # data is attribute name | |
705 self._report = ( | |
706 lambda n, nbr, dd: (n, nbr, dd[data]) | |
707 if data in dd | |
708 else (n, nbr, default) | |
709 ) | |
710 | |
711 def __len__(self): | |
712 return sum(len(nbrs) for n, nbrs in self._nodes_nbrs()) | |
713 | |
714 def __iter__(self): | |
715 return ( | |
716 self._report(n, nbr, dd) | |
717 for n, nbrs in self._nodes_nbrs() | |
718 for nbr, dd in nbrs.items() | |
719 ) | |
720 | |
721 def __contains__(self, e): | |
722 u, v = e[:2] | |
723 if self._nbunch is not None and u not in self._nbunch: | |
724 return False # this edge doesn't start in nbunch | |
725 try: | |
726 ddict = self._adjdict[u][v] | |
727 except KeyError: | |
728 return False | |
729 return e == self._report(u, v, ddict) | |
730 | |
731 def __str__(self): | |
732 return str(list(self)) | |
733 | |
734 def __repr__(self): | |
735 return f"{self.__class__.__name__}({list(self)})" | |
736 | |
737 | |
738 class EdgeDataView(OutEdgeDataView): | |
739 """A EdgeDataView class for edges of Graph | |
740 | |
741 This view is primarily used to iterate over the edges reporting | |
742 edges as node-tuples with edge data optionally reported. The | |
743 argument `nbunch` allows restriction to edges incident to nodes | |
744 in that container/singleton. The default (nbunch=None) | |
745 reports all edges. The arguments `data` and `default` control | |
746 what edge data is reported. The default `data is False` reports | |
747 only node-tuples for each edge. If `data is True` the entire edge | |
748 data dict is returned. Otherwise `data` is assumed to hold the name | |
749 of the edge attribute to report with default `default` if that | |
750 edge attribute is not present. | |
751 | |
752 Parameters | |
753 ---------- | |
754 nbunch : container of nodes, node or None (default None) | |
755 data : False, True or string (default False) | |
756 default : default value (default None) | |
757 | |
758 Examples | |
759 -------- | |
760 >>> G = nx.path_graph(3) | |
761 >>> G.add_edge(1, 2, foo="bar") | |
762 >>> list(G.edges(data="foo", default="biz")) | |
763 [(0, 1, 'biz'), (1, 2, 'bar')] | |
764 >>> assert (0, 1, "biz") in G.edges(data="foo", default="biz") | |
765 """ | |
766 | |
767 __slots__ = () | |
768 | |
769 def __len__(self): | |
770 return sum(1 for e in self) | |
771 | |
772 def __iter__(self): | |
773 seen = {} | |
774 for n, nbrs in self._nodes_nbrs(): | |
775 for nbr, dd in nbrs.items(): | |
776 if nbr not in seen: | |
777 yield self._report(n, nbr, dd) | |
778 seen[n] = 1 | |
779 del seen | |
780 | |
781 def __contains__(self, e): | |
782 u, v = e[:2] | |
783 if self._nbunch is not None and u not in self._nbunch and v not in self._nbunch: | |
784 return False # this edge doesn't start and it doesn't end in nbunch | |
785 try: | |
786 ddict = self._adjdict[u][v] | |
787 except KeyError: | |
788 return False | |
789 return e == self._report(u, v, ddict) | |
790 | |
791 | |
792 class InEdgeDataView(OutEdgeDataView): | |
793 """An EdgeDataView class for outward edges of DiGraph; See EdgeDataView""" | |
794 | |
795 __slots__ = () | |
796 | |
797 def __iter__(self): | |
798 return ( | |
799 self._report(nbr, n, dd) | |
800 for n, nbrs in self._nodes_nbrs() | |
801 for nbr, dd in nbrs.items() | |
802 ) | |
803 | |
804 def __contains__(self, e): | |
805 u, v = e[:2] | |
806 if self._nbunch is not None and v not in self._nbunch: | |
807 return False # this edge doesn't end in nbunch | |
808 try: | |
809 ddict = self._adjdict[v][u] | |
810 except KeyError: | |
811 return False | |
812 return e == self._report(u, v, ddict) | |
813 | |
814 | |
815 class OutMultiEdgeDataView(OutEdgeDataView): | |
816 """An EdgeDataView for outward edges of MultiDiGraph; See EdgeDataView""" | |
817 | |
818 __slots__ = ("keys",) | |
819 | |
820 def __getstate__(self): | |
821 return { | |
822 "viewer": self._viewer, | |
823 "nbunch": self._nbunch, | |
824 "keys": self.keys, | |
825 "data": self._data, | |
826 "default": self._default, | |
827 } | |
828 | |
829 def __setstate__(self, state): | |
830 self.__init__(**state) | |
831 | |
832 def __init__(self, viewer, nbunch=None, data=False, keys=False, default=None): | |
833 self._viewer = viewer | |
834 adjdict = self._adjdict = viewer._adjdict | |
835 self.keys = keys | |
836 if nbunch is None: | |
837 self._nodes_nbrs = adjdict.items | |
838 else: | |
839 # dict retains order of nodes but acts like a set | |
840 nbunch = dict.fromkeys(viewer._graph.nbunch_iter(nbunch)) | |
841 self._nodes_nbrs = lambda: [(n, adjdict[n]) for n in nbunch] | |
842 self._nbunch = nbunch | |
843 self._data = data | |
844 self._default = default | |
845 # Set _report based on data and default | |
846 if data is True: | |
847 if keys is True: | |
848 self._report = lambda n, nbr, k, dd: (n, nbr, k, dd) | |
849 else: | |
850 self._report = lambda n, nbr, k, dd: (n, nbr, dd) | |
851 elif data is False: | |
852 if keys is True: | |
853 self._report = lambda n, nbr, k, dd: (n, nbr, k) | |
854 else: | |
855 self._report = lambda n, nbr, k, dd: (n, nbr) | |
856 else: # data is attribute name | |
857 if keys is True: | |
858 self._report = ( | |
859 lambda n, nbr, k, dd: (n, nbr, k, dd[data]) | |
860 if data in dd | |
861 else (n, nbr, k, default) | |
862 ) | |
863 else: | |
864 self._report = ( | |
865 lambda n, nbr, k, dd: (n, nbr, dd[data]) | |
866 if data in dd | |
867 else (n, nbr, default) | |
868 ) | |
869 | |
870 def __len__(self): | |
871 return sum(1 for e in self) | |
872 | |
873 def __iter__(self): | |
874 return ( | |
875 self._report(n, nbr, k, dd) | |
876 for n, nbrs in self._nodes_nbrs() | |
877 for nbr, kd in nbrs.items() | |
878 for k, dd in kd.items() | |
879 ) | |
880 | |
881 def __contains__(self, e): | |
882 u, v = e[:2] | |
883 if self._nbunch is not None and u not in self._nbunch: | |
884 return False # this edge doesn't start in nbunch | |
885 try: | |
886 kdict = self._adjdict[u][v] | |
887 except KeyError: | |
888 return False | |
889 if self.keys is True: | |
890 k = e[2] | |
891 try: | |
892 dd = kdict[k] | |
893 except KeyError: | |
894 return False | |
895 return e == self._report(u, v, k, dd) | |
896 for k, dd in kdict.items(): | |
897 if e == self._report(u, v, k, dd): | |
898 return True | |
899 return False | |
900 | |
901 | |
902 class MultiEdgeDataView(OutMultiEdgeDataView): | |
903 """An EdgeDataView class for edges of MultiGraph; See EdgeDataView""" | |
904 | |
905 __slots__ = () | |
906 | |
907 def __iter__(self): | |
908 seen = {} | |
909 for n, nbrs in self._nodes_nbrs(): | |
910 for nbr, kd in nbrs.items(): | |
911 if nbr not in seen: | |
912 for k, dd in kd.items(): | |
913 yield self._report(n, nbr, k, dd) | |
914 seen[n] = 1 | |
915 del seen | |
916 | |
917 def __contains__(self, e): | |
918 u, v = e[:2] | |
919 if self._nbunch is not None and u not in self._nbunch and v not in self._nbunch: | |
920 return False # this edge doesn't start and doesn't end in nbunch | |
921 try: | |
922 kdict = self._adjdict[u][v] | |
923 except KeyError: | |
924 try: | |
925 kdict = self._adjdict[v][u] | |
926 except KeyError: | |
927 return False | |
928 if self.keys is True: | |
929 k = e[2] | |
930 try: | |
931 dd = kdict[k] | |
932 except KeyError: | |
933 return False | |
934 return e == self._report(u, v, k, dd) | |
935 for k, dd in kdict.items(): | |
936 if e == self._report(u, v, k, dd): | |
937 return True | |
938 return False | |
939 | |
940 | |
941 class InMultiEdgeDataView(OutMultiEdgeDataView): | |
942 """An EdgeDataView for inward edges of MultiDiGraph; See EdgeDataView""" | |
943 | |
944 __slots__ = () | |
945 | |
946 def __iter__(self): | |
947 return ( | |
948 self._report(nbr, n, k, dd) | |
949 for n, nbrs in self._nodes_nbrs() | |
950 for nbr, kd in nbrs.items() | |
951 for k, dd in kd.items() | |
952 ) | |
953 | |
954 def __contains__(self, e): | |
955 u, v = e[:2] | |
956 if self._nbunch is not None and v not in self._nbunch: | |
957 return False # this edge doesn't end in nbunch | |
958 try: | |
959 kdict = self._adjdict[v][u] | |
960 except KeyError: | |
961 return False | |
962 if self.keys is True: | |
963 k = e[2] | |
964 dd = kdict[k] | |
965 return e == self._report(u, v, k, dd) | |
966 for k, dd in kdict.items(): | |
967 if e == self._report(u, v, k, dd): | |
968 return True | |
969 return False | |
970 | |
971 | |
972 # EdgeViews have set operations and no data reported | |
973 class OutEdgeView(Set, Mapping): | |
974 """A EdgeView class for outward edges of a DiGraph""" | |
975 | |
976 __slots__ = ("_adjdict", "_graph", "_nodes_nbrs") | |
977 | |
978 def __getstate__(self): | |
979 return {"_graph": self._graph} | |
980 | |
981 def __setstate__(self, state): | |
982 self._graph = G = state["_graph"] | |
983 self._adjdict = G._succ if hasattr(G, "succ") else G._adj | |
984 self._nodes_nbrs = self._adjdict.items | |
985 | |
986 @classmethod | |
987 def _from_iterable(cls, it): | |
988 return set(it) | |
989 | |
990 dataview = OutEdgeDataView | |
991 | |
992 def __init__(self, G): | |
993 self._graph = G | |
994 self._adjdict = G._succ if hasattr(G, "succ") else G._adj | |
995 self._nodes_nbrs = self._adjdict.items | |
996 | |
997 # Set methods | |
998 def __len__(self): | |
999 return sum(len(nbrs) for n, nbrs in self._nodes_nbrs()) | |
1000 | |
1001 def __iter__(self): | |
1002 for n, nbrs in self._nodes_nbrs(): | |
1003 for nbr in nbrs: | |
1004 yield (n, nbr) | |
1005 | |
1006 def __contains__(self, e): | |
1007 try: | |
1008 u, v = e | |
1009 return v in self._adjdict[u] | |
1010 except KeyError: | |
1011 return False | |
1012 | |
1013 # Mapping Methods | |
1014 def __getitem__(self, e): | |
1015 u, v = e | |
1016 return self._adjdict[u][v] | |
1017 | |
1018 # EdgeDataView methods | |
1019 def __call__(self, nbunch=None, data=False, default=None): | |
1020 if nbunch is None and data is False: | |
1021 return self | |
1022 return self.dataview(self, nbunch, data, default) | |
1023 | |
1024 def data(self, data=True, default=None, nbunch=None): | |
1025 if nbunch is None and data is False: | |
1026 return self | |
1027 return self.dataview(self, nbunch, data, default) | |
1028 | |
1029 # String Methods | |
1030 def __str__(self): | |
1031 return str(list(self)) | |
1032 | |
1033 def __repr__(self): | |
1034 return f"{self.__class__.__name__}({list(self)})" | |
1035 | |
1036 | |
1037 class EdgeView(OutEdgeView): | |
1038 """A EdgeView class for edges of a Graph | |
1039 | |
1040 This densely packed View allows iteration over edges, data lookup | |
1041 like a dict and set operations on edges represented by node-tuples. | |
1042 In addition, edge data can be controlled by calling this object | |
1043 possibly creating an EdgeDataView. Typically edges are iterated over | |
1044 and reported as `(u, v)` node tuples or `(u, v, key)` node/key tuples | |
1045 for multigraphs. Those edge representations can also be using to | |
1046 lookup the data dict for any edge. Set operations also are available | |
1047 where those tuples are the elements of the set. | |
1048 Calling this object with optional arguments `data`, `default` and `keys` | |
1049 controls the form of the tuple (see EdgeDataView). Optional argument | |
1050 `nbunch` allows restriction to edges only involving certain nodes. | |
1051 | |
1052 If `data is False` (the default) then iterate over 2-tuples `(u, v)`. | |
1053 If `data is True` iterate over 3-tuples `(u, v, datadict)`. | |
1054 Otherwise iterate over `(u, v, datadict.get(data, default))`. | |
1055 For Multigraphs, if `keys is True`, replace `u, v` with `u, v, key` above. | |
1056 | |
1057 Parameters | |
1058 ========== | |
1059 graph : NetworkX graph-like class | |
1060 nbunch : (default= all nodes in graph) only report edges with these nodes | |
1061 keys : (only for MultiGraph. default=False) report edge key in tuple | |
1062 data : bool or string (default=False) see above | |
1063 default : object (default=None) | |
1064 | |
1065 Examples | |
1066 ======== | |
1067 >>> G = nx.path_graph(4) | |
1068 >>> EV = G.edges() | |
1069 >>> (2, 3) in EV | |
1070 True | |
1071 >>> for u, v in EV: | |
1072 ... print((u, v)) | |
1073 (0, 1) | |
1074 (1, 2) | |
1075 (2, 3) | |
1076 >>> assert EV & {(1, 2), (3, 4)} == {(1, 2)} | |
1077 | |
1078 >>> EVdata = G.edges(data="color", default="aqua") | |
1079 >>> G.add_edge(2, 3, color="blue") | |
1080 >>> assert (2, 3, "blue") in EVdata | |
1081 >>> for u, v, c in EVdata: | |
1082 ... print(f"({u}, {v}) has color: {c}") | |
1083 (0, 1) has color: aqua | |
1084 (1, 2) has color: aqua | |
1085 (2, 3) has color: blue | |
1086 | |
1087 >>> EVnbunch = G.edges(nbunch=2) | |
1088 >>> assert (2, 3) in EVnbunch | |
1089 >>> assert (0, 1) not in EVnbunch | |
1090 >>> for u, v in EVnbunch: | |
1091 ... assert u == 2 or v == 2 | |
1092 | |
1093 >>> MG = nx.path_graph(4, create_using=nx.MultiGraph) | |
1094 >>> EVmulti = MG.edges(keys=True) | |
1095 >>> (2, 3, 0) in EVmulti | |
1096 True | |
1097 >>> (2, 3) in EVmulti # 2-tuples work even when keys is True | |
1098 True | |
1099 >>> key = MG.add_edge(2, 3) | |
1100 >>> for u, v, k in EVmulti: | |
1101 ... print((u, v, k)) | |
1102 (0, 1, 0) | |
1103 (1, 2, 0) | |
1104 (2, 3, 0) | |
1105 (2, 3, 1) | |
1106 """ | |
1107 | |
1108 __slots__ = () | |
1109 | |
1110 dataview = EdgeDataView | |
1111 | |
1112 def __len__(self): | |
1113 num_nbrs = (len(nbrs) + (n in nbrs) for n, nbrs in self._nodes_nbrs()) | |
1114 return sum(num_nbrs) // 2 | |
1115 | |
1116 def __iter__(self): | |
1117 seen = {} | |
1118 for n, nbrs in self._nodes_nbrs(): | |
1119 for nbr in list(nbrs): | |
1120 if nbr not in seen: | |
1121 yield (n, nbr) | |
1122 seen[n] = 1 | |
1123 del seen | |
1124 | |
1125 def __contains__(self, e): | |
1126 try: | |
1127 u, v = e[:2] | |
1128 return v in self._adjdict[u] or u in self._adjdict[v] | |
1129 except (KeyError, ValueError): | |
1130 return False | |
1131 | |
1132 | |
1133 class InEdgeView(OutEdgeView): | |
1134 """A EdgeView class for inward edges of a DiGraph""" | |
1135 | |
1136 __slots__ = () | |
1137 | |
1138 def __setstate__(self, state): | |
1139 self._graph = G = state["_graph"] | |
1140 self._adjdict = G._pred if hasattr(G, "pred") else G._adj | |
1141 self._nodes_nbrs = self._adjdict.items | |
1142 | |
1143 dataview = InEdgeDataView | |
1144 | |
1145 def __init__(self, G): | |
1146 self._graph = G | |
1147 self._adjdict = G._pred if hasattr(G, "pred") else G._adj | |
1148 self._nodes_nbrs = self._adjdict.items | |
1149 | |
1150 def __iter__(self): | |
1151 for n, nbrs in self._nodes_nbrs(): | |
1152 for nbr in nbrs: | |
1153 yield (nbr, n) | |
1154 | |
1155 def __contains__(self, e): | |
1156 try: | |
1157 u, v = e | |
1158 return u in self._adjdict[v] | |
1159 except KeyError: | |
1160 return False | |
1161 | |
1162 def __getitem__(self, e): | |
1163 u, v = e | |
1164 return self._adjdict[v][u] | |
1165 | |
1166 | |
1167 class OutMultiEdgeView(OutEdgeView): | |
1168 """A EdgeView class for outward edges of a MultiDiGraph""" | |
1169 | |
1170 __slots__ = () | |
1171 | |
1172 dataview = OutMultiEdgeDataView | |
1173 | |
1174 def __len__(self): | |
1175 return sum( | |
1176 len(kdict) for n, nbrs in self._nodes_nbrs() for nbr, kdict in nbrs.items() | |
1177 ) | |
1178 | |
1179 def __iter__(self): | |
1180 for n, nbrs in self._nodes_nbrs(): | |
1181 for nbr, kdict in nbrs.items(): | |
1182 for key in kdict: | |
1183 yield (n, nbr, key) | |
1184 | |
1185 def __contains__(self, e): | |
1186 N = len(e) | |
1187 if N == 3: | |
1188 u, v, k = e | |
1189 elif N == 2: | |
1190 u, v = e | |
1191 k = 0 | |
1192 else: | |
1193 raise ValueError("MultiEdge must have length 2 or 3") | |
1194 try: | |
1195 return k in self._adjdict[u][v] | |
1196 except KeyError: | |
1197 return False | |
1198 | |
1199 def __getitem__(self, e): | |
1200 u, v, k = e | |
1201 return self._adjdict[u][v][k] | |
1202 | |
1203 def __call__(self, nbunch=None, data=False, keys=False, default=None): | |
1204 if nbunch is None and data is False and keys is True: | |
1205 return self | |
1206 return self.dataview(self, nbunch, data, keys, default) | |
1207 | |
1208 def data(self, data=True, keys=False, default=None, nbunch=None): | |
1209 if nbunch is None and data is False and keys is True: | |
1210 return self | |
1211 return self.dataview(self, nbunch, data, keys, default) | |
1212 | |
1213 | |
1214 class MultiEdgeView(OutMultiEdgeView): | |
1215 """A EdgeView class for edges of a MultiGraph""" | |
1216 | |
1217 __slots__ = () | |
1218 | |
1219 dataview = MultiEdgeDataView | |
1220 | |
1221 def __len__(self): | |
1222 return sum(1 for e in self) | |
1223 | |
1224 def __iter__(self): | |
1225 seen = {} | |
1226 for n, nbrs in self._nodes_nbrs(): | |
1227 for nbr, kd in nbrs.items(): | |
1228 if nbr not in seen: | |
1229 for k, dd in kd.items(): | |
1230 yield (n, nbr, k) | |
1231 seen[n] = 1 | |
1232 del seen | |
1233 | |
1234 | |
1235 class InMultiEdgeView(OutMultiEdgeView): | |
1236 """A EdgeView class for inward edges of a MultiDiGraph""" | |
1237 | |
1238 __slots__ = () | |
1239 | |
1240 def __setstate__(self, state): | |
1241 self._graph = G = state["_graph"] | |
1242 self._adjdict = G._pred if hasattr(G, "pred") else G._adj | |
1243 self._nodes_nbrs = self._adjdict.items | |
1244 | |
1245 dataview = InMultiEdgeDataView | |
1246 | |
1247 def __init__(self, G): | |
1248 self._graph = G | |
1249 self._adjdict = G._pred if hasattr(G, "pred") else G._adj | |
1250 self._nodes_nbrs = self._adjdict.items | |
1251 | |
1252 def __iter__(self): | |
1253 for n, nbrs in self._nodes_nbrs(): | |
1254 for nbr, kdict in nbrs.items(): | |
1255 for key in kdict: | |
1256 yield (nbr, n, key) | |
1257 | |
1258 def __contains__(self, e): | |
1259 N = len(e) | |
1260 if N == 3: | |
1261 u, v, k = e | |
1262 elif N == 2: | |
1263 u, v = e | |
1264 k = 0 | |
1265 else: | |
1266 raise ValueError("MultiEdge must have length 2 or 3") | |
1267 try: | |
1268 return k in self._adjdict[v][u] | |
1269 except KeyError: | |
1270 return False | |
1271 | |
1272 def __getitem__(self, e): | |
1273 u, v, k = e | |
1274 return self._adjdict[v][u][k] |