Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/classes/digraph.py: 50%

1"""Base class for directed graphs.""" 

2 

3from copy import deepcopy 

4from functools import cached_property 

5 

6import networkx as nx 

7from networkx import convert 

8from networkx.classes.coreviews import AdjacencyView 

9from networkx.classes.graph import Graph 

10from networkx.classes.reportviews import ( 

11 DiDegreeView, 

12 InDegreeView, 

13 InEdgeView, 

14 OutDegreeView, 

15 OutEdgeView, 

16) 

17from networkx.exception import NetworkXError 

18 

19__all__ = ["DiGraph"] 

20 

21 

22class _CachedPropertyResetterAdjAndSucc: 

23 """Data Descriptor class that syncs and resets cached properties adj and succ 

24 

25 The cached properties `adj` and `succ` are reset whenever `_adj` or `_succ` 

26 are set to new objects. In addition, the attributes `_succ` and `_adj` 

27 are synced so these two names point to the same object. 

28 

29 Warning: most of the time, when ``G._adj`` is set, ``G._pred`` should also 

30 be set to maintain a valid data structure. They share datadicts. 

31 

32 This object sits on a class and ensures that any instance of that 

33 class clears its cached properties "succ" and "adj" whenever the 

34 underlying instance attributes "_succ" or "_adj" are set to a new object. 

35 It only affects the set process of the obj._adj and obj._succ attribute. 

36 All get/del operations act as they normally would. 

37 

38 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html 

39 """ 

40 

41 def __set__(self, obj, value): 

42 od = obj.__dict__ 

43 od["_adj"] = value 

44 od["_succ"] = value 

45 # reset cached properties 

46 props = [ 

47 "adj", 

48 "succ", 

49 "edges", 

50 "out_edges", 

51 "degree", 

52 "out_degree", 

53 "in_degree", 

54 ] 

55 for prop in props: 

56 if prop in od: 

57 del od[prop] 

58 

59 

60class _CachedPropertyResetterPred: 

61 """Data Descriptor class for _pred that resets ``pred`` cached_property when needed 

62 

63 This assumes that the ``cached_property`` ``G.pred`` should be reset whenever 

64 ``G._pred`` is set to a new value. 

65 

66 Warning: most of the time, when ``G._pred`` is set, ``G._adj`` should also 

67 be set to maintain a valid data structure. They share datadicts. 

68 

69 This object sits on a class and ensures that any instance of that 

70 class clears its cached property "pred" whenever the underlying 

71 instance attribute "_pred" is set to a new object. It only affects 

72 the set process of the obj._pred attribute. All get/del operations 

73 act as they normally would. 

74 

75 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html 

76 """ 

77 

78 def __set__(self, obj, value): 

79 od = obj.__dict__ 

80 od["_pred"] = value 

81 # reset cached properties 

82 props = ["pred", "in_edges", "degree", "out_degree", "in_degree"] 

83 for prop in props: 

84 if prop in od: 

85 del od[prop] 

86 

87 

88class DiGraph(Graph): 

