1"""Base class for undirected graphs. 2 3The Graph class allows any hashable object as a node 4and can associate key/value attribute pairs with each undirected edge. 5 6Self-loops are allowed but multiple edges are not (see MultiGraph). 7 8For directed graphs see DiGraph and MultiDiGraph. 9""" 10from copy import deepcopy 11 12import networkx as nx 13from networkx.classes.coreviews import AdjacencyView 14from networkx.classes.reportviews import NodeView, EdgeView, DegreeView 15from networkx.exception import NetworkXError 16import networkx.convert as convert 17 18__all__ = ["Graph"] 19 20 21class Graph: 22 """ 23 Base class for undirected graphs. 24 25 A Graph stores nodes and edges with optional data, or attributes. 26 27 Graphs hold undirected edges. Self loops are allowed but multiple 28 (parallel) edges are not. 29 30 Nodes can be arbitrary (hashable) Python objects with optional 31 key/value attributes, except that `None` is not allowed as a node. 32 33 Edges are represented as links between nodes with optional 34 key/value attributes. 35 36 Parameters 37 ---------- 38 incoming_graph_data : input graph (optional, default: None) 39 Data to initialize graph. If None (default) an empty 40 graph is created. The data can be any format that is supported 41 by the to_networkx_graph() function, currently including edge list, 42 dict of dicts, dict of lists, NetworkX graph, NumPy matrix 43 or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph. 44 45 attr : keyword arguments, optional (default= no attributes) 46 Attributes to add to graph as key=value pairs. 47 48 See Also 49 -------- 50 DiGraph 51 MultiGraph 52 MultiDiGraph 53 OrderedGraph 54 55 Examples 56 -------- 57 Create an empty graph structure (a "null graph") with no nodes and 58 no edges. 59 60 >>> G = nx.Graph() 61 62 G can be grown in several ways. 63 64 **Nodes:** 65 66 Add one node at a time: 67 68 >>> G.add_node(1) 69 70 Add the nodes from any container (a list, dict, set or 71 even the lines from a file or the nodes from another graph). 72 73 >>> G.add_nodes_from([2, 3]) 74 >>> G.add_nodes_from(range(100, 110)) 75 >>> H = nx.path_graph(10) 76 >>> G.add_nodes_from(H) 77 78 In addition to strings and integers any hashable Python object 79 (except None) can represent a node, e.g. a customized node object, 80 or even another Graph. 81 82 >>> G.add_node(H) 83 84 **Edges:** 85 86 G can also be grown by adding edges. 87 88 Add one edge, 89 90 >>> G.add_edge(1, 2) 91 92 a list of edges, 93 94 >>> G.add_edges_from([(1, 2), (1, 3)]) 95 96 or a collection of edges, 97 98 >>> G.add_edges_from(H.edges) 99 100 If some edges connect nodes not yet in the graph, the nodes 101 are added automatically. There are no errors when adding 102 nodes or edges that already exist. 103 104 **Attributes:** 105 106 Each graph, node, and edge can hold key/value attribute pairs 107 in an associated attribute dictionary (the keys must be hashable). 108 By default these are empty, but can be added or changed using 109 add_edge, add_node or direct manipulation of the attribute 110 dictionaries named graph, node and edge respectively. 111 112 >>> G = nx.Graph(day="Friday") 113 >>> G.graph 114 {'day': 'Friday'} 115 116 Add node attributes using add_node(), add_nodes_from() or G.nodes 117 118 >>> G.add_node(1, time="5pm") 119 >>> G.add_nodes_from([3], time="2pm") 120 >>> G.nodes[1] 121 {'time': '5pm'} 122 >>> G.nodes[1]["room"] = 714 # node must exist already to use G.nodes 123 >>> del G.nodes[1]["room"] # remove attribute 124 >>> list(G.nodes(data=True)) 125 [(1, {'time': '5pm'}), (3, {'time': '2pm'})] 126 127 Add edge attributes using add_edge(), add_edges_from(), subscript 128 notation, or G.edges. 129 130 >>> G.add_edge(1, 2, weight=4.7) 131 >>> G.add_edges_from([(3, 4), (4, 5)], color="red") 132 >>> G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})]) 133 >>> G[1][2]["weight"] = 4.7 134 >>> G.edges[1, 2]["weight"] = 4 135 136 Warning: we protect the graph data structure by making `G.edges` a 137 read-only dict-like structure. However, you can assign to attributes 138 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change 139 data attributes: `G.edges[1, 2]['weight'] = 4` 140 (For multigraphs: `MG.edges[u, v, key][name] = value`). 141 142 **Shortcuts:** 143 144 Many common graph features allow python syntax to speed reporting. 145 146 >>> 1 in G # check if node in graph 147 True 148 >>> [n for n in G if n < 3] # iterate through nodes 149 [1, 2] 150 >>> len(G) # number of nodes in graph 151 5 152 153 Often the best way to traverse all edges of a graph is via the neighbors. 154 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()` 155 156 >>> for n, nbrsdict in G.adjacency(): 157 ... for nbr, eattr in nbrsdict.items(): 158 ... if "weight" in eattr: 159 ... # Do something useful with the edges 160 ... pass 161 162 But the edges() method is often more convenient: 163 164 >>> for u, v, weight in G.edges.data("weight"): 165 ... if weight is not None: 166 ... # Do something useful with the edges 167 ... pass 168 169 **Reporting:** 170 171 Simple graph information is obtained using object-attributes and methods. 172 Reporting typically provides views instead of containers to reduce memory 173 usage. The views update as the graph is updated similarly to dict-views. 174 The objects `nodes`, `edges` and `adj` provide access to data attributes 175 via lookup (e.g. `nodes[n]`, `edges[u, v]`, `adj[u][v]`) and iteration 176 (e.g. `nodes.items()`, `nodes.data('color')`, 177 `nodes.data('color', default='blue')` and similarly for `edges`) 178 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`. 179 180 For details on these and other miscellaneous methods, see below. 181 182 **Subclasses (Advanced):** 183 184 The Graph class uses a dict-of-dict-of-dict data structure. 185 The outer dict (node_dict) holds adjacency information keyed by node. 186 The next dict (adjlist_dict) represents the adjacency information and holds 187 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents 188 the edge data and holds edge attribute values keyed by attribute names. 189 190 Each of these three dicts can be replaced in a subclass by a user defined 191 dict-like object. In general, the dict-like features should be 192 maintained but extra features can be added. To replace one of the 193 dicts create a new graph class by changing the class(!) variable 194 holding the factory for that dict-like structure. 195 196 node_dict_factory : function, (default: dict) 197 Factory function to be used to create the dict containing node 198 attributes, keyed by node id. 199 It should require no arguments and return a dict-like object 200 201 node_attr_dict_factory: function, (default: dict) 202 Factory function to be used to create the node attribute 203 dict which holds attribute values keyed by attribute name. 204 It should require no arguments and return a dict-like object 205 206 adjlist_outer_dict_factory : function, (default: dict) 207 Factory function to be used to create the outer-most dict 208 in the data structure that holds adjacency info keyed by node. 209 It should require no arguments and return a dict-like object. 210 211 adjlist_inner_dict_factory : function, (default: dict) 212 Factory function to be used to create the adjacency list 213 dict which holds edge data keyed by neighbor. 214 It should require no arguments and return a dict-like object 215 216 edge_attr_dict_factory : function, (default: dict) 217 Factory function to be used to create the edge attribute 218 dict which holds attribute values keyed by attribute name. 219 It should require no arguments and return a dict-like object. 220 221 graph_attr_dict_factory : function, (default: dict) 222 Factory function to be used to create the graph attribute 223 dict which holds attribute values keyed by attribute name. 224 It should require no arguments and return a dict-like object. 225 226 Typically, if your extension doesn't impact the data structure all 227 methods will inherit without issue except: `to_directed/to_undirected`. 228 By default these methods create a DiGraph/Graph class and you probably 229 want them to create your extension of a DiGraph/Graph. To facilitate 230 this we define two class variables that you can set in your subclass. 231 232 to_directed_class : callable, (default: DiGraph or MultiDiGraph) 233 Class to create a new graph structure in the `to_directed` method. 234 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used. 235 236 to_undirected_class : callable, (default: Graph or MultiGraph) 237 Class to create a new graph structure in the `to_undirected` method. 238 If `None`, a NetworkX class (Graph or MultiGraph) is used. 239 240 **Subclassing Example** 241 242 Create a low memory graph class that effectively disallows edge 243 attributes by using a single attribute dict for all edges. 244 This reduces the memory used, but you lose edge attributes. 245 246 >>> class ThinGraph(nx.Graph): 247 ... all_edge_dict = {"weight": 1} 248 ... 249 ... def single_edge_dict(self): 250 ... return self.all_edge_dict 251 ... 252 ... edge_attr_dict_factory = single_edge_dict 253 >>> G = ThinGraph() 254 >>> G.add_edge(2, 1) 255 >>> G[2][1] 256 {'weight': 1} 257 >>> G.add_edge(2, 2) 258 >>> G[2][1] is G[2][2] 259 True 260 261 Please see :mod:`~networkx.classes.ordered` for more examples of 262 creating graph subclasses by overwriting the base class `dict` with 263 a dictionary-like object. 264 """ 265 266 node_dict_factory = dict 267 node_attr_dict_factory = dict 268 adjlist_outer_dict_factory = dict 269 adjlist_inner_dict_factory = dict 270 edge_attr_dict_factory = dict 271 graph_attr_dict_factory = dict 272 273 def to_directed_class(self): 274 """Returns the class to use for empty directed copies. 275 276 If you subclass the base classes, use this to designate 277 what directed class to use for `to_directed()` copies. 278 """ 279 return nx.DiGraph 280 281 def to_undirected_class(self): 282 """Returns the class to use for empty undirected copies. 283 284 If you subclass the base classes, use this to designate 285 what directed class to use for `to_directed()` copies. 286 """ 287 return Graph 288 289 def __init__(self, incoming_graph_data=None, **attr): 290 """Initialize a graph with edges, name, or graph attributes. 291 292 Parameters 293 ---------- 294 incoming_graph_data : input graph (optional, default: None) 295 Data to initialize graph. If None (default) an empty 296 graph is created. The data can be an edge list, or any 297 NetworkX graph object. If the corresponding optional Python 298 packages are installed the data can also be a NumPy matrix 299 or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph. 300 301 attr : keyword arguments, optional (default= no attributes) 302 Attributes to add to graph as key=value pairs. 303 304 See Also 305 -------- 306 convert 307 308 Examples 309 -------- 310 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 311 >>> G = nx.Graph(name="my graph") 312 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges 313 >>> G = nx.Graph(e) 314 315 Arbitrary graph attribute pairs (key=value) may be assigned 316 317 >>> G = nx.Graph(e, day="Friday") 318 >>> G.graph 319 {'day': 'Friday'} 320 321 """ 322 self.graph_attr_dict_factory = self.graph_attr_dict_factory 323 self.node_dict_factory = self.node_dict_factory 324 self.node_attr_dict_factory = self.node_attr_dict_factory 325 self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory 326 self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory 327 self.edge_attr_dict_factory = self.edge_attr_dict_factory 328 329 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes 330 self._node = self.node_dict_factory() # empty node attribute dict 331 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict 332 # attempt to load graph with data 333 if incoming_graph_data is not None: 334 convert.to_networkx_graph(incoming_graph_data, create_using=self) 335 # load graph attributes (must be after convert) 336 self.graph.update(attr) 337 338 @property 339 def adj(self): 340 """Graph adjacency object holding the neighbors of each node. 341 342 This object is a read-only dict-like structure with node keys 343 and neighbor-dict values. The neighbor-dict is keyed by neighbor 344 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets 345 the color of the edge `(3, 2)` to `"blue"`. 346 347 Iterating over G.adj behaves like a dict. Useful idioms include 348 `for nbr, datadict in G.adj[n].items():`. 349 350 The neighbor information is also provided by subscripting the graph. 351 So `for nbr, foovalue in G[node].data('foo', default=1):` works. 352 353 For directed graphs, `G.adj` holds outgoing (successor) info. 354 """ 355 return AdjacencyView(self._adj) 356 357 @property 358 def name(self): 359 """String identifier of the graph. 360 361 This graph attribute appears in the attribute dict G.graph 362 keyed by the string `"name"`. as well as an attribute (technically 363 a property) `G.name`. This is entirely user controlled. 364 """ 365 return self.graph.get("name", "") 366 367 @name.setter 368 def name(self, s): 369 self.graph["name"] = s 370 371 def __str__(self): 372 """Returns a short summary of the graph. 373 374 Returns 375 ------- 376 info : string 377 Graph information as provided by `nx.info` 378 379 Examples 380 -------- 381 >>> G = nx.Graph(name="foo") 382 >>> str(G) 383 "Graph named 'foo' with 0 nodes and 0 edges" 384 385 >>> G = nx.path_graph(3) 386 >>> str(G) 387 'Graph with 3 nodes and 2 edges' 388 389 """ 390 return "".join( 391 [ 392 type(self).__name__, 393 f" named {self.name!r}" if self.name else "", 394 f" with {self.number_of_nodes()} nodes and {self.number_of_edges()} edges", 395 ] 396 ) 397 398 def __iter__(self): 399 """Iterate over the nodes. Use: 'for n in G'. 400 401 Returns 402 ------- 403 niter : iterator 404 An iterator over all nodes in the graph. 405 406 Examples 407 -------- 408 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 409 >>> [n for n in G] 410 [0, 1, 2, 3] 411 >>> list(G) 412 [0, 1, 2, 3] 413 """ 414 return iter(self._node) 415 416 def __contains__(self, n): 417 """Returns True if n is a node, False otherwise. Use: 'n in G'. 418 419 Examples 420 -------- 421 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 422 >>> 1 in G 423 True 424 """ 425 try: 426 return n in self._node 427 except TypeError: 428 return False 429 430 def __len__(self): 431 """Returns the number of nodes in the graph. Use: 'len(G)'. 432 433 Returns 434 ------- 435 nnodes : int 436 The number of nodes in the graph. 437 438 See Also 439 -------- 440 number_of_nodes: identical method 441 order: identical method 442 443 Examples 444 -------- 445 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 446 >>> len(G) 447 4 448 449 """ 450 return len(self._node) 451 452 def __getitem__(self, n): 453 """Returns a dict of neighbors of node n. Use: 'G[n]'. 454 455 Parameters 456 ---------- 457 n : node 458 A node in the graph. 459 460 Returns 461 ------- 462 adj_dict : dictionary 463 The adjacency dictionary for nodes connected to n. 464 465 Notes 466 ----- 467 G[n] is the same as G.adj[n] and similar to G.neighbors(n) 468 (which is an iterator over G.adj[n]) 469 470 Examples 471 -------- 472 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 473 >>> G[0] 474 AtlasView({1: {}}) 475 """ 476 return self.adj[n] 477 478 def add_node(self, node_for_adding, **attr): 479 """Add a single node `node_for_adding` and update node attributes. 480 481 Parameters 482 ---------- 483 node_for_adding : node 484 A node can be any hashable Python object except None. 485 attr : keyword arguments, optional 486 Set or change node attributes using key=value. 487 488 See Also 489 -------- 490 add_nodes_from 491 492 Examples 493 -------- 494 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 495 >>> G.add_node(1) 496 >>> G.add_node("Hello") 497 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) 498 >>> G.add_node(K3) 499 >>> G.number_of_nodes() 500 3 501 502 Use keywords set/change node attributes: 503 504 >>> G.add_node(1, size=10) 505 >>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649)) 506 507 Notes 508 ----- 509 A hashable object is one that can be used as a key in a Python 510 dictionary. This includes strings, numbers, tuples of strings 511 and numbers, etc. 512 513 On many platforms hashable items also include mutables such as 514 NetworkX Graphs, though one should be careful that the hash 515 doesn't change on mutables. 516 """ 517 if node_for_adding not in self._node: 518 if node_for_adding is None: 519 raise ValueError("None cannot be a node") 520 self._adj[node_for_adding] = self.adjlist_inner_dict_factory() 521 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory() 522 attr_dict.update(attr) 523 else: # update attr even if node already exists 524 self._node[node_for_adding].update(attr) 525 526 def add_nodes_from(self, nodes_for_adding, **attr): 527 """Add multiple nodes. 528 529 Parameters 530 ---------- 531 nodes_for_adding : iterable container 532 A container of nodes (list, dict, set, etc.). 533 OR 534 A container of (node, attribute dict) tuples. 535 Node attributes are updated using the attribute dict. 536 attr : keyword arguments, optional (default= no attributes) 537 Update attributes for all nodes in nodes. 538 Node attributes specified in nodes as a tuple take 539 precedence over attributes specified via keyword arguments. 540 541 See Also 542 -------- 543 add_node 544 545 Examples 546 -------- 547 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 548 >>> G.add_nodes_from("Hello") 549 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) 550 >>> G.add_nodes_from(K3) 551 >>> sorted(G.nodes(), key=str) 552 [0, 1, 2, 'H', 'e', 'l', 'o'] 553 554 Use keywords to update specific node attributes for every node. 555 556 >>> G.add_nodes_from([1, 2], size=10) 557 >>> G.add_nodes_from([3, 4], weight=0.4) 558 559 Use (node, attrdict) tuples to update attributes for specific nodes. 560 561 >>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})]) 562 >>> G.nodes[1]["size"] 563 11 564 >>> H = nx.Graph() 565 >>> H.add_nodes_from(G.nodes(data=True)) 566 >>> H.nodes[1]["size"] 567 11 568 569 """ 570 for n in nodes_for_adding: 571 try: 572 newnode = n not in self._node 573 newdict = attr 574 except TypeError: 575 n, ndict = n 576 newnode = n not in self._node 577 newdict = attr.copy() 578 newdict.update(ndict) 579 if newnode: 580 if n is None: 581 raise ValueError("None cannot be a node") 582 self._adj[n] = self.adjlist_inner_dict_factory() 583 self._node[n] = self.node_attr_dict_factory() 584 self._node[n].update(newdict) 585 586 def remove_node(self, n): 587 """Remove node n. 588 589 Removes the node n and all adjacent edges. 590 Attempting to remove a non-existent node will raise an exception. 591 592 Parameters 593 ---------- 594 n : node 595 A node in the graph 596 597 Raises 598 ------ 599 NetworkXError 600 If n is not in the graph. 601 602 See Also 603 -------- 604 remove_nodes_from 605 606 Examples 607 -------- 608 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 609 >>> list(G.edges) 610 [(0, 1), (1, 2)] 611 >>> G.remove_node(1) 612 >>> list(G.edges) 613 [] 614 615 """ 616 adj = self._adj 617 try: 618 nbrs = list(adj[n]) # list handles self-loops (allows mutation) 619 del self._node[n] 620 except KeyError as e: # NetworkXError if n not in self 621 raise NetworkXError(f"The node {n} is not in the graph.") from e 622 for u in nbrs: 623 del adj[u][n] # remove all edges n-u in graph 624 del adj[n] # now remove node 625 626 def remove_nodes_from(self, nodes): 627 """Remove multiple nodes. 628 629 Parameters 630 ---------- 631 nodes : iterable container 632 A container of nodes (list, dict, set, etc.). If a node 633 in the container is not in the graph it is silently 634 ignored. 635 636 See Also 637 -------- 638 remove_node 639 640 Examples 641 -------- 642 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 643 >>> e = list(G.nodes) 644 >>> e 645 [0, 1, 2] 646 >>> G.remove_nodes_from(e) 647 >>> list(G.nodes) 648 [] 649 650 """ 651 adj = self._adj 652 for n in nodes: 653 try: 654 del self._node[n] 655 for u in list(adj[n]): # list handles self-loops 656 del adj[u][n] # (allows mutation of dict in loop) 657 del adj[n] 658 except KeyError: 659 pass 660 661 @property 662 def nodes(self): 663 """A NodeView of the Graph as G.nodes or G.nodes(). 664 665 Can be used as `G.nodes` for data lookup and for set-like operations. 666 Can also be used as `G.nodes(data='color', default=None)` to return a 667 NodeDataView which reports specific node data but no set operations. 668 It presents a dict-like interface as well with `G.nodes.items()` 669 iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']` 670 providing the value of the `foo` attribute for node `3`. In addition, 671 a view `G.nodes.data('foo')` provides a dict-like interface to the 672 `foo` attribute of each node. `G.nodes.data('foo', default=1)` 673 provides a default for nodes that do not have attribute `foo`. 674 675 Parameters 676 ---------- 677 data : string or bool, optional (default=False) 678 The node attribute returned in 2-tuple (n, ddict[data]). 679 If True, return entire node attribute dict as (n, ddict). 680 If False, return just the nodes n. 681 682 default : value, optional (default=None) 683 Value used for nodes that don't have the requested attribute. 684 Only relevant if data is not True or False. 685 686 Returns 687 ------- 688 NodeView 689 Allows set-like operations over the nodes as well as node 690 attribute dict lookup and calling to get a NodeDataView. 691 A NodeDataView iterates over `(n, data)` and has no set operations. 692 A NodeView iterates over `n` and includes set operations. 693 694 When called, if data is False, an iterator over nodes. 695 Otherwise an iterator of 2-tuples (node, attribute value) 696 where the attribute is specified in `data`. 697 If data is True then the attribute becomes the 698 entire data dictionary. 699 700 Notes 701 ----- 702 If your node data is not needed, it is simpler and equivalent 703 to use the expression ``for n in G``, or ``list(G)``. 704 705 Examples 706 -------- 707 There are two simple ways of getting a list of all nodes in the graph: 708 709 >>> G = nx.path_graph(3) 710 >>> list(G.nodes) 711 [0, 1, 2] 712 >>> list(G) 713 [0, 1, 2] 714 715 To get the node data along with the nodes: 716 717 >>> G.add_node(1, time="5pm") 718 >>> G.nodes[0]["foo"] = "bar" 719 >>> list(G.nodes(data=True)) 720 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})] 721 >>> list(G.nodes.data()) 722 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})] 723 724 >>> list(G.nodes(data="foo")) 725 [(0, 'bar'), (1, None), (2, None)] 726 >>> list(G.nodes.data("foo")) 727 [(0, 'bar'), (1, None), (2, None)] 728 729 >>> list(G.nodes(data="time")) 730 [(0, None), (1, '5pm'), (2, None)] 731 >>> list(G.nodes.data("time")) 732 [(0, None), (1, '5pm'), (2, None)] 733 734 >>> list(G.nodes(data="time", default="Not Available")) 735 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')] 736 >>> list(G.nodes.data("time", default="Not Available")) 737 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')] 738 739 If some of your nodes have an attribute and the rest are assumed 740 to have a default attribute value you can create a dictionary 741 from node/attribute pairs using the `default` keyword argument 742 to guarantee the value is never None:: 743 744 >>> G = nx.Graph() 745 >>> G.add_node(0) 746 >>> G.add_node(1, weight=2) 747 >>> G.add_node(2, weight=3) 748 >>> dict(G.nodes(data="weight", default=1)) 749 {0: 1, 1: 2, 2: 3} 750 751 """ 752 nodes = NodeView(self) 753 # Lazy View creation: overload the (class) property on the instance 754 # Then future G.nodes use the existing View 755 # setattr doesn't work because attribute already exists 756 self.__dict__["nodes"] = nodes 757 return nodes 758 759 def number_of_nodes(self): 760 """Returns the number of nodes in the graph. 761 762 Returns 763 ------- 764 nnodes : int 765 The number of nodes in the graph. 766 767 See Also 768 -------- 769 order: identical method 770 __len__: identical method 771 772 Examples 773 -------- 774 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 775 >>> G.number_of_nodes() 776 3 777 """ 778 return len(self._node) 779 780 def order(self): 781 """Returns the number of nodes in the graph. 782 783 Returns 784 ------- 785 nnodes : int 786 The number of nodes in the graph. 787 788 See Also 789 -------- 790 number_of_nodes: identical method 791 __len__: identical method 792 793 Examples 794 -------- 795 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 796 >>> G.order() 797 3 798 """ 799 return len(self._node) 800 801 def has_node(self, n): 802 """Returns True if the graph contains the node n. 803 804 Identical to `n in G` 805 806 Parameters 807 ---------- 808 n : node 809 810 Examples 811 -------- 812 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 813 >>> G.has_node(0) 814 True 815 816 It is more readable and simpler to use 817 818 >>> 0 in G 819 True 820 821 """ 822 try: 823 return n in self._node 824 except TypeError: 825 return False 826 827 def add_edge(self, u_of_edge, v_of_edge, **attr): 828 """Add an edge between u and v. 829 830 The nodes u and v will be automatically added if they are 831 not already in the graph. 832 833 Edge attributes can be specified with keywords or by directly 834 accessing the edge's attribute dictionary. See examples below. 835 836 Parameters 837 ---------- 838 u_of_edge, v_of_edge : nodes 839 Nodes can be, for example, strings or numbers. 840 Nodes must be hashable (and not None) Python objects. 841 attr : keyword arguments, optional 842 Edge data (or labels or objects) can be assigned using 843 keyword arguments. 844 845 See Also 846 -------- 847 add_edges_from : add a collection of edges 848 849 Notes 850 ----- 851 Adding an edge that already exists updates the edge data. 852 853 Many NetworkX algorithms designed for weighted graphs use 854 an edge attribute (by default `weight`) to hold a numerical value. 855 856 Examples 857 -------- 858 The following all add the edge e=(1, 2) to graph G: 859 860 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 861 >>> e = (1, 2) 862 >>> G.add_edge(1, 2) # explicit two-node form 863 >>> G.add_edge(*e) # single edge as tuple of two nodes 864 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container 865 866 Associate data to edges using keywords: 867 868 >>> G.add_edge(1, 2, weight=3) 869 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7) 870 871 For non-string attribute keys, use subscript notation. 872 873 >>> G.add_edge(1, 2) 874 >>> G[1][2].update({0: 5}) 875 >>> G.edges[1, 2].update({0: 5}) 876 """ 877 u, v = u_of_edge, v_of_edge 878 # add nodes 879 if u not in self._node: 880 if u is None: 881 raise ValueError("None cannot be a node") 882 self._adj[u] = self.adjlist_inner_dict_factory() 883 self._node[u] = self.node_attr_dict_factory() 884 if v not in self._node: 885 if v is None: 886 raise ValueError("None cannot be a node") 887 self._adj[v] = self.adjlist_inner_dict_factory() 888 self._node[v] = self.node_attr_dict_factory() 889 # add the edge 890 datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) 891 datadict.update(attr) 892 self._adj[u][v] = datadict 893 self._adj[v][u] = datadict 894 895 def add_edges_from(self, ebunch_to_add, **attr): 896 """Add all the edges in ebunch_to_add. 897 898 Parameters 899 ---------- 900 ebunch_to_add : container of edges 901 Each edge given in the container will be added to the 902 graph. The edges must be given as 2-tuples (u, v) or 903 3-tuples (u, v, d) where d is a dictionary containing edge data. 904 attr : keyword arguments, optional 905 Edge data (or labels or objects) can be assigned using 906 keyword arguments. 907 908 See Also 909 -------- 910 add_edge : add a single edge 911 add_weighted_edges_from : convenient way to add weighted edges 912 913 Notes 914 ----- 915 Adding the same edge twice has no effect but any edge data 916 will be updated when each duplicate edge is added. 917 918 Edge attributes specified in an ebunch take precedence over 919 attributes specified via keyword arguments. 920 921 Examples 922 -------- 923 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 924 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples 925 >>> e = zip(range(0, 3), range(1, 4)) 926 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3 927 928 Associate data to edges 929 930 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3) 931 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898") 932 """ 933 for e in ebunch_to_add: 934 ne = len(e) 935 if ne == 3: 936 u, v, dd = e 937 elif ne == 2: 938 u, v = e 939 dd = {} # doesn't need edge_attr_dict_factory 940 else: 941 raise NetworkXError(f"Edge tuple {e} must be a 2-tuple or 3-tuple.") 942 if u not in self._node: 943 if u is None: 944 raise ValueError("None cannot be a node") 945 self._adj[u] = self.adjlist_inner_dict_factory() 946 self._node[u] = self.node_attr_dict_factory() 947 if v not in self._node: 948 if v is None: 949 raise ValueError("None cannot be a node") 950 self._adj[v] = self.adjlist_inner_dict_factory() 951 self._node[v] = self.node_attr_dict_factory() 952 datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) 953 datadict.update(attr) 954 datadict.update(dd) 955 self._adj[u][v] = datadict 956 self._adj[v][u] = datadict 957 958 def add_weighted_edges_from(self, ebunch_to_add, weight="weight", **attr): 959 """Add weighted edges in `ebunch_to_add` with specified weight attr 960 961 Parameters 962 ---------- 963 ebunch_to_add : container of edges 964 Each edge given in the list or container will be added 965 to the graph. The edges must be given as 3-tuples (u, v, w) 966 where w is a number. 967 weight : string, optional (default= 'weight') 968 The attribute name for the edge weights to be added. 969 attr : keyword arguments, optional (default= no attributes) 970 Edge attributes to add/update for all edges. 971 972 See Also 973 -------- 974 add_edge : add a single edge 975 add_edges_from : add multiple edges 976 977 Notes 978 ----- 979 Adding the same edge twice for Graph/DiGraph simply updates 980 the edge data. For MultiGraph/MultiDiGraph, duplicate edges 981 are stored. 982 983 Examples 984 -------- 985 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 986 >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)]) 987 """ 988 self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), **attr) 989 990 def remove_edge(self, u, v): 991 """Remove the edge between u and v. 992 993 Parameters 994 ---------- 995 u, v : nodes 996 Remove the edge between nodes u and v. 997 998 Raises 999 ------ 1000 NetworkXError 1001 If there is not an edge between u and v. 1002 1003 See Also 1004 -------- 1005 remove_edges_from : remove a collection of edges 1006 1007 Examples 1008 -------- 1009 >>> G = nx.path_graph(4) # or DiGraph, etc 1010 >>> G.remove_edge(0, 1) 1011 >>> e = (1, 2) 1012 >>> G.remove_edge(*e) # unpacks e from an edge tuple 1013 >>> e = (2, 3, {"weight": 7}) # an edge with attribute data 1014 >>> G.remove_edge(*e[:2]) # select first part of edge tuple 1015 """ 1016 try: 1017 del self._adj[u][v] 1018 if u != v: # self-loop needs only one entry removed 1019 del self._adj[v][u] 1020 except KeyError as e: 1021 raise NetworkXError(f"The edge {u}-{v} is not in the graph") from e 1022 1023 def remove_edges_from(self, ebunch): 1024 """Remove all edges specified in ebunch. 1025 1026 Parameters 1027 ---------- 1028 ebunch: list or container of edge tuples 1029 Each edge given in the list or container will be removed 1030 from the graph. The edges can be: 1031 1032 - 2-tuples (u, v) edge between u and v. 1033 - 3-tuples (u, v, k) where k is ignored. 1034 1035 See Also 1036 -------- 1037 remove_edge : remove a single edge 1038 1039 Notes 1040 ----- 1041 Will fail silently if an edge in ebunch is not in the graph. 1042 1043 Examples 1044 -------- 1045 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1046 >>> ebunch = [(1, 2), (2, 3)] 1047 >>> G.remove_edges_from(ebunch) 1048 """ 1049 adj = self._adj 1050 for e in ebunch: 1051 u, v = e[:2] # ignore edge data if present 1052 if u in adj and v in adj[u]: 1053 del adj[u][v] 1054 if u != v: # self loop needs only one entry removed 1055 del adj[v][u] 1056 1057 def update(self, edges=None, nodes=None): 1058 """Update the graph using nodes/edges/graphs as input. 1059 1060 Like dict.update, this method takes a graph as input, adding the 1061 graph's nodes and edges to this graph. It can also take two inputs: 1062 edges and nodes. Finally it can take either edges or nodes. 1063 To specify only nodes the keyword `nodes` must be used. 1064 1065 The collections of edges and nodes are treated similarly to 1066 the add_edges_from/add_nodes_from methods. When iterated, they 1067 should yield 2-tuples (u, v) or 3-tuples (u, v, datadict). 1068 1069 Parameters 1070 ---------- 1071 edges : Graph object, collection of edges, or None 1072 The first parameter can be a graph or some edges. If it has 1073 attributes `nodes` and `edges`, then it is taken to be a 1074 Graph-like object and those attributes are used as collections 1075 of nodes and edges to be added to the graph. 1076 If the first parameter does not have those attributes, it is 1077 treated as a collection of edges and added to the graph. 1078 If the first argument is None, no edges are added. 1079 nodes : collection of nodes, or None 1080 The second parameter is treated as a collection of nodes 1081 to be added to the graph unless it is None. 1082 If `edges is None` and `nodes is None` an exception is raised. 1083 If the first parameter is a Graph, then `nodes` is ignored. 1084 1085 Examples 1086 -------- 1087 >>> G = nx.path_graph(5) 1088 >>> G.update(nx.complete_graph(range(4, 10))) 1089 >>> from itertools import combinations 1090 >>> edges = ( 1091 ... (u, v, {"power": u * v}) 1092 ... for u, v in combinations(range(10, 20), 2) 1093 ... if u * v < 225 1094 ... ) 1095 >>> nodes = [1000] # for singleton, use a container 1096 >>> G.update(edges, nodes) 1097 1098 Notes 1099 ----- 1100 It you want to update the graph using an adjacency structure 1101 it is straightforward to obtain the edges/nodes from adjacency. 1102 The following examples provide common cases, your adjacency may 1103 be slightly different and require tweaks of these examples:: 1104 1105 >>> # dict-of-set/list/tuple 1106 >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}} 1107 >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs] 1108 >>> G.update(edges=e, nodes=adj) 1109 1110 >>> DG = nx.DiGraph() 1111 >>> # dict-of-dict-of-attribute 1112 >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}} 1113 >>> e = [ 1114 ... (u, v, {"weight": d}) 1115 ... for u, nbrs in adj.items() 1116 ... for v, d in nbrs.items() 1117 ... ] 1118 >>> DG.update(edges=e, nodes=adj) 1119 1120 >>> # dict-of-dict-of-dict 1121 >>> adj = {1: {2: {"weight": 1.3}, 3: {"color": 0.7, "weight": 1.2}}} 1122 >>> e = [ 1123 ... (u, v, {"weight": d}) 1124 ... for u, nbrs in adj.items() 1125 ... for v, d in nbrs.items() 1126 ... ] 1127 >>> DG.update(edges=e, nodes=adj) 1128 1129 >>> # predecessor adjacency (dict-of-set) 1130 >>> pred = {1: {2, 3}, 2: {3}, 3: {3}} 1131 >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs] 1132 1133 >>> # MultiGraph dict-of-dict-of-dict-of-attribute 1134 >>> MDG = nx.MultiDiGraph() 1135 >>> adj = { 1136 ... 1: {2: {0: {"weight": 1.3}, 1: {"weight": 1.2}}}, 1137 ... 3: {2: {0: {"weight": 0.7}}}, 1138 ... } 1139 >>> e = [ 1140 ... (u, v, ekey, d) 1141 ... for u, nbrs in adj.items() 1142 ... for v, keydict in nbrs.items() 1143 ... for ekey, d in keydict.items() 1144 ... ] 1145 >>> MDG.update(edges=e) 1146 1147 See Also 1148 -------- 1149 add_edges_from: add multiple edges to a graph 1150 add_nodes_from: add multiple nodes to a graph 1151 """ 1152 if edges is not None: 1153 if nodes is not None: 1154 self.add_nodes_from(nodes) 1155 self.add_edges_from(edges) 1156 else: 1157 # check if edges is a Graph object 1158 try: 1159 graph_nodes = edges.nodes 1160 graph_edges = edges.edges 1161 except AttributeError: 1162 # edge not Graph-like 1163 self.add_edges_from(edges) 1164 else: # edges is Graph-like 1165 self.add_nodes_from(graph_nodes.data()) 1166 self.add_edges_from(graph_edges.data()) 1167 self.graph.update(edges.graph) 1168 elif nodes is not None: 1169 self.add_nodes_from(nodes) 1170 else: 1171 raise NetworkXError("update needs nodes or edges input") 1172 1173 def has_edge(self, u, v): 1174 """Returns True if the edge (u, v) is in the graph. 1175 1176 This is the same as `v in G[u]` without KeyError exceptions. 1177 1178 Parameters 1179 ---------- 1180 u, v : nodes 1181 Nodes can be, for example, strings or numbers. 1182 Nodes must be hashable (and not None) Python objects. 1183 1184 Returns 1185 ------- 1186 edge_ind : bool 1187 True if edge is in the graph, False otherwise. 1188 1189 Examples 1190 -------- 1191 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1192 >>> G.has_edge(0, 1) # using two nodes 1193 True 1194 >>> e = (0, 1) 1195 >>> G.has_edge(*e) # e is a 2-tuple (u, v) 1196 True 1197 >>> e = (0, 1, {"weight": 7}) 1198 >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary) 1199 True 1200 1201 The following syntax are equivalent: 1202 1203 >>> G.has_edge(0, 1) 1204 True 1205 >>> 1 in G[0] # though this gives KeyError if 0 not in G 1206 True 1207 1208 """ 1209 try: 1210 return v in self._adj[u] 1211 except KeyError: 1212 return False 1213 1214 def neighbors(self, n): 1215 """Returns an iterator over all neighbors of node n. 1216 1217 This is identical to `iter(G[n])` 1218 1219 Parameters 1220 ---------- 1221 n : node 1222 A node in the graph 1223 1224 Returns 1225 ------- 1226 neighbors : iterator 1227 An iterator over all neighbors of node n 1228 1229 Raises 1230 ------ 1231 NetworkXError 1232 If the node n is not in the graph. 1233 1234 Examples 1235 -------- 1236 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1237 >>> [n for n in G.neighbors(0)] 1238 [1] 1239 1240 Notes 1241 ----- 1242 Alternate ways to access the neighbors are ``G.adj[n]`` or ``G[n]``: 1243 1244 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 1245 >>> G.add_edge("a", "b", weight=7) 1246 >>> G["a"] 1247 AtlasView({'b': {'weight': 7}}) 1248 >>> G = nx.path_graph(4) 1249 >>> [n for n in G[0]] 1250 [1] 1251 """ 1252 try: 1253 return iter(self._adj[n]) 1254 except KeyError as e: 1255 raise NetworkXError(f"The node {n} is not in the graph.") from e 1256 1257 @property 1258 def edges(self): 1259 """An EdgeView of the Graph as G.edges or G.edges(). 1260 1261 edges(self, nbunch=None, data=False, default=None) 1262 1263 The EdgeView provides set-like operations on the edge-tuples 1264 as well as edge attribute lookup. When called, it also provides 1265 an EdgeDataView object which allows control of access to edge 1266 attributes (but does not provide set-like operations). 1267 Hence, `G.edges[u, v]['color']` provides the value of the color 1268 attribute for edge `(u, v)` while 1269 `for (u, v, c) in G.edges.data('color', default='red'):` 1270 iterates through all the edges yielding the color attribute 1271 with default `'red'` if no color attribute exists. 1272 1273 Parameters 1274 ---------- 1275 nbunch : single node, container, or all nodes (default= all nodes) 1276 The view will only report edges incident to these nodes. 1277 data : string or bool, optional (default=False) 1278 The edge attribute returned in 3-tuple (u, v, ddict[data]). 1279 If True, return edge attribute dict in 3-tuple (u, v, ddict). 1280 If False, return 2-tuple (u, v). 1281 default : value, optional (default=None) 1282 Value used for edges that don't have the requested attribute. 1283 Only relevant if data is not True or False. 1284 1285 Returns 1286 ------- 1287 edges : EdgeView 1288 A view of edge attributes, usually it iterates over (u, v) 1289 or (u, v, d) tuples of edges, but can also be used for 1290 attribute lookup as `edges[u, v]['foo']`. 1291 1292 Notes 1293 ----- 1294 Nodes in nbunch that are not in the graph will be (quietly) ignored. 1295 For directed graphs this returns the out-edges. 1296 1297 Examples 1298 -------- 1299 >>> G = nx.path_graph(3) # or MultiGraph, etc 1300 >>> G.add_edge(2, 3, weight=5) 1301 >>> [e for e in G.edges] 1302 [(0, 1), (1, 2), (2, 3)] 1303 >>> G.edges.data() # default data is {} (empty dict) 1304 EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})]) 1305 >>> G.edges.data("weight", default=1) 1306 EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)]) 1307 >>> G.edges([0, 3]) # only edges incident to these nodes 1308 EdgeDataView([(0, 1), (3, 2)]) 1309 >>> G.edges(0) # only edges incident to a single node (use G.adj[0]?) 1310 EdgeDataView([(0, 1)]) 1311 """ 1312 return EdgeView(self) 1313 1314 def get_edge_data(self, u, v, default=None): 1315 """Returns the attribute dictionary associated with edge (u, v). 1316 1317 This is identical to `G[u][v]` except the default is returned 1318 instead of an exception if the edge doesn't exist. 1319 1320 Parameters 1321 ---------- 1322 u, v : nodes 1323 default: any Python object (default=None) 1324 Value to return if the edge (u, v) is not found. 1325 1326 Returns 1327 ------- 1328 edge_dict : dictionary 1329 The edge attribute dictionary. 1330 1331 Examples 1332 -------- 1333 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1334 >>> G[0][1] 1335 {} 1336 1337 Warning: Assigning to `G[u][v]` is not permitted. 1338 But it is safe to assign attributes `G[u][v]['foo']` 1339 1340 >>> G[0][1]["weight"] = 7 1341 >>> G[0][1]["weight"] 1342 7 1343 >>> G[1][0]["weight"] 1344 7 1345 1346 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1347 >>> G.get_edge_data(0, 1) # default edge data is {} 1348 {} 1349 >>> e = (0, 1) 1350 >>> G.get_edge_data(*e) # tuple form 1351 {} 1352 >>> G.get_edge_data("a", "b", default=0) # edge not in graph, return 0 1353 0 1354 """ 1355 try: 1356 return self._adj[u][v] 1357 except KeyError: 1358 return default 1359 1360 def adjacency(self): 1361 """Returns an iterator over (node, adjacency dict) tuples for all nodes. 1362 1363 For directed graphs, only outgoing neighbors/adjacencies are included. 1364 1365 Returns 1366 ------- 1367 adj_iter : iterator 1368 An iterator over (node, adjacency dictionary) for all nodes in 1369 the graph. 1370 1371 Examples 1372 -------- 1373 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1374 >>> [(n, nbrdict) for n, nbrdict in G.adjacency()] 1375 [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})] 1376 1377 """ 1378 return iter(self._adj.items()) 1379 1380 @property 1381 def degree(self): 1382 """A DegreeView for the Graph as G.degree or G.degree(). 1383 1384 The node degree is the number of edges adjacent to the node. 1385 The weighted node degree is the sum of the edge weights for 1386 edges incident to that node. 1387 1388 This object provides an iterator for (node, degree) as well as 1389 lookup for the degree for a single node. 1390 1391 Parameters 1392 ---------- 1393 nbunch : single node, container, or all nodes (default= all nodes) 1394 The view will only report edges incident to these nodes. 1395 1396 weight : string or None, optional (default=None) 1397 The name of an edge attribute that holds the numerical value used 1398 as a weight. If None, then each edge has weight 1. 1399 The degree is the sum of the edge weights adjacent to the node. 1400 1401 Returns 1402 ------- 1403 If a single node is requested 1404 deg : int 1405 Degree of the node 1406 1407 OR if multiple nodes are requested 1408 nd_view : A DegreeView object capable of iterating (node, degree) pairs 1409 1410 Examples 1411 -------- 1412 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1413 >>> G.degree[0] # node 0 has degree 1 1414 1 1415 >>> list(G.degree([0, 1, 2])) 1416 [(0, 1), (1, 2), (2, 2)] 1417 """ 1418 return DegreeView(self) 1419 1420 def clear(self): 1421 """Remove all nodes and edges from the graph. 1422 1423 This also removes the name, and all graph, node, and edge attributes. 1424 1425 Examples 1426 -------- 1427 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1428 >>> G.clear() 1429 >>> list(G.nodes) 1430 [] 1431 >>> list(G.edges) 1432 [] 1433 1434 """ 1435 self._adj.clear() 1436 self._node.clear() 1437 self.graph.clear() 1438 1439 def clear_edges(self): 1440 """Remove all edges from the graph without altering nodes. 1441 1442 Examples 1443 -------- 1444 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1445 >>> G.clear_edges() 1446 >>> list(G.nodes) 1447 [0, 1, 2, 3] 1448 >>> list(G.edges) 1449 [] 1450 """ 1451 for neighbours_dict in self._adj.values(): 1452 neighbours_dict.clear() 1453 1454 def is_multigraph(self): 1455 """Returns True if graph is a multigraph, False otherwise.""" 1456 return False 1457 1458 def is_directed(self): 1459 """Returns True if graph is directed, False otherwise.""" 1460 return False 1461 1462 def copy(self, as_view=False): 1463 """Returns a copy of the graph. 1464 1465 The copy method by default returns an independent shallow copy 1466 of the graph and attributes. That is, if an attribute is a 1467 container, that container is shared by the original an the copy. 1468 Use Python's `copy.deepcopy` for new containers. 1469 1470 If `as_view` is True then a view is returned instead of a copy. 1471 1472 Notes 1473 ----- 1474 All copies reproduce the graph structure, but data attributes 1475 may be handled in different ways. There are four types of copies 1476 of a graph that people might want. 1477 1478 Deepcopy -- A "deepcopy" copies the graph structure as well as 1479 all data attributes and any objects they might contain. 1480 The entire graph object is new so that changes in the copy 1481 do not affect the original object. (see Python's copy.deepcopy) 1482 1483 Data Reference (Shallow) -- For a shallow copy the graph structure 1484 is copied but the edge, node and graph attribute dicts are 1485 references to those in the original graph. This saves 1486 time and memory but could cause confusion if you change an attribute 1487 in one graph and it changes the attribute in the other. 1488 NetworkX does not provide this level of shallow copy. 1489 1490 Independent Shallow -- This copy creates new independent attribute 1491 dicts and then does a shallow copy of the attributes. That is, any 1492 attributes that are containers are shared between the new graph 1493 and the original. This is exactly what `dict.copy()` provides. 1494 You can obtain this style copy using: 1495 1496 >>> G = nx.path_graph(5) 1497 >>> H = G.copy() 1498 >>> H = G.copy(as_view=False) 1499 >>> H = nx.Graph(G) 1500 >>> H = G.__class__(G) 1501 1502 Fresh Data -- For fresh data, the graph structure is copied while 1503 new empty data attribute dicts are created. The resulting graph 1504 is independent of the original and it has no edge, node or graph 1505 attributes. Fresh copies are not enabled. Instead use: 1506 1507 >>> H = G.__class__() 1508 >>> H.add_nodes_from(G) 1509 >>> H.add_edges_from(G.edges) 1510 1511 View -- Inspired by dict-views, graph-views act like read-only 1512 versions of the original graph, providing a copy of the original 1513 structure without requiring any memory for copying the information. 1514 1515 See the Python copy module for more information on shallow 1516 and deep copies, https://docs.python.org/3/library/copy.html. 1517 1518 Parameters 1519 ---------- 1520 as_view : bool, optional (default=False) 1521 If True, the returned graph-view provides a read-only view 1522 of the original graph without actually copying any data. 1523 1524 Returns 1525 ------- 1526 G : Graph 1527 A copy of the graph. 1528 1529 See Also 1530 -------- 1531 to_directed: return a directed copy of the graph. 1532 1533 Examples 1534 -------- 1535 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1536 >>> H = G.copy() 1537 1538 """ 1539 if as_view is True: 1540 return nx.graphviews.generic_graph_view(self) 1541 G = self.__class__() 1542 G.graph.update(self.graph) 1543 G.add_nodes_from((n, d.copy()) for n, d in self._node.items()) 1544 G.add_edges_from( 1545 (u, v, datadict.copy()) 1546 for u, nbrs in self._adj.items() 1547 for v, datadict in nbrs.items() 1548 ) 1549 return G 1550 1551 def to_directed(self, as_view=False): 1552 """Returns a directed representation of the graph. 1553 1554 Returns 1555 ------- 1556 G : DiGraph 1557 A directed graph with the same name, same nodes, and with 1558 each edge (u, v, data) replaced by two directed edges 1559 (u, v, data) and (v, u, data). 1560 1561 Notes 1562 ----- 1563 This returns a "deepcopy" of the edge, node, and 1564 graph attributes which attempts to completely copy 1565 all of the data and references. 1566 1567 This is in contrast to the similar D=DiGraph(G) which returns a 1568 shallow copy of the data. 1569 1570 See the Python copy module for more information on shallow 1571 and deep copies, https://docs.python.org/3/library/copy.html. 1572 1573 Warning: If you have subclassed Graph to use dict-like objects 1574 in the data structure, those changes do not transfer to the 1575 DiGraph created by this method. 1576 1577 Examples 1578 -------- 1579 >>> G = nx.Graph() # or MultiGraph, etc 1580 >>> G.add_edge(0, 1) 1581 >>> H = G.to_directed() 1582 >>> list(H.edges) 1583 [(0, 1), (1, 0)] 1584 1585 If already directed, return a (deep) copy 1586 1587 >>> G = nx.DiGraph() # or MultiDiGraph, etc 1588 >>> G.add_edge(0, 1) 1589 >>> H = G.to_directed() 1590 >>> list(H.edges) 1591 [(0, 1)] 1592 """ 1593 graph_class = self.to_directed_class() 1594 if as_view is True: 1595 return nx.graphviews.generic_graph_view(self, graph_class) 1596 # deepcopy when not a view 1597 G = graph_class() 1598 G.graph.update(deepcopy(self.graph)) 1599 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) 1600 G.add_edges_from( 1601 (u, v, deepcopy(data)) 1602 for u, nbrs in self._adj.items() 1603 for v, data in nbrs.items() 1604 ) 1605 return G 1606 1607 def to_undirected(self, as_view=False): 1608 """Returns an undirected copy of the graph. 1609 1610 Parameters 1611 ---------- 1612 as_view : bool (optional, default=False) 1613 If True return a view of the original undirected graph. 1614 1615 Returns 1616 ------- 1617 G : Graph/MultiGraph 1618 A deepcopy of the graph. 1619 1620 See Also 1621 -------- 1622 Graph, copy, add_edge, add_edges_from 1623 1624 Notes 1625 ----- 1626 This returns a "deepcopy" of the edge, node, and 1627 graph attributes which attempts to completely copy 1628 all of the data and references. 1629 1630 This is in contrast to the similar `G = nx.DiGraph(D)` which returns a 1631 shallow copy of the data. 1632 1633 See the Python copy module for more information on shallow 1634 and deep copies, https://docs.python.org/3/library/copy.html. 1635 1636 Warning: If you have subclassed DiGraph to use dict-like objects 1637 in the data structure, those changes do not transfer to the 1638 Graph created by this method. 1639 1640 Examples 1641 -------- 1642 >>> G = nx.path_graph(2) # or MultiGraph, etc 1643 >>> H = G.to_directed() 1644 >>> list(H.edges) 1645 [(0, 1), (1, 0)] 1646 >>> G2 = H.to_undirected() 1647 >>> list(G2.edges) 1648 [(0, 1)] 1649 """ 1650 graph_class = self.to_undirected_class() 1651 if as_view is True: 1652 return nx.graphviews.generic_graph_view(self, graph_class) 1653 # deepcopy when not a view 1654 G = graph_class() 1655 G.graph.update(deepcopy(self.graph)) 1656 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) 1657 G.add_edges_from( 1658 (u, v, deepcopy(d)) 1659 for u, nbrs in self._adj.items() 1660 for v, d in nbrs.items() 1661 ) 1662 return G 1663 1664 def subgraph(self, nodes): 1665 """Returns a SubGraph view of the subgraph induced on `nodes`. 1666 1667 The induced subgraph of the graph contains the nodes in `nodes` 1668 and the edges between those nodes. 1669 1670 Parameters 1671 ---------- 1672 nodes : list, iterable 1673 A container of nodes which will be iterated through once. 1674 1675 Returns 1676 ------- 1677 G : SubGraph View 1678 A subgraph view of the graph. The graph structure cannot be 1679 changed but node/edge attributes can and are shared with the 1680 original graph. 1681 1682 Notes 1683 ----- 1684 The graph, edge and node attributes are shared with the original graph. 1685 Changes to the graph structure is ruled out by the view, but changes 1686 to attributes are reflected in the original graph. 1687 1688 To create a subgraph with its own copy of the edge/node attributes use: 1689 G.subgraph(nodes).copy() 1690 1691 For an inplace reduction of a graph to a subgraph you can remove nodes: 1692 G.remove_nodes_from([n for n in G if n not in set(nodes)]) 1693 1694 Subgraph views are sometimes NOT what you want. In most cases where 1695 you want to do more than simply look at the induced edges, it makes 1696 more sense to just create the subgraph as its own graph with code like: 1697 1698 :: 1699 1700 # Create a subgraph SG based on a (possibly multigraph) G 1701 SG = G.__class__() 1702 SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc) 1703 if SG.is_multigraph(): 1704 SG.add_edges_from((n, nbr, key, d) 1705 for n, nbrs in G.adj.items() if n in largest_wcc 1706 for nbr, keydict in nbrs.items() if nbr in largest_wcc 1707 for key, d in keydict.items()) 1708 else: 1709 SG.add_edges_from((n, nbr, d) 1710 for n, nbrs in G.adj.items() if n in largest_wcc 1711 for nbr, d in nbrs.items() if nbr in largest_wcc) 1712 SG.graph.update(G.graph) 1713 1714 Examples 1715 -------- 1716 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1717 >>> H = G.subgraph([0, 1, 2]) 1718 >>> list(H.edges) 1719 [(0, 1), (1, 2)] 1720 """ 1721 induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes)) 1722 # if already a subgraph, don't make a chain 1723 subgraph = nx.graphviews.subgraph_view 1724 if hasattr(self, "_NODE_OK"): 1725 return subgraph(self._graph, induced_nodes, self._EDGE_OK) 1726 return subgraph(self, induced_nodes) 1727 1728 def edge_subgraph(self, edges): 1729 """Returns the subgraph induced by the specified edges. 1730 1731 The induced subgraph contains each edge in `edges` and each 1732 node incident to any one of those edges. 1733 1734 Parameters 1735 ---------- 1736 edges : iterable 1737 An iterable of edges in this graph. 1738 1739 Returns 1740 ------- 1741 G : Graph 1742 An edge-induced subgraph of this graph with the same edge 1743 attributes. 1744 1745 Notes 1746 ----- 1747 The graph, edge, and node attributes in the returned subgraph 1748 view are references to the corresponding attributes in the original 1749 graph. The view is read-only. 1750 1751 To create a full graph version of the subgraph with its own copy 1752 of the edge or node attributes, use:: 1753 1754 G.edge_subgraph(edges).copy() 1755 1756 Examples 1757 -------- 1758 >>> G = nx.path_graph(5) 1759 >>> H = G.edge_subgraph([(0, 1), (3, 4)]) 1760 >>> list(H.nodes) 1761 [0, 1, 3, 4] 1762 >>> list(H.edges) 1763 [(0, 1), (3, 4)] 1764 1765 """ 1766 return nx.edge_subgraph(self, edges) 1767 1768 def size(self, weight=None): 1769 """Returns the number of edges or total of all edge weights. 1770 1771 Parameters 1772 ---------- 1773 weight : string or None, optional (default=None) 1774 The edge attribute that holds the numerical value used 1775 as a weight. If None, then each edge has weight 1. 1776 1777 Returns 1778 ------- 1779 size : numeric 1780 The number of edges or 1781 (if weight keyword is provided) the total weight sum. 1782 1783 If weight is None, returns an int. Otherwise a float 1784 (or more general numeric if the weights are more general). 1785 1786 See Also 1787 -------- 1788 number_of_edges 1789 1790 Examples 1791 -------- 1792 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 1793 >>> G.size() 1794 3 1795 1796 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 1797 >>> G.add_edge("a", "b", weight=2) 1798 >>> G.add_edge("b", "c", weight=4) 1799 >>> G.size() 1800 2 1801 >>> G.size(weight="weight") 1802 6.0 1803 """ 1804 s = sum(d for v, d in self.degree(weight=weight)) 1805 # If `weight` is None, the sum of the degrees is guaranteed to be 1806 # even, so we can perform integer division and hence return an 1807 # integer. Otherwise, the sum of the weighted degrees is not 1808 # guaranteed to be an integer, so we perform "real" division. 1809 return s // 2 if weight is None else s / 2 1810 1811 def number_of_edges(self, u=None, v=None): 1812 """Returns the number of edges between two nodes. 1813 1814 Parameters 1815 ---------- 1816 u, v : nodes, optional (default=all edges) 1817 If u and v are specified, return the number of edges between 1818 u and v. Otherwise return the total number of all edges. 1819 1820 Returns 1821 ------- 1822 nedges : int 1823 The number of edges in the graph. If nodes `u` and `v` are 1824 specified return the number of edges between those nodes. If 1825 the graph is directed, this only returns the number of edges 1826 from `u` to `v`. 1827 1828 See Also 1829 -------- 1830 size 1831 1832 Examples 1833 -------- 1834 For undirected graphs, this method counts the total number of 1835 edges in the graph: 1836 1837 >>> G = nx.path_graph(4) 1838 >>> G.number_of_edges() 1839 3 1840 1841 If you specify two nodes, this counts the total number of edges 1842 joining the two nodes: 1843 1844 >>> G.number_of_edges(0, 1) 1845 1 1846 1847 For directed graphs, this method can count the total number of 1848 directed edges from `u` to `v`: 1849 1850 >>> G = nx.DiGraph() 1851 >>> G.add_edge(0, 1) 1852 >>> G.add_edge(1, 0) 1853 >>> G.number_of_edges(0, 1) 1854 1 1855 1856 """ 1857 if u is None: 1858 return int(self.size()) 1859 if v in self._adj[u]: 1860 return 1 1861 return 0 1862 1863 def nbunch_iter(self, nbunch=None): 1864 """Returns an iterator over nodes contained in nbunch that are 1865 also in the graph. 1866 1867 The nodes in nbunch are checked for membership in the graph 1868 and if not are silently ignored. 1869 1870 Parameters 1871 ---------- 1872 nbunch : single node, container, or all nodes (default= all nodes) 1873 The view will only report edges incident to these nodes. 1874 1875 Returns 1876 ------- 1877 niter : iterator 1878 An iterator over nodes in nbunch that are also in the graph. 1879 If nbunch is None, iterate over all nodes in the graph. 1880 1881 Raises 1882 ------ 1883 NetworkXError 1884 If nbunch is not a node or sequence of nodes. 1885 If a node in nbunch is not hashable. 1886 1887 See Also 1888 -------- 1889 Graph.__iter__ 1890 1891 Notes 1892 ----- 1893 When nbunch is an iterator, the returned iterator yields values 1894 directly from nbunch, becoming exhausted when nbunch is exhausted. 1895 1896 To test whether nbunch is a single node, one can use 1897 "if nbunch in self:", even after processing with this routine. 1898 1899 If nbunch is not a node or a (possibly empty) sequence/iterator 1900 or None, a :exc:`NetworkXError` is raised. Also, if any object in 1901 nbunch is not hashable, a :exc:`NetworkXError` is raised. 1902 """ 1903 if nbunch is None: # include all nodes via iterator 1904 bunch = iter(self._adj) 1905 elif nbunch in self: # if nbunch is a single node 1906 bunch = iter([nbunch]) 1907 else: # if nbunch is a sequence of nodes 1908 1909 def bunch_iter(nlist, adj): 1910 try: 1911 for n in nlist: 1912 if n in adj: 1913 yield n 1914 except TypeError as e: 1915 exc, message = e, e.args[0] 1916 # capture error for non-sequence/iterator nbunch. 1917 if "iter" in message: 1918 exc = NetworkXError( 1919 "nbunch is not a node or a sequence of nodes." 1920 ) 1921 # capture error for unhashable node. 1922 if "hashable" in message: 1923 exc = NetworkXError( 1924 f"Node {n} in sequence nbunch is not a valid node." 1925 ) 1926 raise exc 1927 1928 bunch = bunch_iter(nbunch, self._adj) 1929 return bunch 1930