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"""
2View Classes provide node, edge and degree "views" of a graph.
4Views for nodes, edges and degree are provided for all base graph classes.
5A view means a read-only object that is quick to create, automatically
6updated when the graph changes, and provides basic access like `n in V`,
7`for n in V`, `V[n]` and sometimes set operations.
9The views are read-only iterable containers that are updated as the
10graph is updated. As with dicts, the graph should not be updated
11while iterating through the view. Views can be iterated multiple times.
13Edge and Node views also allow data attribute lookup.
14The resulting attribute dict is writable as `G.edges[3, 4]['color']='red'`
15Degree views allow lookup of degree values for single nodes.
16Weighted degree is supported with the `weight` argument.
18NodeView
19========
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.
25NodeDataView
26============
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.
36DegreeView
37==========
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.
49 The argument `nbunch` restricts iteration to nodes in nbunch.
50 The DegreeView can still lookup any node even if nbunch is specified.
52EdgeView
53========
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)`.
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.
68EdgeDataView
69============
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.
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.
83 The argument `nbunch` restricts edges to those incident to nodes in nbunch.
84"""
86from abc import ABC
87from collections.abc import Mapping, Set
89import networkx as nx
91__all__ = [
92 "NodeView",
93 "NodeDataView",
94 "EdgeView",
95 "OutEdgeView",
96 "InEdgeView",
97 "EdgeDataView",
98 "OutEdgeDataView",
99 "InEdgeDataView",
100 "MultiEdgeView",
101 "OutMultiEdgeView",
102 "InMultiEdgeView",
103 "MultiEdgeDataView",
104 "OutMultiEdgeDataView",
105 "InMultiEdgeDataView",
106 "DegreeView",
107 "DiDegreeView",
108 "InDegreeView",
109 "OutDegreeView",
110 "MultiDegreeView",
111 "DiMultiDegreeView",
112 "InMultiDegreeView",
113 "OutMultiDegreeView",
114]
117# NodeViews
118class NodeView(Mapping, Set):
119 """A NodeView class to act as G.nodes for a NetworkX Graph
121 Set operations act on the nodes without considering data.
122 Iteration is over nodes. Node data can be looked up like a dict.
123 Use NodeDataView to iterate over node data or to specify a data
124 attribute for lookup. NodeDataView is created by calling the NodeView.
126 Parameters
127 ----------
128 graph : NetworkX graph-like class
130 Examples
131 --------
132 >>> G = nx.path_graph(3)
133 >>> NV = G.nodes()
134 >>> 2 in NV
135 True
136 >>> for n in NV:
137 ... print(n)
138 0
139 1
140 2
141 >>> assert NV & {1, 2, 3} == {1, 2}
143 >>> G.add_node(2, color="blue")
144 >>> NV[2]
145 {'color': 'blue'}
146 >>> G.add_node(8, color="red")
147 >>> NDV = G.nodes(data=True)
148 >>> (2, NV[2]) in NDV
149 True
150 >>> for n, dd in NDV:
151 ... print((n, dd.get("color", "aqua")))
152 (0, 'aqua')
153 (1, 'aqua')
154 (2, 'blue')
155 (8, 'red')
156 >>> NDV[2] == NV[2]
157 True
159 >>> NVdata = G.nodes(data="color", default="aqua")
160 >>> (2, NVdata[2]) in NVdata
161 True
162 >>> for n, dd in NVdata:
163 ... print((n, dd))
164 (0, 'aqua')
165 (1, 'aqua')
166 (2, 'blue')
167 (8, 'red')
168 >>> NVdata[2] == NV[2] # NVdata gets 'color', NV gets datadict
169 False
170 """
172 __slots__ = ("_nodes",)
174 def __getstate__(self):
175 return {"_nodes": self._nodes}
177 def __setstate__(self, state):
178 self._nodes = state["_nodes"]
180 def __init__(self, graph):
181 self._nodes = graph._node
183 # Mapping methods
184 def __len__(self):
185 return len(self._nodes)
187 def __iter__(self):
188 return iter(self._nodes)
190 def __getitem__(self, n):
191 if isinstance(n, slice):
192 raise nx.NetworkXError(
193 f"{type(self).__name__} does not support slicing, "
194 f"try list(G.nodes)[{n.start}:{n.stop}:{n.step}]"
195 )
196 return self._nodes[n]
198 # Set methods
199 def __contains__(self, n):
200 return n in self._nodes
202 @classmethod
203 def _from_iterable(cls, it):
204 return set(it)
206 # DataView method
207 def __call__(self, data=False, default=None):
208 if data is False:
209 return self
210 return NodeDataView(self._nodes, data, default)
212 def data(self, data=True, default=None):
213 """
214 Return a read-only view of node data.
216 Parameters
217 ----------
218 data : bool or node data key, default=True
219 If ``data=True`` (the default), return a `NodeDataView` object that
220 maps each node to *all* of its attributes. `data` may also be an
221 arbitrary key, in which case the `NodeDataView` maps each node to
222 the value for the keyed attribute. In this case, if a node does
223 not have the `data` attribute, the `default` value is used.
224 default : object, default=None
225 The value used when a node does not have a specific attribute.
227 Returns
228 -------
229 NodeDataView
230 The layout of the returned NodeDataView depends on the value of the
231 `data` parameter.
233 Notes
234 -----
235 If ``data=False``, returns a `NodeView` object without data.
237 See Also
238 --------
239 NodeDataView
241 Examples
242 --------
243 >>> G = nx.Graph()
244 >>> G.add_nodes_from(
245 ... [
246 ... (0, {"color": "red", "weight": 10}),
247 ... (1, {"color": "blue"}),
248 ... (2, {"color": "yellow", "weight": 2}),
249 ... ]
250 ... )
252 Accessing node data with ``data=True`` (the default) returns a
253 NodeDataView mapping each node to all of its attributes:
255 >>> G.nodes.data()
256 NodeDataView({0: {'color': 'red', 'weight': 10}, 1: {'color': 'blue'}, 2: {'color': 'yellow', 'weight': 2}})
258 If `data` represents a key in the node attribute dict, a NodeDataView mapping
259 the nodes to the value for that specific key is returned:
261 >>> G.nodes.data("color")
262 NodeDataView({0: 'red', 1: 'blue', 2: 'yellow'}, data='color')
264 If a specific key is not found in an attribute dict, the value specified
265 by `default` is returned:
267 >>> G.nodes.data("weight", default=-999)
268 NodeDataView({0: 10, 1: -999, 2: 2}, data='weight')
270 Note that there is no check that the `data` key is in any of the
271 node attribute dictionaries:
273 >>> G.nodes.data("height")
274 NodeDataView({0: None, 1: None, 2: None}, data='height')
275 """
276 if data is False:
277 return self
278 return NodeDataView(self._nodes, data, default)
280 def __str__(self):
281 return str(list(self))
283 def __repr__(self):
284 return f"{self.__class__.__name__}({tuple(self)})"
287class NodeDataView(Set):
288 """A DataView class for nodes of a NetworkX Graph
290 The main use for this class is to iterate through node-data pairs.
291 The data can be the entire data-dictionary for each node, or it
292 can be a specific attribute (with default) for each node.
293 Set operations are enabled with NodeDataView, but don't work in
294 cases where the data is not hashable. Use with caution.
295 Typically, set operations on nodes use NodeView, not NodeDataView.
296 That is, they use `G.nodes` instead of `G.nodes(data='foo')`.
298 Parameters
299 ==========
300 graph : NetworkX graph-like class
301 data : bool or string (default=False)
302 default : object (default=None)
303 """
305 __slots__ = ("_nodes", "_data", "_default")
307 def __getstate__(self):
308 return {"_nodes": self._nodes, "_data": self._data, "_default": self._default}
310 def __setstate__(self, state):
311 self._nodes = state["_nodes"]
312 self._data = state["_data"]
313 self._default = state["_default"]
315 def __init__(self, nodedict, data=False, default=None):
316 self._nodes = nodedict
317 self._data = data
318 self._default = default
320 @classmethod
321 def _from_iterable(cls, it):
322 try:
323 return set(it)
324 except TypeError as err:
325 if "unhashable" in str(err):
326 msg = " : Could be b/c data=True or your values are unhashable"
327 raise TypeError(str(err) + msg) from err
328 raise
330 def __len__(self):
331 return len(self._nodes)
333 def __iter__(self):
334 data = self._data
335 if data is False:
336 return iter(self._nodes)
337 if data is True:
338 return iter(self._nodes.items())
339 return (
340 (n, dd[data] if data in dd else self._default)
341 for n, dd in self._nodes.items()
342 )
344 def __contains__(self, n):
345 try:
346 node_in = n in self._nodes
347 except TypeError:
348 n, d = n
349 return n in self._nodes and self[n] == d
350 if node_in is True:
351 return node_in
352 try:
353 n, d = n
354 except (TypeError, ValueError):
355 return False
356 return n in self._nodes and self[n] == d
358 def __getitem__(self, n):
359 if isinstance(n, slice):
360 raise nx.NetworkXError(
361 f"{type(self).__name__} does not support slicing, "
362 f"try list(G.nodes.data())[{n.start}:{n.stop}:{n.step}]"
363 )
364 ddict = self._nodes[n]
365 data = self._data
366 if data is False or data is True:
367 return ddict
368 return ddict[data] if data in ddict else self._default
370 def __str__(self):
371 return str(list(self))
373 def __repr__(self):
374 name = self.__class__.__name__
375 if self._data is False:
376 return f"{name}({tuple(self)})"
377 if self._data is True:
378 return f"{name}({dict(self)})"
379 return f"{name}({dict(self)}, data={self._data!r})"
382# DegreeViews
383class DiDegreeView:
384 """A View class for degree of nodes in a NetworkX Graph
386 The functionality is like dict.items() with (node, degree) pairs.
387 Additional functionality includes read-only lookup of node degree,
388 and calling with optional features nbunch (for only a subset of nodes)
389 and weight (use edge weights to compute degree).
391 Parameters
392 ==========
393 graph : NetworkX graph-like class
394 nbunch : node, container of nodes, or None meaning all nodes (default=None)
395 weight : bool or string (default=None)
397 Notes
398 -----
399 DegreeView can still lookup any node even if nbunch is specified.
401 Examples
402 --------
403 >>> G = nx.path_graph(3)
404 >>> DV = G.degree()
405 >>> assert DV[2] == 1
406 >>> assert sum(deg for n, deg in DV) == 4
408 >>> DVweight = G.degree(weight="span")
409 >>> G.add_edge(1, 2, span=34)
410 >>> DVweight[2]
411 34
412 >>> DVweight[0] # default edge weight is 1
413 1
414 >>> sum(span for n, span in DVweight) # sum weighted degrees
415 70
417 >>> DVnbunch = G.degree(nbunch=(1, 2))
418 >>> assert len(list(DVnbunch)) == 2 # iteration over nbunch only
419 """
421 def __init__(self, G, nbunch=None, weight=None):
422 self._graph = G
423 self._succ = G._succ if hasattr(G, "_succ") else G._adj
424 self._pred = G._pred if hasattr(G, "_pred") else G._adj
425 self._nodes = self._succ if nbunch is None else list(G.nbunch_iter(nbunch))
426 self._weight = weight
428 def __call__(self, nbunch=None, weight=None):
429 if nbunch is None:
430 if weight == self._weight:
431 return self
432 return self.__class__(self._graph, None, weight)
433 try:
434 if nbunch in self._nodes:
435 if weight == self._weight:
436 return self[nbunch]
437 return self.__class__(self._graph, None, weight)[nbunch]
438 except TypeError:
439 pass
440 return self.__class__(self._graph, nbunch, weight)
442 def __getitem__(self, n):
443 weight = self._weight
444 succs = self._succ[n]
445 preds = self._pred[n]
446 if weight is None:
447 return len(succs) + len(preds)
448 return sum(dd.get(weight, 1) for dd in succs.values()) + sum(
449 dd.get(weight, 1) for dd in preds.values()
450 )
452 def __iter__(self):
453 weight = self._weight
454 if weight is None:
455 for n in self._nodes:
456 succs = self._succ[n]
457 preds = self._pred[n]
458 yield (n, len(succs) + len(preds))
459 else:
460 for n in self._nodes:
461 succs = self._succ[n]
462 preds = self._pred[n]
463 deg = sum(dd.get(weight, 1) for dd in succs.values()) + sum(
464 dd.get(weight, 1) for dd in preds.values()
465 )
466 yield (n, deg)
468 def __len__(self):
469 return len(self._nodes)
471 def __str__(self):
472 return str(list(self))
474 def __repr__(self):
475 return f"{self.__class__.__name__}({dict(self)})"
478class DegreeView(DiDegreeView):
479 """A DegreeView class to act as G.degree for a NetworkX Graph
481 Typical usage focuses on iteration over `(node, degree)` pairs.
482 The degree is by default the number of edges incident to the node.
483 Optional argument `weight` enables weighted degree using the edge
484 attribute named in the `weight` argument. Reporting and iteration
485 can also be restricted to a subset of nodes using `nbunch`.
487 Additional functionality include node lookup so that `G.degree[n]`
488 reported the (possibly weighted) degree of node `n`. Calling the
489 view creates a view with different arguments `nbunch` or `weight`.
491 Parameters
492 ==========
493 graph : NetworkX graph-like class
494 nbunch : node, container of nodes, or None meaning all nodes (default=None)
495 weight : string or None (default=None)
497 Notes
498 -----
499 DegreeView can still lookup any node even if nbunch is specified.
501 Examples
502 --------
503 >>> G = nx.path_graph(3)
504 >>> DV = G.degree()
505 >>> assert DV[2] == 1
506 >>> assert G.degree[2] == 1
507 >>> assert sum(deg for n, deg in DV) == 4
509 >>> DVweight = G.degree(weight="span")
510 >>> G.add_edge(1, 2, span=34)
511 >>> DVweight[2]
512 34
513 >>> DVweight[0] # default edge weight is 1
514 1
515 >>> sum(span for n, span in DVweight) # sum weighted degrees
516 70
518 >>> DVnbunch = G.degree(nbunch=(1, 2))
519 >>> assert len(list(DVnbunch)) == 2 # iteration over nbunch only
520 """
522 def __getitem__(self, n):
523 weight = self._weight
524 nbrs = self._succ[n]
525 if weight is None:
526 return len(nbrs) + (n in nbrs)
527 return sum(dd.get(weight, 1) for dd in nbrs.values()) + (
528 n in nbrs and nbrs[n].get(weight, 1)
529 )
531 def __iter__(self):
532 weight = self._weight
533 if weight is None:
534 for n in self._nodes:
535 nbrs = self._succ[n]
536 yield (n, len(nbrs) + (n in nbrs))
537 else:
538 for n in self._nodes:
539 nbrs = self._succ[n]
540 deg = sum(dd.get(weight, 1) for dd in nbrs.values()) + (
541 n in nbrs and nbrs[n].get(weight, 1)
542 )
543 yield (n, deg)
546class OutDegreeView(DiDegreeView):
547 """A DegreeView class to report out_degree for a DiGraph; See DegreeView"""
549 def __getitem__(self, n):
550 weight = self._weight
551 nbrs = self._succ[n]
552 if self._weight is None:
553 return len(nbrs)
554 return sum(dd.get(self._weight, 1) for dd in nbrs.values())
556 def __iter__(self):
557 weight = self._weight
558 if weight is None:
559 for n in self._nodes:
560 succs = self._succ[n]
561 yield (n, len(succs))
562 else:
563 for n in self._nodes:
564 succs = self._succ[n]
565 deg = sum(dd.get(weight, 1) for dd in succs.values())
566 yield (n, deg)
569class InDegreeView(DiDegreeView):
570 """A DegreeView class to report in_degree for a DiGraph; See DegreeView"""
572 def __getitem__(self, n):
573 weight = self._weight
574 nbrs = self._pred[n]
575 if weight is None:
576 return len(nbrs)
577 return sum(dd.get(weight, 1) for dd in nbrs.values())
579 def __iter__(self):
580 weight = self._weight
581 if weight is None:
582 for n in self._nodes:
583 preds = self._pred[n]
584 yield (n, len(preds))
585 else:
586 for n in self._nodes:
587 preds = self._pred[n]
588 deg = sum(dd.get(weight, 1) for dd in preds.values())
589 yield (n, deg)
592class MultiDegreeView(DiDegreeView):
593 """A DegreeView class for undirected multigraphs; See DegreeView"""
595 def __getitem__(self, n):
596 weight = self._weight
597 nbrs = self._succ[n]
598 if weight is None:
599 return sum(len(keys) for keys in nbrs.values()) + (
600 n in nbrs and len(nbrs[n])
601 )
602 # edge weighted graph - degree is sum of nbr edge weights
603 deg = sum(
604 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values()
605 )
606 if n in nbrs:
607 deg += sum(d.get(weight, 1) for d in nbrs[n].values())
608 return deg
610 def __iter__(self):
611 weight = self._weight
612 if weight is None:
613 for n in self._nodes:
614 nbrs = self._succ[n]
615 deg = sum(len(keys) for keys in nbrs.values()) + (
616 n in nbrs and len(nbrs[n])
617 )
618 yield (n, deg)
619 else:
620 for n in self._nodes:
621 nbrs = self._succ[n]
622 deg = sum(
623 d.get(weight, 1)
624 for key_dict in nbrs.values()
625 for d in key_dict.values()
626 )
627 if n in nbrs:
628 deg += sum(d.get(weight, 1) for d in nbrs[n].values())
629 yield (n, deg)
632class DiMultiDegreeView(DiDegreeView):
633 """A DegreeView class for MultiDiGraph; See DegreeView"""
635 def __getitem__(self, n):
636 weight = self._weight
637 succs = self._succ[n]
638 preds = self._pred[n]
639 if weight is None:
640 return sum(len(keys) for keys in succs.values()) + sum(
641 len(keys) for keys in preds.values()
642 )
643 # edge weighted graph - degree is sum of nbr edge weights
644 deg = sum(
645 d.get(weight, 1) for key_dict in succs.values() for d in key_dict.values()
646 ) + sum(
647 d.get(weight, 1) for key_dict in preds.values() for d in key_dict.values()
648 )
649 return deg
651 def __iter__(self):
652 weight = self._weight
653 if weight is None:
654 for n in self._nodes:
655 succs = self._succ[n]
656 preds = self._pred[n]
657 deg = sum(len(keys) for keys in succs.values()) + sum(
658 len(keys) for keys in preds.values()
659 )
660 yield (n, deg)
661 else:
662 for n in self._nodes:
663 succs = self._succ[n]
664 preds = self._pred[n]
665 deg = sum(
666 d.get(weight, 1)
667 for key_dict in succs.values()
668 for d in key_dict.values()
669 ) + sum(
670 d.get(weight, 1)
671 for key_dict in preds.values()
672 for d in key_dict.values()
673 )
674 yield (n, deg)
677class InMultiDegreeView(DiDegreeView):
678 """A DegreeView class for inward degree of MultiDiGraph; See DegreeView"""
680 def __getitem__(self, n):
681 weight = self._weight
682 nbrs = self._pred[n]
683 if weight is None:
684 return sum(len(data) for data in nbrs.values())
685 # edge weighted graph - degree is sum of nbr edge weights
686 return sum(
687 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values()
688 )
690 def __iter__(self):
691 weight = self._weight
692 if weight is None:
693 for n in self._nodes:
694 nbrs = self._pred[n]
695 deg = sum(len(data) for data in nbrs.values())
696 yield (n, deg)
697 else:
698 for n in self._nodes:
699 nbrs = self._pred[n]
700 deg = sum(
701 d.get(weight, 1)
702 for key_dict in nbrs.values()
703 for d in key_dict.values()
704 )
705 yield (n, deg)
708class OutMultiDegreeView(DiDegreeView):
709 """A DegreeView class for outward degree of MultiDiGraph; See DegreeView"""
711 def __getitem__(self, n):
712 weight = self._weight
713 nbrs = self._succ[n]
714 if weight is None:
715 return sum(len(data) for data in nbrs.values())
716 # edge weighted graph - degree is sum of nbr edge weights
717 return sum(
718 d.get(weight, 1) for key_dict in nbrs.values() for d in key_dict.values()
719 )
721 def __iter__(self):
722 weight = self._weight
723 if weight is None:
724 for n in self._nodes:
725 nbrs = self._succ[n]
726 deg = sum(len(data) for data in nbrs.values())
727 yield (n, deg)
728 else:
729 for n in self._nodes:
730 nbrs = self._succ[n]
731 deg = sum(
732 d.get(weight, 1)
733 for key_dict in nbrs.values()
734 for d in key_dict.values()
735 )
736 yield (n, deg)
739# A base class for all edge views. Ensures all edge view and edge data view
740# objects/classes are captured by `isinstance(obj, EdgeViewABC)` and
741# `issubclass(cls, EdgeViewABC)` respectively
742class EdgeViewABC(ABC):
743 pass
746# EdgeDataViews
747class OutEdgeDataView(EdgeViewABC):
748 """EdgeDataView for outward edges of DiGraph; See EdgeDataView"""
750 __slots__ = (
751 "_viewer",
752 "_nbunch",
753 "_data",
754 "_default",
755 "_adjdict",
756 "_nodes_nbrs",
757 "_report",
758 )
760 def __getstate__(self):
761 return {
762 "viewer": self._viewer,
763 "nbunch": self._nbunch,
764 "data": self._data,
765 "default": self._default,
766 }
768 def __setstate__(self, state):
769 self.__init__(**state)
771 def __init__(self, viewer, nbunch=None, data=False, *, default=None):
772 self._viewer = viewer
773 adjdict = self._adjdict = viewer._adjdict
774 if nbunch is None:
775 self._nodes_nbrs = adjdict.items
776 else:
777 # dict retains order of nodes but acts like a set
778 nbunch = dict.fromkeys(viewer._graph.nbunch_iter(nbunch))
779 self._nodes_nbrs = lambda: [(n, adjdict[n]) for n in nbunch]
780 self._nbunch = nbunch
781 self._data = data
782 self._default = default
783 # Set _report based on data and default
784 if data is True:
785 self._report = lambda n, nbr, dd: (n, nbr, dd)
786 elif data is False:
787 self._report = lambda n, nbr, dd: (n, nbr)
788 else: # data is attribute name
789 self._report = (
790 lambda n, nbr, dd: (n, nbr, dd[data])
791 if data in dd
792 else (n, nbr, default)
793 )
795 def __len__(self):
796 return sum(len(nbrs) for n, nbrs in self._nodes_nbrs())
798 def __iter__(self):
799 return (
800 self._report(n, nbr, dd)
801 for n, nbrs in self._nodes_nbrs()
802 for nbr, dd in nbrs.items()
803 )
805 def __contains__(self, e):
806 u, v = e[:2]
807 if self._nbunch is not None and u not in self._nbunch:
808 return False # this edge doesn't start in nbunch
809 try:
810 ddict = self._adjdict[u][v]
811 except KeyError:
812 return False
813 return e == self._report(u, v, ddict)
815 def __str__(self):
816 return str(list(self))
818 def __repr__(self):
819 return f"{self.__class__.__name__}({list(self)})"
822class EdgeDataView(OutEdgeDataView):
823 """A EdgeDataView class for edges of Graph
825 This view is primarily used to iterate over the edges reporting
826 edges as node-tuples with edge data optionally reported. The
827 argument `nbunch` allows restriction to edges incident to nodes
828 in that container/singleton. The default (nbunch=None)
829 reports all edges. The arguments `data` and `default` control
830 what edge data is reported. The default `data is False` reports
831 only node-tuples for each edge. If `data is True` the entire edge
832 data dict is returned. Otherwise `data` is assumed to hold the name
833 of the edge attribute to report with default `default` if that
834 edge attribute is not present.
836 Parameters
837 ----------
838 nbunch : container of nodes, node or None (default None)
839 data : False, True or string (default False)
840 default : default value (default None)
842 Examples
843 --------
844 >>> G = nx.path_graph(3)
845 >>> G.add_edge(1, 2, foo="bar")
846 >>> list(G.edges(data="foo", default="biz"))
847 [(0, 1, 'biz'), (1, 2, 'bar')]
848 >>> assert (0, 1, "biz") in G.edges(data="foo", default="biz")
849 """
851 __slots__ = ()
853 def __len__(self):
854 return sum(1 for e in self)
856 def __iter__(self):
857 seen = {}
858 for n, nbrs in self._nodes_nbrs():
859 for nbr, dd in nbrs.items():
860 if nbr not in seen:
861 yield self._report(n, nbr, dd)
862 seen[n] = 1
863 del seen
865 def __contains__(self, e):
866 u, v = e[:2]
867 if self._nbunch is not None and u not in self._nbunch and v not in self._nbunch:
868 return False # this edge doesn't start and it doesn't end in nbunch
869 try:
870 ddict = self._adjdict[u][v]
871 except KeyError:
872 return False
873 return e == self._report(u, v, ddict)
876class InEdgeDataView(OutEdgeDataView):
877 """An EdgeDataView class for outward edges of DiGraph; See EdgeDataView"""
879 __slots__ = ()
881 def __iter__(self):
882 return (
883 self._report(nbr, n, dd)
884 for n, nbrs in self._nodes_nbrs()
885 for nbr, dd in nbrs.items()
886 )
888 def __contains__(self, e):
889 u, v = e[:2]
890 if self._nbunch is not None and v not in self._nbunch:
891 return False # this edge doesn't end in nbunch
892 try:
893 ddict = self._adjdict[v][u]
894 except KeyError:
895 return False
896 return e == self._report(u, v, ddict)
899class OutMultiEdgeDataView(OutEdgeDataView):
900 """An EdgeDataView for outward edges of MultiDiGraph; See EdgeDataView"""
902 __slots__ = ("keys",)
904 def __getstate__(self):
905 return {
906 "viewer": self._viewer,
907 "nbunch": self._nbunch,
908 "keys": self.keys,
909 "data": self._data,
910 "default": self._default,
911 }
913 def __setstate__(self, state):
914 self.__init__(**state)
916 def __init__(self, viewer, nbunch=None, data=False, *, default=None, keys=False):
917 self._viewer = viewer
918 adjdict = self._adjdict = viewer._adjdict
919 self.keys = keys
920 if nbunch is None:
921 self._nodes_nbrs = adjdict.items
922 else:
923 # dict retains order of nodes but acts like a set
924 nbunch = dict.fromkeys(viewer._graph.nbunch_iter(nbunch))
925 self._nodes_nbrs = lambda: [(n, adjdict[n]) for n in nbunch]
926 self._nbunch = nbunch
927 self._data = data
928 self._default = default
929 # Set _report based on data and default
930 if data is True:
931 if keys is True:
932 self._report = lambda n, nbr, k, dd: (n, nbr, k, dd)
933 else:
934 self._report = lambda n, nbr, k, dd: (n, nbr, dd)
935 elif data is False:
936 if keys is True:
937 self._report = lambda n, nbr, k, dd: (n, nbr, k)
938 else:
939 self._report = lambda n, nbr, k, dd: (n, nbr)
940 else: # data is attribute name
941 if keys is True:
942 self._report = (
943 lambda n, nbr, k, dd: (n, nbr, k, dd[data])
944 if data in dd
945 else (n, nbr, k, default)
946 )
947 else:
948 self._report = (
949 lambda n, nbr, k, dd: (n, nbr, dd[data])
950 if data in dd
951 else (n, nbr, default)
952 )
954 def __len__(self):
955 return sum(1 for e in self)
957 def __iter__(self):
958 return (
959 self._report(n, nbr, k, dd)
960 for n, nbrs in self._nodes_nbrs()
961 for nbr, kd in nbrs.items()
962 for k, dd in kd.items()
963 )
965 def __contains__(self, e):
966 u, v = e[:2]
967 if self._nbunch is not None and u not in self._nbunch:
968 return False # this edge doesn't start in nbunch
969 try:
970 kdict = self._adjdict[u][v]
971 except KeyError:
972 return False
973 if self.keys is True:
974 k = e[2]
975 try:
976 dd = kdict[k]
977 except KeyError:
978 return False
979 return e == self._report(u, v, k, dd)
980 return any(e == self._report(u, v, k, dd) for k, dd in kdict.items())
983class MultiEdgeDataView(OutMultiEdgeDataView):
984 """An EdgeDataView class for edges of MultiGraph; See EdgeDataView"""
986 __slots__ = ()
988 def __iter__(self):
989 seen = {}
990 for n, nbrs in self._nodes_nbrs():
991 for nbr, kd in nbrs.items():
992 if nbr not in seen:
993 for k, dd in kd.items():
994 yield self._report(n, nbr, k, dd)
995 seen[n] = 1
996 del seen
998 def __contains__(self, e):
999 u, v = e[:2]
1000 if self._nbunch is not None and u not in self._nbunch and v not in self._nbunch:
1001 return False # this edge doesn't start and doesn't end in nbunch
1002 try:
1003 kdict = self._adjdict[u][v]
1004 except KeyError:
1005 try:
1006 kdict = self._adjdict[v][u]
1007 except KeyError:
1008 return False
1009 if self.keys is True:
1010 k = e[2]
1011 try:
1012 dd = kdict[k]
1013 except KeyError:
1014 return False
1015 return e == self._report(u, v, k, dd)
1016 return any(e == self._report(u, v, k, dd) for k, dd in kdict.items())
1019class InMultiEdgeDataView(OutMultiEdgeDataView):
1020 """An EdgeDataView for inward edges of MultiDiGraph; See EdgeDataView"""
1022 __slots__ = ()
1024 def __iter__(self):
1025 return (
1026 self._report(nbr, n, k, dd)
1027 for n, nbrs in self._nodes_nbrs()
1028 for nbr, kd in nbrs.items()
1029 for k, dd in kd.items()
1030 )
1032 def __contains__(self, e):
1033 u, v = e[:2]
1034 if self._nbunch is not None and v not in self._nbunch:
1035 return False # this edge doesn't end in nbunch
1036 try:
1037 kdict = self._adjdict[v][u]
1038 except KeyError:
1039 return False
1040 if self.keys is True:
1041 k = e[2]
1042 dd = kdict[k]
1043 return e == self._report(u, v, k, dd)
1044 return any(e == self._report(u, v, k, dd) for k, dd in kdict.items())
1047# EdgeViews have set operations and no data reported
1048class OutEdgeView(Set, Mapping, EdgeViewABC):
1049 """A EdgeView class for outward edges of a DiGraph"""
1051 __slots__ = ("_adjdict", "_graph", "_nodes_nbrs")
1053 def __getstate__(self):
1054 return {"_graph": self._graph, "_adjdict": self._adjdict}
1056 def __setstate__(self, state):
1057 self._graph = state["_graph"]
1058 self._adjdict = state["_adjdict"]
1059 self._nodes_nbrs = self._adjdict.items
1061 @classmethod
1062 def _from_iterable(cls, it):
1063 return set(it)
1065 dataview = OutEdgeDataView
1067 def __init__(self, G):
1068 self._graph = G
1069 self._adjdict = G._succ if hasattr(G, "succ") else G._adj
1070 self._nodes_nbrs = self._adjdict.items
1072 # Set methods
1073 def __len__(self):
1074 return sum(len(nbrs) for n, nbrs in self._nodes_nbrs())
1076 def __iter__(self):
1077 for n, nbrs in self._nodes_nbrs():
1078 for nbr in nbrs:
1079 yield (n, nbr)
1081 def __contains__(self, e):
1082 try:
1083 u, v = e
1084 return v in self._adjdict[u]
1085 except KeyError:
1086 return False
1088 # Mapping Methods
1089 def __getitem__(self, e):
1090 if isinstance(e, slice):
1091 raise nx.NetworkXError(
1092 f"{type(self).__name__} does not support slicing, "
1093 f"try list(G.edges)[{e.start}:{e.stop}:{e.step}]"
1094 )
1095 u, v = e
1096 try:
1097 return self._adjdict[u][v]
1098 except KeyError as ex: # Customize msg to indicate exception origin
1099 raise KeyError(f"The edge {e} is not in the graph.")
1101 # EdgeDataView methods
1102 def __call__(self, nbunch=None, data=False, *, default=None):
1103 if nbunch is None and data is False:
1104 return self
1105 return self.dataview(self, nbunch, data, default=default)
1107 def data(self, data=True, default=None, nbunch=None):
1108 """
1109 Return a read-only view of edge data.
1111 Parameters
1112 ----------
1113 data : bool or edge attribute key
1114 If ``data=True``, then the data view maps each edge to a dictionary
1115 containing all of its attributes. If `data` is a key in the edge
1116 dictionary, then the data view maps each edge to its value for
1117 the keyed attribute. In this case, if the edge doesn't have the
1118 attribute, the `default` value is returned.
1119 default : object, default=None
1120 The value used when an edge does not have a specific attribute
1121 nbunch : container of nodes, optional (default=None)
1122 Allows restriction to edges only involving certain nodes. All edges
1123 are considered by default.
1125 Returns
1126 -------
1127 dataview
1128 Returns an `EdgeDataView` for undirected Graphs, `OutEdgeDataView`
1129 for DiGraphs, `MultiEdgeDataView` for MultiGraphs and
1130 `OutMultiEdgeDataView` for MultiDiGraphs.
1132 Notes
1133 -----
1134 If ``data=False``, returns an `EdgeView` without any edge data.
1136 See Also
1137 --------
1138 EdgeDataView
1139 OutEdgeDataView
1140 MultiEdgeDataView
1141 OutMultiEdgeDataView
1143 Examples
1144 --------
1145 >>> G = nx.Graph()
1146 >>> G.add_edges_from(
1147 ... [
1148 ... (0, 1, {"dist": 3, "capacity": 20}),
1149 ... (1, 2, {"dist": 4}),
1150 ... (2, 0, {"dist": 5}),
1151 ... ]
1152 ... )
1154 Accessing edge data with ``data=True`` (the default) returns an
1155 edge data view object listing each edge with all of its attributes:
1157 >>> G.edges.data()
1158 EdgeDataView([(0, 1, {'dist': 3, 'capacity': 20}), (0, 2, {'dist': 5}), (1, 2, {'dist': 4})])
1160 If `data` represents a key in the edge attribute dict, a dataview listing
1161 each edge with its value for that specific key is returned:
1163 >>> G.edges.data("dist")
1164 EdgeDataView([(0, 1, 3), (0, 2, 5), (1, 2, 4)])
1166 `nbunch` can be used to limit the edges:
1168 >>> G.edges.data("dist", nbunch=[0])
1169 EdgeDataView([(0, 1, 3), (0, 2, 5)])
1171 If a specific key is not found in an edge attribute dict, the value
1172 specified by `default` is used:
1174 >>> G.edges.data("capacity")
1175 EdgeDataView([(0, 1, 20), (0, 2, None), (1, 2, None)])
1177 Note that there is no check that the `data` key is present in any of
1178 the edge attribute dictionaries:
1180 >>> G.edges.data("speed")
1181 EdgeDataView([(0, 1, None), (0, 2, None), (1, 2, None)])
1182 """
1183 if nbunch is None and data is False:
1184 return self
1185 return self.dataview(self, nbunch, data, default=default)
1187 # String Methods
1188 def __str__(self):
1189 return str(list(self))
1191 def __repr__(self):
1192 return f"{self.__class__.__name__}({list(self)})"
1195class EdgeView(OutEdgeView):
1196 """A EdgeView class for edges of a Graph
1198 This densely packed View allows iteration over edges, data lookup
1199 like a dict and set operations on edges represented by node-tuples.
1200 In addition, edge data can be controlled by calling this object
1201 possibly creating an EdgeDataView. Typically edges are iterated over
1202 and reported as `(u, v)` node tuples or `(u, v, key)` node/key tuples
1203 for multigraphs. Those edge representations can also be using to
1204 lookup the data dict for any edge. Set operations also are available
1205 where those tuples are the elements of the set.
1206 Calling this object with optional arguments `data`, `default` and `keys`
1207 controls the form of the tuple (see EdgeDataView). Optional argument
1208 `nbunch` allows restriction to edges only involving certain nodes.
1210 If `data is False` (the default) then iterate over 2-tuples `(u, v)`.
1211 If `data is True` iterate over 3-tuples `(u, v, datadict)`.
1212 Otherwise iterate over `(u, v, datadict.get(data, default))`.
1213 For Multigraphs, if `keys is True`, replace `u, v` with `u, v, key` above.
1215 Parameters
1216 ==========
1217 graph : NetworkX graph-like class
1218 nbunch : (default= all nodes in graph) only report edges with these nodes
1219 keys : (only for MultiGraph. default=False) report edge key in tuple
1220 data : bool or string (default=False) see above
1221 default : object (default=None)
1223 Examples
1224 ========
1225 >>> G = nx.path_graph(4)
1226 >>> EV = G.edges()
1227 >>> (2, 3) in EV
1228 True
1229 >>> for u, v in EV:
1230 ... print((u, v))
1231 (0, 1)
1232 (1, 2)
1233 (2, 3)
1234 >>> assert EV & {(1, 2), (3, 4)} == {(1, 2)}
1236 >>> EVdata = G.edges(data="color", default="aqua")
1237 >>> G.add_edge(2, 3, color="blue")
1238 >>> assert (2, 3, "blue") in EVdata
1239 >>> for u, v, c in EVdata:
1240 ... print(f"({u}, {v}) has color: {c}")
1241 (0, 1) has color: aqua
1242 (1, 2) has color: aqua
1243 (2, 3) has color: blue
1245 >>> EVnbunch = G.edges(nbunch=2)
1246 >>> assert (2, 3) in EVnbunch
1247 >>> assert (0, 1) not in EVnbunch
1248 >>> for u, v in EVnbunch:
1249 ... assert u == 2 or v == 2
1251 >>> MG = nx.path_graph(4, create_using=nx.MultiGraph)
1252 >>> EVmulti = MG.edges(keys=True)
1253 >>> (2, 3, 0) in EVmulti
1254 True
1255 >>> (2, 3) in EVmulti # 2-tuples work even when keys is True
1256 True
1257 >>> key = MG.add_edge(2, 3)
1258 >>> for u, v, k in EVmulti:
1259 ... print((u, v, k))
1260 (0, 1, 0)
1261 (1, 2, 0)
1262 (2, 3, 0)
1263 (2, 3, 1)
1264 """
1266 __slots__ = ()
1268 dataview = EdgeDataView
1270 def __len__(self):
1271 num_nbrs = (len(nbrs) + (n in nbrs) for n, nbrs in self._nodes_nbrs())
1272 return sum(num_nbrs) // 2
1274 def __iter__(self):
1275 seen = {}
1276 for n, nbrs in self._nodes_nbrs():
1277 for nbr in list(nbrs):
1278 if nbr not in seen:
1279 yield (n, nbr)
1280 seen[n] = 1
1281 del seen
1283 def __contains__(self, e):
1284 try:
1285 u, v = e[:2]
1286 return v in self._adjdict[u] or u in self._adjdict[v]
1287 except (KeyError, ValueError):
1288 return False
1291class InEdgeView(OutEdgeView):
1292 """A EdgeView class for inward edges of a DiGraph"""
1294 __slots__ = ()
1296 def __setstate__(self, state):
1297 self._graph = state["_graph"]
1298 self._adjdict = state["_adjdict"]
1299 self._nodes_nbrs = self._adjdict.items
1301 dataview = InEdgeDataView
1303 def __init__(self, G):
1304 self._graph = G
1305 self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1306 self._nodes_nbrs = self._adjdict.items
1308 def __iter__(self):
1309 for n, nbrs in self._nodes_nbrs():
1310 for nbr in nbrs:
1311 yield (nbr, n)
1313 def __contains__(self, e):
1314 try:
1315 u, v = e
1316 return u in self._adjdict[v]
1317 except KeyError:
1318 return False
1320 def __getitem__(self, e):
1321 if isinstance(e, slice):
1322 raise nx.NetworkXError(
1323 f"{type(self).__name__} does not support slicing, "
1324 f"try list(G.in_edges)[{e.start}:{e.stop}:{e.step}]"
1325 )
1326 u, v = e
1327 return self._adjdict[v][u]
1330class OutMultiEdgeView(OutEdgeView):
1331 """A EdgeView class for outward edges of a MultiDiGraph"""
1333 __slots__ = ()
1335 dataview = OutMultiEdgeDataView
1337 def __len__(self):
1338 return sum(
1339 len(kdict) for n, nbrs in self._nodes_nbrs() for nbr, kdict in nbrs.items()
1340 )
1342 def __iter__(self):
1343 for n, nbrs in self._nodes_nbrs():
1344 for nbr, kdict in nbrs.items():
1345 for key in kdict:
1346 yield (n, nbr, key)
1348 def __contains__(self, e):
1349 N = len(e)
1350 if N == 3:
1351 u, v, k = e
1352 elif N == 2:
1353 u, v = e
1354 k = 0
1355 else:
1356 raise ValueError("MultiEdge must have length 2 or 3")
1357 try:
1358 return k in self._adjdict[u][v]
1359 except KeyError:
1360 return False
1362 def __getitem__(self, e):
1363 if isinstance(e, slice):
1364 raise nx.NetworkXError(
1365 f"{type(self).__name__} does not support slicing, "
1366 f"try list(G.edges)[{e.start}:{e.stop}:{e.step}]"
1367 )
1368 u, v, k = e
1369 return self._adjdict[u][v][k]
1371 def __call__(self, nbunch=None, data=False, *, default=None, keys=False):
1372 if nbunch is None and data is False and keys is True:
1373 return self
1374 return self.dataview(self, nbunch, data, default=default, keys=keys)
1376 def data(self, data=True, default=None, nbunch=None, keys=False):
1377 if nbunch is None and data is False and keys is True:
1378 return self
1379 return self.dataview(self, nbunch, data, default=default, keys=keys)
1382class MultiEdgeView(OutMultiEdgeView):
1383 """A EdgeView class for edges of a MultiGraph"""
1385 __slots__ = ()
1387 dataview = MultiEdgeDataView
1389 def __len__(self):
1390 return sum(1 for e in self)
1392 def __iter__(self):
1393 seen = {}
1394 for n, nbrs in self._nodes_nbrs():
1395 for nbr, kd in nbrs.items():
1396 if nbr not in seen:
1397 for k, dd in kd.items():
1398 yield (n, nbr, k)
1399 seen[n] = 1
1400 del seen
1403class InMultiEdgeView(OutMultiEdgeView):
1404 """A EdgeView class for inward edges of a MultiDiGraph"""
1406 __slots__ = ()
1408 def __setstate__(self, state):
1409 self._graph = state["_graph"]
1410 self._adjdict = state["_adjdict"]
1411 self._nodes_nbrs = self._adjdict.items
1413 dataview = InMultiEdgeDataView
1415 def __init__(self, G):
1416 self._graph = G
1417 self._adjdict = G._pred if hasattr(G, "pred") else G._adj
1418 self._nodes_nbrs = self._adjdict.items
1420 def __iter__(self):
1421 for n, nbrs in self._nodes_nbrs():
1422 for nbr, kdict in nbrs.items():
1423 for key in kdict:
1424 yield (nbr, n, key)
1426 def __contains__(self, e):
1427 N = len(e)
1428 if N == 3:
1429 u, v, k = e
1430 elif N == 2:
1431 u, v = e
1432 k = 0
1433 else:
1434 raise ValueError("MultiEdge must have length 2 or 3")
1435 try:
1436 return k in self._adjdict[v][u]
1437 except KeyError:
1438 return False
1440 def __getitem__(self, e):
1441 if isinstance(e, slice):
1442 raise nx.NetworkXError(
1443 f"{type(self).__name__} does not support slicing, "
1444 f"try list(G.in_edges)[{e.start}:{e.stop}:{e.step}]"
1445 )
1446 u, v, k = e
1447 return self._adjdict[v][u][k]