89 """ 

90 Base class for directed graphs. 

91 

92 A DiGraph stores nodes and edges with optional data, or attributes. 

93 

94 DiGraphs hold directed edges. Self loops are allowed but multiple 

95 (parallel) edges are not. 

96 

97 Nodes can be arbitrary (hashable) Python objects with optional 

98 key/value attributes. By convention `None` is not used as a node. 

99 

100 Edges are represented as links between nodes with optional 

101 key/value attributes. 

102 

103 Parameters 

104 ---------- 

105 incoming_graph_data : input graph (optional, default: None) 

106 Data to initialize graph. If None (default) an empty 

107 graph is created. The data can be any format that is supported 

108 by the to_networkx_graph() function, currently including edge list, 

109 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array, SciPy 

110 sparse matrix, or PyGraphviz graph. 

111 

112 attr : keyword arguments, optional (default= no attributes) 

113 Attributes to add to graph as key=value pairs. 

114 

115 See Also 

116 -------- 

117 Graph 

118 MultiGraph 

119 MultiDiGraph 

120 

121 Examples 

122 -------- 

123 Create an empty graph structure (a "null graph") with no nodes and 

124 no edges. 

125 

126 >>> G = nx.DiGraph() 

127 

128 G can be grown in several ways. 

129 

130 **Nodes:** 

131 

132 Add one node at a time: 

133 

134 >>> G.add_node(1) 

135 

136 Add the nodes from any container (a list, dict, set or 

137 even the lines from a file or the nodes from another graph). 

138 

139 >>> G.add_nodes_from([2, 3]) 

140 >>> G.add_nodes_from(range(100, 110)) 

141 >>> H = nx.path_graph(10) 

142 >>> G.add_nodes_from(H) 

143 

144 In addition to strings and integers any hashable Python object 

145 (except None) can represent a node, e.g. a customized node object, 

146 or even another Graph. 

147 

148 >>> G.add_node(H) 

149 

150 **Edges:** 

151 

152 G can also be grown by adding edges. 

153 

154 Add one edge, 

155 

156 >>> G.add_edge(1, 2) 

157 

158 a list of edges, 

159 

160 >>> G.add_edges_from([(1, 2), (1, 3)]) 

161 

162 or a collection of edges, 

163 

164 >>> G.add_edges_from(H.edges) 

165 

166 If some edges connect nodes not yet in the graph, the nodes 

167 are added automatically. There are no errors when adding 

168 nodes or edges that already exist. 

169 

170 **Attributes:** 

171 

172 Each graph, node, and edge can hold key/value attribute pairs 

173 in an associated attribute dictionary (the keys must be hashable). 

174 By default these are empty, but can be added or changed using 

175 add_edge, add_node or direct manipulation of the attribute 

176 dictionaries named graph, node and edge respectively. 

177 

178 >>> G = nx.DiGraph(day="Friday") 

179 >>> G.graph 

180 {'day': 'Friday'} 

181 

182 Add node attributes using add_node(), add_nodes_from() or G.nodes 

183 

184 >>> G.add_node(1, time="5pm") 

185 >>> G.add_nodes_from([3], time="2pm") 

186 >>> G.nodes[1] 

187 {'time': '5pm'} 

188 >>> G.nodes[1]["room"] = 714 

189 >>> del G.nodes[1]["room"] # remove attribute 

190 >>> list(G.nodes(data=True)) 

191 [(1, {'time': '5pm'}), (3, {'time': '2pm'})] 

192 

193 Add edge attributes using add_edge(), add_edges_from(), subscript 

194 notation, or G.edges. 

195 

196 >>> G.add_edge(1, 2, weight=4.7) 

197 >>> G.add_edges_from([(3, 4), (4, 5)], color="red") 

198 >>> G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})]) 

199 >>> G[1][2]["weight"] = 4.7 

200 >>> G.edges[1, 2]["weight"] = 4 

201 

202 Warning: we protect the graph data structure by making `G.edges[1, 2]` a 

203 read-only dict-like structure. However, you can assign to attributes 

204 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change 

205 data attributes: `G.edges[1, 2]['weight'] = 4` 

206 (For multigraphs: `MG.edges[u, v, key][name] = value`). 

207 

208 **Shortcuts:** 

209 

210 Many common graph features allow python syntax to speed reporting. 

211 

212 >>> 1 in G # check if node in graph 

213 True 

214 >>> [n for n in G if n < 3] # iterate through nodes 

215 [1, 2] 

216 >>> len(G) # number of nodes in graph 

217 5 

218 

219 Often the best way to traverse all edges of a graph is via the neighbors. 

220 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()` 

221 

222 >>> for n, nbrsdict in G.adjacency(): 

223 ... for nbr, eattr in nbrsdict.items(): 

224 ... if "weight" in eattr: 

225 ... # Do something useful with the edges 

226 ... pass 

227 

228 But the edges reporting object is often more convenient: 

229 

230 >>> for u, v, weight in G.edges(data="weight"): 

231 ... if weight is not None: 

232 ... # Do something useful with the edges 

233 ... pass 

234 

235 **Reporting:** 

236 

237 Simple graph information is obtained using object-attributes and methods. 

238 Reporting usually provides views instead of containers to reduce memory 

239 usage. The views update as the graph is updated similarly to dict-views. 

240 The objects `nodes`, `edges` and `adj` provide access to data attributes 

241 via lookup (e.g. `nodes[n]`, `edges[u, v]`, `adj[u][v]`) and iteration 

242 (e.g. `nodes.items()`, `nodes.data('color')`, 

243 `nodes.data('color', default='blue')` and similarly for `edges`) 

244 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`. 

245 

246 For details on these and other miscellaneous methods, see below. 

247 

248 **Subclasses (Advanced):** 

249 

250 The Graph class uses a dict-of-dict-of-dict data structure. 

251 The outer dict (node_dict) holds adjacency information keyed by node. 

252 The next dict (adjlist_dict) represents the adjacency information and holds 

253 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents 

254 the edge data and holds edge attribute values keyed by attribute names. 

255 

256 Each of these three dicts can be replaced in a subclass by a user defined 

257 dict-like object. In general, the dict-like features should be 

258 maintained but extra features can be added. To replace one of the 

259 dicts create a new graph class by changing the class(!) variable 

260 holding the factory for that dict-like structure. The variable names are 

261 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory, 

262 adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory. 

263 

264 node_dict_factory : function, (default: dict) 

265 Factory function to be used to create the dict containing node 

266 attributes, keyed by node id. 

267 It should require no arguments and return a dict-like object 

268 

269 node_attr_dict_factory: function, (default: dict) 

270 Factory function to be used to create the node attribute 

271 dict which holds attribute values keyed by attribute name. 

272 It should require no arguments and return a dict-like object 

273 

274 adjlist_outer_dict_factory : function, (default: dict) 

275 Factory function to be used to create the outer-most dict 

276 in the data structure that holds adjacency info keyed by node. 

277 It should require no arguments and return a dict-like object. 

278 

279 adjlist_inner_dict_factory : function, optional (default: dict) 

280 Factory function to be used to create the adjacency list 

281 dict which holds edge data keyed by neighbor. 

282 It should require no arguments and return a dict-like object 

283 

284 edge_attr_dict_factory : function, optional (default: dict) 

285 Factory function to be used to create the edge attribute 

286 dict which holds attribute values keyed by attribute name. 

287 It should require no arguments and return a dict-like object. 

288 

289 graph_attr_dict_factory : function, (default: dict) 

290 Factory function to be used to create the graph attribute 

291 dict which holds attribute values keyed by attribute name. 

292 It should require no arguments and return a dict-like object. 

293 

294 Typically, if your extension doesn't impact the data structure all 

295 methods will inherited without issue except: `to_directed/to_undirected`. 

296 By default these methods create a DiGraph/Graph class and you probably 

297 want them to create your extension of a DiGraph/Graph. To facilitate 

298 this we define two class variables that you can set in your subclass. 

299 

300 to_directed_class : callable, (default: DiGraph or MultiDiGraph) 

301 Class to create a new graph structure in the `to_directed` method. 

302 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used. 

303 

304 to_undirected_class : callable, (default: Graph or MultiGraph) 

305 Class to create a new graph structure in the `to_undirected` method. 

306 If `None`, a NetworkX class (Graph or MultiGraph) is used. 

307 

308 **Subclassing Example** 

309 

310 Create a low memory graph class that effectively disallows edge 

311 attributes by using a single attribute dict for all edges. 

312 This reduces the memory used, but you lose edge attributes. 

313 

314 >>> class ThinGraph(nx.Graph): 

315 ... all_edge_dict = {"weight": 1} 

316 ... 

317 ... def single_edge_dict(self): 

318 ... return self.all_edge_dict 

319 ... 

320 ... edge_attr_dict_factory = single_edge_dict 

321 >>> G = ThinGraph() 

322 >>> G.add_edge(2, 1) 

323 >>> G[2][1] 

324 {'weight': 1} 

325 >>> G.add_edge(2, 2) 

326 >>> G[2][1] is G[2][2] 

327 True 

328 """ 

329 

330 _adj = _CachedPropertyResetterAdjAndSucc() # type: ignore[assignment] 

331 _succ = _adj # type: ignore[has-type] 

332 _pred = _CachedPropertyResetterPred() 

333 

334 # This __new__ method just does what Python itself does automatically. 

335 # We include it here as part of the dispatchable/backend interface. 

336 # If your goal is to understand how the graph classes work, you can ignore 

337 # this method, even when subclassing the base classes. If you are subclassing 

338 # in order to provide a backend that allows class instantiation, this method 

339 # can be overridden to return your own backend graph class. 

340 @nx._dispatchable(name="digraph__new__", graphs=None, returns_graph=True) 

341 def __new__(cls, incoming_graph_data=None, **attr): 

342 return object.__new__(cls) 

343 

344 def __init__(self, incoming_graph_data=None, **attr): 

345 """Initialize a graph with edges, name, or graph attributes. 

346 

347 Parameters 

348 ---------- 

349 incoming_graph_data : input graph (optional, default: None) 

350 Data to initialize graph. If None (default) an empty 

351 graph is created. The data can be an edge list, or any 

352 NetworkX graph object. If the corresponding optional Python 

353 packages are installed the data can also be a 2D NumPy array, a 

354 SciPy sparse array, or a PyGraphviz graph. 

355 

356 attr : keyword arguments, optional (default= no attributes) 

357 Attributes to add to graph as key=value pairs. 

358 

359 See Also 

360 -------- 

361 convert 

362 

363 Examples 

364 -------- 

365 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 

366 >>> G = nx.Graph(name="my graph") 

367 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges 

368 >>> G = nx.Graph(e) 

369 

370 Arbitrary graph attribute pairs (key=value) may be assigned 

371 

372 >>> G = nx.Graph(e, day="Friday") 

373 >>> G.graph 

374 {'day': 'Friday'} 

375 

376 """ 

377 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes 

378 self._node = self.node_dict_factory() # dictionary for node attr 

379 # We store two adjacency lists: 

380 # the predecessors of node n are stored in the dict self._pred 

381 # the successors of node n are stored in the dict self._succ=self._adj 

382 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict successor 

383 self._pred = self.adjlist_outer_dict_factory() # predecessor 

384 # Note: self._succ = self._adj # successor 

385 

386 self.__networkx_cache__ = {} 

387 # attempt to load graph with data 

388 if incoming_graph_data is not None: 

389 convert.to_networkx_graph(incoming_graph_data, create_using=self) 

390 # load graph attributes (must be after convert) 

391 attr.pop("backend", None) # Ignore explicit `backend="networkx"` 

392 self.graph.update(attr) 

393 

394 @cached_property 

395 def adj(self): 

396 """Graph adjacency object holding the neighbors of each node. 

397 

398 This object is a read-only dict-like structure with node keys 

399 and neighbor-dict values. The neighbor-dict is keyed by neighbor 

400 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets 

401 the color of the edge `(3, 2)` to `"blue"`. 

402 

403 Iterating over G.adj behaves like a dict. Useful idioms include 

404 `for nbr, datadict in G.adj[n].items():`. 

405 

406 The neighbor information is also provided by subscripting the graph. 

407 So `for nbr, foovalue in G[node].data('foo', default=1):` works. 

408 

409 For directed graphs, `G.adj` holds outgoing (successor) info. 

410 """ 

411 return AdjacencyView(self._succ) 

412 

413 @cached_property 

414 def succ(self): 

415 """Graph adjacency object holding the successors of each node. 

416 

417 This object is a read-only dict-like structure with node keys 

418 and neighbor-dict values. The neighbor-dict is keyed by neighbor 

419 to the edge-data-dict. So `G.succ[3][2]['color'] = 'blue'` sets 

420 the color of the edge `(3, 2)` to `"blue"`. 

421 

422 Iterating over G.succ behaves like a dict. Useful idioms include 

423 `for nbr, datadict in G.succ[n].items():`. A data-view not provided 

424 by dicts also exists: `for nbr, foovalue in G.succ[node].data('foo'):` 

425 and a default can be set via a `default` argument to the `data` method. 

426 

427 The neighbor information is also provided by subscripting the graph. 

428 So `for nbr, foovalue in G[node].data('foo', default=1):` works. 

429 

430 For directed graphs, `G.adj` is identical to `G.succ`. 

431 """ 

432 return AdjacencyView(self._succ) 

433 

434 @cached_property 

435 def pred(self): 

436 """Graph adjacency object holding the predecessors of each node. 

437 

438 This object is a read-only dict-like structure with node keys 

439 and neighbor-dict values. The neighbor-dict is keyed by neighbor 

440 to the edge-data-dict. So `G.pred[2][3]['color'] = 'blue'` sets 

441 the color of the edge `(3, 2)` to `"blue"`. 

442 

443 Iterating over G.pred behaves like a dict. Useful idioms include 

444 `for nbr, datadict in G.pred[n].items():`. A data-view not provided 

445 by dicts also exists: `for nbr, foovalue in G.pred[node].data('foo'):` 

446 A default can be set via a `default` argument to the `data` method. 

447 """ 

448 return AdjacencyView(self._pred) 

449 

450 def add_node(self, node_for_adding, **attr): 

451 """Add a single node `node_for_adding` and update node attributes. 

452 

453 Parameters 

454 ---------- 

455 node_for_adding : node 

456 A node can be any hashable Python object except None. 

457 attr : keyword arguments, optional 

458 Set or change node attributes using key=value. 

459 

460 See Also 

461 -------- 

462 add_nodes_from 

463 

464 Examples 

465 -------- 

466 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 

467 >>> G.add_node(1) 

468 >>> G.add_node("Hello") 

469 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) 

470 >>> G.add_node(K3) 

471 >>> G.number_of_nodes() 

472 3 

473 

474 Use keywords set/change node attributes: 

475 

476 >>> G.add_node(1, size=10) 

477 >>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649)) 

478 

479 Notes 

480 ----- 

481 A hashable object is one that can be used as a key in a Python 

482 dictionary. This includes strings, numbers, tuples of strings 

483 and numbers, etc. 

484 

485 On many platforms hashable items also include mutables such as 

486 NetworkX Graphs, though one should be careful that the hash 

487 doesn't change on mutables. 

488 """ 

489 if node_for_adding not in self._succ: 

490 if node_for_adding is None: 

491 raise ValueError("None cannot be a node") 

492 self._succ[node_for_adding] = self.adjlist_inner_dict_factory() 

493 self._pred[node_for_adding] = self.adjlist_inner_dict_factory() 

494 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory() 

495 attr_dict.update(attr) 

496 else: # update attr even if node already exists 

497 self._node[node_for_adding].update(attr) 

498 nx._clear_cache(self) 

499 

500 def add_nodes_from(self, nodes_for_adding, **attr): 

501 """Add multiple nodes. 

502 

503 Parameters 

504 ---------- 

505 nodes_for_adding : iterable container 

506 A container of nodes (list, dict, set, etc.). 

507 OR 

508 A container of (node, attribute dict) tuples. 

509 Node attributes are updated using the attribute dict. 

510 attr : keyword arguments, optional (default= no attributes) 

511 Update attributes for all nodes in nodes. 

512 Node attributes specified in nodes as a tuple take 

513 precedence over attributes specified via keyword arguments. 

514 

515 See Also 

516 -------- 

517 add_node 

518 

519 Notes 

520 ----- 

521 When adding nodes from an iterator over the graph you are changing, 

522 a `RuntimeError` can be raised with message: 

523 `RuntimeError: dictionary changed size during iteration`. This 

524 happens when the graph's underlying dictionary is modified during 

525 iteration. To avoid this error, evaluate the iterator into a separate 

526 object, e.g. by using `list(iterator_of_nodes)`, and pass this 

527 object to `G.add_nodes_from`. 

528 

529 Examples 

530 -------- 

531 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 

532 >>> G.add_nodes_from("Hello") 

533 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) 

534 >>> G.add_nodes_from(K3) 

535 >>> sorted(G.nodes(), key=str) 

536 [0, 1, 2, 'H', 'e', 'l', 'o'] 

537 

538 Use keywords to update specific node attributes for every node. 

539 

540 >>> G.add_nodes_from([1, 2], size=10) 

541 >>> G.add_nodes_from([3, 4], weight=0.4) 

542 

543 Use (node, attrdict) tuples to update attributes for specific nodes. 

544 

545 >>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})]) 

546 >>> G.nodes[1]["size"] 

547 11 

548 >>> H = nx.Graph() 

549 >>> H.add_nodes_from(G.nodes(data=True)) 

550 >>> H.nodes[1]["size"] 

551 11 

552 

553 Evaluate an iterator over a graph if using it to modify the same graph 

554 

555 >>> G = nx.DiGraph([(0, 1), (1, 2), (3, 4)]) 

556 >>> # wrong way - will raise RuntimeError 

557 >>> # G.add_nodes_from(n + 1 for n in G.nodes) 

558 >>> # correct way 

559 >>> G.add_nodes_from(list(n + 1 for n in G.nodes)) 

560 """ 

561 for n in nodes_for_adding: 

562 try: 

563 newnode = n not in self._node 

564 newdict = attr 

565 except TypeError: 

566 n, ndict = n 

567 newnode = n not in self._node 

568 newdict = attr.copy() 

569 newdict.update(ndict) 

570 if newnode: 

571 if n is None: 

572 raise ValueError("None cannot be a node") 

573 self._succ[n] = self.adjlist_inner_dict_factory() 

574 self._pred[n] = self.adjlist_inner_dict_factory() 

575 self._node[n] = self.node_attr_dict_factory() 

576 self._node[n].update(newdict) 

577 nx._clear_cache(self) 

578 

579 def remove_node(self, n): 

580 """Remove node n. 

581 

582 Removes the node n and all adjacent edges. 

583 Attempting to remove a nonexistent node will raise an exception. 

584 

585 Parameters 

586 ---------- 

587 n : node 

588 A node in the graph 

589 

590 Raises 

591 ------ 

592 NetworkXError 

593 If n is not in the graph. 

594 

595 See Also 

596 -------- 

597 remove_nodes_from 

598 

599 Examples 

600 -------- 

601 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 

602 >>> list(G.edges) 

603 [(0, 1), (1, 2)] 

604 >>> G.remove_node(1) 

605 >>> list(G.edges) 

606 [] 

607 

608 """ 

609 try: 

610 nbrs = self._succ[n] 

611 del self._node[n] 

612 except KeyError as err: # NetworkXError if n not in self 

613 raise NetworkXError(f"The node {n} is not in the digraph.") from err 

614 for u in nbrs: 

615 del self._pred[u][n] # remove all edges n-u in digraph 

616 del self._succ[n] # remove node from succ 

617 for u in self._pred[n]: 

618 del self._succ[u][n] # remove all edges n-u in digraph 

619 del self._pred[n] # remove node from pred 

620 nx._clear_cache(self) 

621 

622 def remove_nodes_from(self, nodes): 

623 """Remove multiple nodes. 

624 

625 Parameters 

626 ---------- 

627 nodes : iterable container 

628 A container of nodes (list, dict, set, etc.). If a node 

629 in the container is not in the graph it is silently ignored. 

630 

631 See Also 

632 -------- 

633 remove_node 

634 

635 Notes 

636 ----- 

637 When removing nodes from an iterator over the graph you are changing, 

638 a `RuntimeError` will be raised with message: 

639 `RuntimeError: dictionary changed size during iteration`. This 

640 happens when the graph's underlying dictionary is modified during 

641 iteration. To avoid this error, evaluate the iterator into a separate 

642 object, e.g. by using `list(iterator_of_nodes)`, and pass this 

643 object to `G.remove_nodes_from`. 

644 

645 Examples 

646 -------- 

647 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc 

648 >>> e = list(G.nodes) 

649 >>> e 

650 [0, 1, 2] 

651 >>> G.remove_nodes_from(e) 

652 >>> list(G.nodes) 

653 [] 

654 

655 Evaluate an iterator over a graph if using it to modify the same graph 

656 

657 >>> G = nx.DiGraph([(0, 1), (1, 2), (3, 4)]) 

658 >>> # this command will fail, as the graph's dict is modified during iteration 

659 >>> # G.remove_nodes_from(n for n in G.nodes if n < 2) 

660 >>> # this command will work, since the dictionary underlying graph is not modified 

661 >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2)) 

662 """ 

663 for n in nodes: 

664 try: 

665 succs = self._succ[n] 

666 del self._node[n] 

667 for u in succs: 

668 del self._pred[u][n] # remove all edges n-u in digraph 

669 del self._succ[n] # now remove node 

670 for u in self._pred[n]: 

671 del self._succ[u][n] # remove all edges n-u in digraph 

672 del self._pred[n] # now remove node 

673 except KeyError: 

674 pass # silent failure on remove 

675 nx._clear_cache(self) 

676 

677 def add_edge(self, u_of_edge, v_of_edge, **attr): 

678 """Add an edge between u and v. 

679 

680 The nodes u and v will be automatically added if they are 

681 not already in the graph. 

682 

683 Edge attributes can be specified with keywords or by directly 

684 accessing the edge's attribute dictionary. See examples below. 

685 

686 Parameters 

687 ---------- 

688 u_of_edge, v_of_edge : nodes 

689 Nodes can be, for example, strings or numbers. 

690 Nodes must be hashable (and not None) Python objects. 

691 attr : keyword arguments, optional 

692 Edge data (or labels or objects) can be assigned using 

693 keyword arguments. 

694 

695 See Also 

696 -------- 

697 add_edges_from : add a collection of edges 

698 

699 Notes 

700 ----- 

701 Adding an edge that already exists updates the edge data. 

702 

703 Many NetworkX algorithms designed for weighted graphs use 

704 an edge attribute (by default `weight`) to hold a numerical value. 

705 

706 Examples 

707 -------- 

708 The following all add the edge e=(1, 2) to graph G: 

709 

710 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 

711 >>> e = (1, 2) 

712 >>> G.add_edge(1, 2) # explicit two-node form 

713 >>> G.add_edge(*e) # single edge as tuple of two nodes 

714 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container 

715 

716 Associate data to edges using keywords: 

717 

718 >>> G.add_edge(1, 2, weight=3) 

719 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7) 

720 

721 For non-string attribute keys, use subscript notation. 

722 

723 >>> G.add_edge(1, 2) 

724 >>> G[1][2].update({0: 5}) 

725 >>> G.edges[1, 2].update({0: 5}) 

726 """ 

727 u, v = u_of_edge, v_of_edge 

728 # add nodes 

729 if u not in self._succ: 

730 if u is None: 

731 raise ValueError("None cannot be a node") 

732 self._succ[u] = self.adjlist_inner_dict_factory() 

733 self._pred[u] = self.adjlist_inner_dict_factory() 

734 self._node[u] = self.node_attr_dict_factory() 

735 if v not in self._succ: 

736 if v is None: 

737 raise ValueError("None cannot be a node") 

738 self._succ[v] = self.adjlist_inner_dict_factory() 

739 self._pred[v] = self.adjlist_inner_dict_factory() 

740 self._node[v] = self.node_attr_dict_factory() 

741 # add the edge 

742 datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) 

743 datadict.update(attr) 

744 self._succ[u][v] = datadict 

745 self._pred[v][u] = datadict 

746 nx._clear_cache(self) 

747 

748 def add_edges_from(self, ebunch_to_add, **attr): 

749 """Add all the edges in ebunch_to_add. 

750 

751 Parameters 

752 ---------- 

753 ebunch_to_add : container of edges 

754 Each edge given in the container will be added to the 

755 graph. The edges must be given as 2-tuples (u, v) or 

756 3-tuples (u, v, d) where d is a dictionary containing edge data. 

757 attr : keyword arguments, optional 

758 Edge data (or labels or objects) can be assigned using 

759 keyword arguments. 

760 

761 See Also 

762 -------- 

763 add_edge : add a single edge 

764 add_weighted_edges_from : convenient way to add weighted edges 

765 

766 Notes 

767 ----- 

768 Adding the same edge twice has no effect but any edge data 

769 will be updated when each duplicate edge is added. 

770 

771 Edge attributes specified in an ebunch take precedence over 

772 attributes specified via keyword arguments. 

773 

774 When adding edges from an iterator over the graph you are changing, 

775 a `RuntimeError` can be raised with message: 

776 `RuntimeError: dictionary changed size during iteration`. This 

777 happens when the graph's underlying dictionary is modified during 

778 iteration. To avoid this error, evaluate the iterator into a separate 

779 object, e.g. by using `list(iterator_of_edges)`, and pass this 

780 object to `G.add_edges_from`. 

781 

782 Examples 

783 -------- 

784 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 

785 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples 

786 >>> e = zip(range(0, 3), range(1, 4)) 

787 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3 

788 

789 Associate data to edges 

790 

791 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3) 

792 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898") 

793 

794 Evaluate an iterator over a graph if using it to modify the same graph 

795 

796 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4)]) 

797 >>> # Grow graph by one new node, adding edges to all existing nodes. 

798 >>> # wrong way - will raise RuntimeError 

799 >>> # G.add_edges_from(((5, n) for n in G.nodes)) 

800 >>> # right way - note that there will be no self-edge for node 5 

801 >>> G.add_edges_from(list((5, n) for n in G.nodes)) 

802 """ 

803 for e in ebunch_to_add: 

804 ne = len(e) 

805 if ne == 3: 

806 u, v, dd = e 

807 elif ne == 2: 

808 u, v = e 

809 dd = {} 

810 else: 

811 raise NetworkXError(f"Edge tuple {e} must be a 2-tuple or 3-tuple.") 

812 if u not in self._succ: 

813 if u is None: 

814 raise ValueError("None cannot be a node") 

815 self._succ[u] = self.adjlist_inner_dict_factory() 

816 self._pred[u] = self.adjlist_inner_dict_factory() 

817 self._node[u] = self.node_attr_dict_factory() 

818 if v not in self._succ: 

819 if v is None: 

820 raise ValueError("None cannot be a node") 

821 self._succ[v] = self.adjlist_inner_dict_factory() 

822 self._pred[v] = self.adjlist_inner_dict_factory() 

823 self._node[v] = self.node_attr_dict_factory() 

824 datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) 

825 datadict.update(attr) 

826 datadict.update(dd) 

827 self._succ[u][v] = datadict 

828 self._pred[v][u] = datadict 

829 nx._clear_cache(self) 

830 

831 def remove_edge(self, u, v): 

832 """Remove the edge between u and v. 

833 

834 Parameters 

835 ---------- 

836 u, v : nodes 

837 Remove the edge between nodes u and v. 

838 

839 Raises 

840 ------ 

841 NetworkXError 

842 If there is not an edge between u and v. 

843 

844 See Also 

845 -------- 

846 remove_edges_from : remove a collection of edges 

847 

848 Examples 

849 -------- 

850 >>> G = nx.Graph() # or DiGraph, etc 

851 >>> nx.add_path(G, [0, 1, 2, 3]) 

852 >>> G.remove_edge(0, 1) 

853 >>> e = (1, 2) 

854 >>> G.remove_edge(*e) # unpacks e from an edge tuple 

855 >>> e = (2, 3, {"weight": 7}) # an edge with attribute data 

856 >>> G.remove_edge(*e[:2]) # select first part of edge tuple 

857 """ 

858 try: 

859 del self._succ[u][v] 

860 del self._pred[v][u] 

861 except KeyError as err: 

862 raise NetworkXError(f"The edge {u}-{v} not in graph.") from err 

863 nx._clear_cache(self) 

864 

865 def remove_edges_from(self, ebunch): 

866 """Remove all edges specified in ebunch. 

867 

868 Parameters 

869 ---------- 

870 ebunch: list or container of edge tuples 

871 Each edge given in the list or container will be removed 

872 from the graph. The edges can be: 

873 

874 - 2-tuples (u, v) edge between u and v. 

875 - 3-tuples (u, v, k) where k is ignored. 

876 

877 See Also 

878 -------- 

879 remove_edge : remove a single edge 

880 

881 Notes 

882 ----- 

883 Will fail silently if an edge in ebunch is not in the graph. 

884 

885 Examples 

886 -------- 

887 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc 

888 >>> ebunch = [(1, 2), (2, 3)] 

889 >>> G.remove_edges_from(ebunch) 

890 """ 

891 for e in ebunch: 

892 u, v = e[:2] # ignore edge data 

893 if u in self._succ and v in self._succ[u]: 

894 del self._succ[u][v] 

895 del self._pred[v][u] 

896 nx._clear_cache(self) 

897 

898 def has_successor(self, u, v): 

899 """Returns True if node u has successor v. 

900 

901 This is true if graph has the edge u->v. 

902 """ 

903 return u in self._succ and v in self._succ[u] 

904 

905 def has_predecessor(self, u, v): 

906 """Returns True if node u has predecessor v. 

907 

908 This is true if graph has the edge u<-v. 

909 """ 

910 return u in self._pred and v in self._pred[u] 

911 

912 def successors(self, n): 

913 """Returns an iterator over successor nodes of n. 

914 

915 A successor of n is a node m such that there exists a directed 

916 edge from n to m. 

917 

918 Parameters 

919 ---------- 

920 n : node 

921 A node in the graph 

922 

923 Raises 

924 ------ 

925 NetworkXError 

926 If n is not in the graph. 

927 

928 See Also 

929 -------- 

930 predecessors 

931 

932 Notes 

933 ----- 

934 neighbors() and successors() are the same. 

935 """ 

936 try: 

937 return iter(self._succ[n]) 

938 except KeyError as err: 

939 raise NetworkXError(f"The node {n} is not in the digraph.") from err 

940 

941 # digraph definitions 

942 neighbors = successors 

943 

944 def predecessors(self, n): 

945 """Returns an iterator over predecessor nodes of n. 

946 

947 A predecessor of n is a node m such that there exists a directed 

948 edge from m to n. 

949 

950 Parameters 

951 ---------- 

952 n : node 

953 A node in the graph 

954 

955 Raises 

956 ------ 

957 NetworkXError 

958 If n is not in the graph. 

959 

960 See Also 

961 -------- 

962 successors 

963 """ 

964 try: 

965 return iter(self._pred[n]) 

966 except KeyError as err: 

967 raise NetworkXError(f"The node {n} is not in the digraph.") from err 

968 

969 @cached_property 

970 def edges(self): 

971 """An OutEdgeView of the DiGraph as G.edges or G.edges(). 

972 

973 edges(self, nbunch=None, data=False, default=None) 

974 

975 The OutEdgeView provides set-like operations on the edge-tuples 

976 as well as edge attribute lookup. When called, it also provides 

977 an EdgeDataView object which allows control of access to edge 

978 attributes (but does not provide set-like operations). 

979 Hence, `G.edges[u, v]['color']` provides the value of the color 

980 attribute for edge `(u, v)` while 

981 `for (u, v, c) in G.edges.data('color', default='red'):` 

982 iterates through all the edges yielding the color attribute 

983 with default `'red'` if no color attribute exists. 

984 

985 Parameters 

986 ---------- 

987 nbunch : single node, container, or all nodes (default= all nodes) 

988 The view will only report edges from these nodes. 

989 data : string or bool, optional (default=False) 

990 The edge attribute returned in 3-tuple (u, v, ddict[data]). 

991 If True, return edge attribute dict in 3-tuple (u, v, ddict). 

992 If False, return 2-tuple (u, v). 

993 default : value, optional (default=None) 

994 Value used for edges that don't have the requested attribute. 

995 Only relevant if data is not True or False. 

996 

997 Returns 

998 ------- 

999 edges : OutEdgeView 

1000 A view of edge attributes, usually it iterates over (u, v) 

1001 or (u, v, d) tuples of edges, but can also be used for 

1002 attribute lookup as `edges[u, v]['foo']`. 

1003 

1004 See Also 

1005 -------- 

1006 in_edges, out_edges 

1007 

1008 Notes 

1009 ----- 

1010 Nodes in nbunch that are not in the graph will be (quietly) ignored. 

1011 For directed graphs this returns the out-edges. 

1012 

1013 Examples 

1014 -------- 

1015 >>> G = nx.DiGraph() # or MultiDiGraph, etc 

1016 >>> nx.add_path(G, [0, 1, 2]) 

1017 >>> G.add_edge(2, 3, weight=5) 

1018 >>> [e for e in G.edges] 

1019 [(0, 1), (1, 2), (2, 3)] 

1020 >>> G.edges.data() # default data is {} (empty dict) 

1021 OutEdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})]) 

1022 >>> G.edges.data("weight", default=1) 

1023 OutEdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)]) 

1024 >>> G.edges([0, 2]) # only edges originating from these nodes 

1025 OutEdgeDataView([(0, 1), (2, 3)]) 

1026 >>> G.edges(0) # only edges from node 0 

1027 OutEdgeDataView([(0, 1)]) 

1028 

1029 """ 

1030 return OutEdgeView(self) 

1031 

1032 # alias out_edges to edges 

1033 @cached_property 

1034 def out_edges(self): 

1035 return OutEdgeView(self) 

1036 

1037 out_edges.__doc__ = edges.__doc__ 

1038 

1039 @cached_property 

1040 def in_edges(self): 

1041 """A view of the in edges of the graph as G.in_edges or G.in_edges(). 

1042 

1043 in_edges(self, nbunch=None, data=False, default=None): 

1044 

1045 Parameters 

1046 ---------- 

1047 nbunch : single node, container, or all nodes (default= all nodes) 

1048 The view will only report edges incident to these nodes. 

1049 data : string or bool, optional (default=False) 

1050 The edge attribute returned in 3-tuple (u, v, ddict[data]). 

1051 If True, return edge attribute dict in 3-tuple (u, v, ddict). 

1052 If False, return 2-tuple (u, v). 

1053 default : value, optional (default=None) 

1054 Value used for edges that don't have the requested attribute. 

1055 Only relevant if data is not True or False. 

1056 

1057 Returns 

1058 ------- 

1059 in_edges : InEdgeView or InEdgeDataView 

1060 A view of edge attributes, usually it iterates over (u, v) 

1061 or (u, v, d) tuples of edges, but can also be used for 

1062 attribute lookup as `edges[u, v]['foo']`. 

1063 

1064 Examples 

1065 -------- 

1066 >>> G = nx.DiGraph() 

1067 >>> G.add_edge(1, 2, color="blue") 

1068 >>> G.in_edges() 

1069 InEdgeView([(1, 2)]) 

1070 >>> G.in_edges(nbunch=2) 

1071 InEdgeDataView([(1, 2)]) 

1072 

1073 See Also 

1074 -------- 

1075 edges 

1076 """ 

1077 return InEdgeView(self) 

1078 

1079 @cached_property 

1080 def degree(self): 

1081 """A DegreeView for the Graph as G.degree or G.degree(). 

1082 

1083 The node degree is the number of edges adjacent to the node. 

1084 The weighted node degree is the sum of the edge weights for 

1085 edges incident to that node. 

1086 

1087 This object provides an iterator for (node, degree) as well as 

1088 lookup for the degree for a single node. 

1089 

1090 Parameters 

1091 ---------- 

1092 nbunch : single node, container, or all nodes (default= all nodes) 

1093 The view will only report edges incident to these nodes. 

1094 

1095 weight : string or None, optional (default=None) 

1096 The name of an edge attribute that holds the numerical value used 

1097 as a weight. If None, then each edge has weight 1. 

1098 The degree is the sum of the edge weights adjacent to the node. 

1099 

1100 Returns 

1101 ------- 

1102 DiDegreeView or int 

1103 If multiple nodes are requested (the default), returns a `DiDegreeView` 

1104 mapping nodes to their degree. 

1105 If a single node is requested, returns the degree of the node as an integer. 

1106 

1107 See Also 

1108 -------- 

1109 in_degree, out_degree 

1110 

1111 Examples 

1112 -------- 

1113 >>> G = nx.DiGraph() # or MultiDiGraph 

1114 >>> nx.add_path(G, [0, 1, 2, 3]) 

1115 >>> G.degree(0) # node 0 with degree 1 

1116 1 

1117 >>> list(G.degree([0, 1, 2])) 

1118 [(0, 1), (1, 2), (2, 2)] 

1119 

1120 """ 

1121 return DiDegreeView(self) 

1122 

1123 @cached_property 

1124 def in_degree(self): 

1125 """An InDegreeView for (node, in_degree) or in_degree for single node. 

1126 

1127 The node in_degree is the number of edges pointing to the node. 

1128 The weighted node degree is the sum of the edge weights for 

1129 edges incident to that node. 

1130 

1131 This object provides an iteration over (node, in_degree) as well as 

1132 lookup for the degree for a single node. 

1133 

1134 Parameters 

1135 ---------- 

1136 nbunch : single node, container, or all nodes (default= all nodes) 

1137 The view will only report edges incident to these nodes. 

1138 

1139 weight : string or None, optional (default=None) 

1140 The name of an edge attribute that holds the numerical value used 

1141 as a weight. If None, then each edge has weight 1. 

1142 The degree is the sum of the edge weights adjacent to the node. 

1143 

1144 Returns 

1145 ------- 

1146 If a single node is requested 

1147 deg : int 

1148 In-degree of the node 

1149 

1150 OR if multiple nodes are requested 

1151 nd_iter : iterator 

1152 The iterator returns two-tuples of (node, in-degree). 

1153 

1154 See Also 

1155 -------- 

1156 degree, out_degree 

1157 

1158 Examples 

1159 --------