Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/classes/digraph.py: 48%

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

2from copy import deepcopy 

3from functools import cached_property 

4 

5import networkx as nx 

6from networkx import convert 

7from networkx.classes.coreviews import AdjacencyView 

8from networkx.classes.graph import Graph 

9from networkx.classes.reportviews import ( 

10 DiDegreeView, 

11 InDegreeView, 

12 InEdgeView, 

13 OutDegreeView, 

14 OutEdgeView, 

15) 

16from networkx.exception import NetworkXError 

17 

18__all__ = ["DiGraph"] 

19 

20 

21class _CachedPropertyResetterAdjAndSucc: 

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

23 

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

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

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

27 

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

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

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

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

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

33 

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

35 """ 

36 

37 def __set__(self, obj, value): 

38 od = obj.__dict__ 

39 od["_adj"] = value 

40 od["_succ"] = value 

41 # reset cached properties 

42 if "adj" in od: 

43 del od["adj"] 

44 if "succ" in od: 

45 del od["succ"] 

46 

47 

48class _CachedPropertyResetterPred: 

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

50 

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

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

53 

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

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

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

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

58 act as they normally would. 

59 

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

61 """ 

62 

63 def __set__(self, obj, value): 

64 od = obj.__dict__ 

65 od["_pred"] = value 

66 if "pred" in od: 

67 del od["pred"] 

68 

69 

70class DiGraph(Graph): 

71 """ 

72 Base class for directed graphs. 

73 

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

75 

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

77 (parallel) edges are not. 

78 

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

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

81 

82 Edges are represented as links between nodes with optional 

83 key/value attributes. 

84 

85 Parameters 

86 ---------- 

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

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

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

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

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

92 sparse matrix, or PyGraphviz graph. 

93 

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

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

96 

97 See Also 

98 -------- 

99 Graph 

100 MultiGraph 

101 MultiDiGraph 

102 

103 Examples 

104 -------- 

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

106 no edges. 

107 

108 >>> G = nx.DiGraph() 

109 

110 G can be grown in several ways. 

111 

112 **Nodes:** 

113 

114 Add one node at a time: 

115 

116 >>> G.add_node(1) 

117 

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

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

120 

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

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

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

124 >>> G.add_nodes_from(H) 

125 

126 In addition to strings and integers any hashable Python object 

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

128 or even another Graph. 

129 

130 >>> G.add_node(H) 

131 

132 **Edges:** 

133 

134 G can also be grown by adding edges. 

135 

136 Add one edge, 

137 

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

139 

140 a list of edges, 

141 

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

143 

144 or a collection of edges, 

145 

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

147 

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

149 are added automatically. There are no errors when adding 

150 nodes or edges that already exist. 

151 

152 **Attributes:** 

153 

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

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

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

157 add_edge, add_node or direct manipulation of the attribute 

158 dictionaries named graph, node and edge respectively. 

159 

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

161 >>> G.graph 

162 {'day': 'Friday'} 

163 

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

165 

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

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

168 >>> G.nodes[1] 

169 {'time': '5pm'} 

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

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

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

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

174 

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

176 notation, or G.edges. 

177 

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

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

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

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

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

183 

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

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

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

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

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

189 

190 **Shortcuts:** 

191 

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

193 

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

195 True 

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

197 [1, 2] 

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

199 5 

200 

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

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

203 

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

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

206 ... if "weight" in eattr: 

207 ... # Do something useful with the edges 

208 ... pass 

209 

210 But the edges reporting object is often more convenient: 

211 

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

213 ... if weight is not None: 

214 ... # Do something useful with the edges 

215 ... pass 

216 

217 **Reporting:** 

218 

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

220 Reporting usually provides views instead of containers to reduce memory 

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

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

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

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

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

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

227 

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

229 

230 **Subclasses (Advanced):** 

231 

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

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

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

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

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

237 

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

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

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

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

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

243 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory, 

244 adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory. 

245 

246 node_dict_factory : function, (default: dict) 

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

248 attributes, keyed by node id. 

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

250 

251 node_attr_dict_factory: function, (default: dict) 

252 Factory function to be used to create the node attribute 

253 dict which holds attribute values keyed by attribute name. 

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

255 

256 adjlist_outer_dict_factory : function, (default: dict) 

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

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

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

260 

261 adjlist_inner_dict_factory : function, optional (default: dict) 

262 Factory function to be used to create the adjacency list 

263 dict which holds edge data keyed by neighbor. 

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

265 

266 edge_attr_dict_factory : function, optional (default: dict) 

267 Factory function to be used to create the edge attribute 

268 dict which holds attribute values keyed by attribute name. 

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

270 

271 graph_attr_dict_factory : function, (default: dict) 

272 Factory function to be used to create the graph attribute 

273 dict which holds attribute values keyed by attribute name. 

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

275 

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

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

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

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

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

281 

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

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

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

285 

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

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

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

289 

290 **Subclassing Example** 

291 

292 Create a low memory graph class that effectively disallows edge 

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

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

295 

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

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

298 ... 

299 ... def single_edge_dict(self): 

300 ... return self.all_edge_dict 

301 ... 

302 ... edge_attr_dict_factory = single_edge_dict 

303 >>> G = ThinGraph() 

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

305 >>> G[2][1] 

306 {'weight': 1} 

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

308 >>> G[2][1] is G[2][2] 

309 True 

310 """ 

311 

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

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

314 _pred = _CachedPropertyResetterPred() 

315 

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

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

318 

319 Parameters 

320 ---------- 

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

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

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

324 NetworkX graph object. If the corresponding optional Python 

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

326 SciPy sparse array, or a PyGraphviz graph. 

327 

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

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

330 

331 See Also 

332 -------- 

333 convert 

334 

335 Examples 

336 -------- 

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

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

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

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

341 

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

343 

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

345 >>> G.graph 

346 {'day': 'Friday'} 

347 

348 """ 

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

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

351 # We store two adjacency lists: 

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

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

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

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

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

357 

358 # attempt to load graph with data 

359 if incoming_graph_data is not None: 

360 convert.to_networkx_graph(incoming_graph_data, create_using=self) 

361 # load graph attributes (must be after convert) 

362 self.graph.update(attr) 

363 

364 @cached_property 

365 def adj(self): 

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

367 

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

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

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

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

372 

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

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

375 

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

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

378 

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

380 """ 

381 return AdjacencyView(self._succ) 

382 

383 @cached_property 

384 def succ(self): 

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

386 

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

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

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

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

391 

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

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

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

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

396 

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

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

399 

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

401 """ 

402 return AdjacencyView(self._succ) 

403 

404 @cached_property 

405 def pred(self): 

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

407 

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

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

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

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

412 

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

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

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

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

417 """ 

418 return AdjacencyView(self._pred) 

419 

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

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

422 

423 Parameters 

424 ---------- 

425 node_for_adding : node 

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

427 attr : keyword arguments, optional 

428 Set or change node attributes using key=value. 

429 

430 See Also 

431 -------- 

432 add_nodes_from 

433 

434 Examples 

435 -------- 

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

437 >>> G.add_node(1) 

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

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

440 >>> G.add_node(K3) 

441 >>> G.number_of_nodes() 

442 3 

443 

444 Use keywords set/change node attributes: 

445 

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

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

448 

449 Notes 

450 ----- 

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

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

453 and numbers, etc. 

454 

455 On many platforms hashable items also include mutables such as 

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

457 doesn't change on mutables. 

458 """ 

459 if node_for_adding not in self._succ: 

460 if node_for_adding is None: 

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

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

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

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

465 attr_dict.update(attr) 

466 else: # update attr even if node already exists 

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

468 

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

470 """Add multiple nodes. 

471 

472 Parameters 

473 ---------- 

474 nodes_for_adding : iterable container 

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

476 OR 

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

478 Node attributes are updated using the attribute dict. 

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

480 Update attributes for all nodes in nodes. 

481 Node attributes specified in nodes as a tuple take 

482 precedence over attributes specified via keyword arguments. 

483 

484 See Also 

485 -------- 

486 add_node 

487 

488 Notes 

489 ----- 

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

491 a `RuntimeError` can be raised with message: 

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

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

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

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

496 object to `G.add_nodes_from`. 

497 

498 Examples 

499 -------- 

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

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

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

503 >>> G.add_nodes_from(K3) 

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

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

506 

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

508 

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

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

511 

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

513 

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

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

516 11 

517 >>> H = nx.Graph() 

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

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

520 11 

521 

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

523 

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

525 >>> # wrong way - will raise RuntimeError 

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

527 >>> # correct way 

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

529 """ 

530 for n in nodes_for_adding: 

531 try: 

532 newnode = n not in self._node 

533 newdict = attr 

534 except TypeError: 

535 n, ndict = n 

536 newnode = n not in self._node 

537 newdict = attr.copy() 

538 newdict.update(ndict) 

539 if newnode: 

540 if n is None: 

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

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

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

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

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

546 

547 def remove_node(self, n): 

548 """Remove node n. 

549 

550 Removes the node n and all adjacent edges. 

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

552 

553 Parameters 

554 ---------- 

555 n : node 

556 A node in the graph 

557 

558 Raises 

559 ------ 

560 NetworkXError 

561 If n is not in the graph. 

562 

563 See Also 

564 -------- 

565 remove_nodes_from 

566 

567 Examples 

568 -------- 

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

570 >>> list(G.edges) 

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

572 >>> G.remove_node(1) 

573 >>> list(G.edges) 

574 [] 

575 

576 """ 

577 try: 

578 nbrs = self._succ[n] 

579 del self._node[n] 

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

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

582 for u in nbrs: 

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

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

585 for u in self._pred[n]: 

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

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

588 

589 def remove_nodes_from(self, nodes): 

590 """Remove multiple nodes. 

591 

592 Parameters 

593 ---------- 

594 nodes : iterable container 

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

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

597 

598 See Also 

599 -------- 

600 remove_node 

601 

602 Notes 

603 ----- 

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

605 a `RuntimeError` will be raised with message: 

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

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

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

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

610 object to `G.remove_nodes_from`. 

611 

612 Examples 

613 -------- 

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

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

616 >>> e 

617 [0, 1, 2] 

618 >>> G.remove_nodes_from(e) 

619 >>> list(G.nodes) 

620 [] 

621 

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

623 

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

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

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

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

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

629 """ 

630 for n in nodes: 

631 try: 

632 succs = self._succ[n] 

633 del self._node[n] 

634 for u in succs: 

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

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

637 for u in self._pred[n]: 

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

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

640 except KeyError: 

641 pass # silent failure on remove 

642 

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

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

645 

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

647 not already in the graph. 

648 

649 Edge attributes can be specified with keywords or by directly 

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

651 

652 Parameters 

653 ---------- 

654 u_of_edge, v_of_edge : nodes 

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

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

657 attr : keyword arguments, optional 

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

659 keyword arguments. 

660 

661 See Also 

662 -------- 

663 add_edges_from : add a collection of edges 

664 

665 Notes 

666 ----- 

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

668 

669 Many NetworkX algorithms designed for weighted graphs use 

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

671 

672 Examples 

673 -------- 

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

675 

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

677 >>> e = (1, 2) 

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

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

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

681 

682 Associate data to edges using keywords: 

683 

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

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

686 

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

688 

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

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

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

692 """ 

693 u, v = u_of_edge, v_of_edge 

694 # add nodes 

695 if u not in self._succ: 

696 if u is None: 

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

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

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

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

701 if v not in self._succ: 

702 if v is None: 

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

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

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

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

707 # add the edge 

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

709 datadict.update(attr) 

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

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

712 

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

714 """Add all the edges in ebunch_to_add. 

715 

716 Parameters 

717 ---------- 

718 ebunch_to_add : container of edges 

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

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

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

722 attr : keyword arguments, optional 

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

724 keyword arguments. 

725 

726 See Also 

727 -------- 

728 add_edge : add a single edge 

729 add_weighted_edges_from : convenient way to add weighted edges 

730 

731 Notes 

732 ----- 

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

734 will be updated when each duplicate edge is added. 

735 

736 Edge attributes specified in an ebunch take precedence over 

737 attributes specified via keyword arguments. 

738 

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

740 a `RuntimeError` can be raised with message: 

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

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

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

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

745 object to `G.add_edges_from`. 

746 

747 Examples 

748 -------- 

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

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

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

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

753 

754 Associate data to edges 

755 

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

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

758 

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

760 

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

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

763 >>> # wrong way - will raise RuntimeError 

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

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

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

767 """ 

768 for e in ebunch_to_add: 

769 ne = len(e) 

770 if ne == 3: 

771 u, v, dd = e 

772 elif ne == 2: 

773 u, v = e 

774 dd = {} 

775 else: 

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

777 if u not in self._succ: 

778 if u is None: 

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

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

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

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

783 if v not in self._succ: 

784 if v is None: 

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

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

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

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

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

790 datadict.update(attr) 

791 datadict.update(dd) 

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

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

794 

795 def remove_edge(self, u, v): 

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

797 

798 Parameters 

799 ---------- 

800 u, v : nodes 

801 Remove the edge between nodes u and v. 

802 

803 Raises 

804 ------ 

805 NetworkXError 

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

807 

808 See Also 

809 -------- 

810 remove_edges_from : remove a collection of edges 

811 

812 Examples 

813 -------- 

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

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

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

817 >>> e = (1, 2) 

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

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

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

821 """ 

822 try: 

823 del self._succ[u][v] 

824 del self._pred[v][u] 

825 except KeyError as err: 

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

827 

828 def remove_edges_from(self, ebunch): 

829 """Remove all edges specified in ebunch. 

830 

831 Parameters 

832 ---------- 

833 ebunch: list or container of edge tuples 

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

835 from the graph. The edges can be: 

836 

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

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

839 

840 See Also 

841 -------- 

842 remove_edge : remove a single edge 

843 

844 Notes 

845 ----- 

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

847 

848 Examples 

849 -------- 

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

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

852 >>> G.remove_edges_from(ebunch) 

853 """ 

854 for e in ebunch: 

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

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

857 del self._succ[u][v] 

858 del self._pred[v][u] 

859 

860 def has_successor(self, u, v): 

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

862 

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

864 """ 

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

866 

867 def has_predecessor(self, u, v): 

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

869 

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

871 """ 

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

873 

874 def successors(self, n): 

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

876 

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

878 edge from n to m. 

879 

880 Parameters 

881 ---------- 

882 n : node 

883 A node in the graph 

884 

885 Raises 

886 ------ 

887 NetworkXError 

888 If n is not in the graph. 

889 

890 See Also 

891 -------- 

892 predecessors 

893 

894 Notes 

895 ----- 

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

897 """ 

898 try: 

899 return iter(self._succ[n]) 

900 except KeyError as err: 

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

902 

903 # digraph definitions 

904 neighbors = successors 

905 

906 def predecessors(self, n): 

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

908 

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

910 edge from m to n. 

911 

912 Parameters 

913 ---------- 

914 n : node 

915 A node in the graph 

916 

917 Raises 

918 ------ 

919 NetworkXError 

920 If n is not in the graph. 

921 

922 See Also 

923 -------- 

924 successors 

925 """ 

926 try: 

927 return iter(self._pred[n]) 

928 except KeyError as err: 

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

930 

931 @cached_property 

932 def edges(self): 

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

934 

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

936 

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

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

939 an EdgeDataView object which allows control of access to edge 

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

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

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

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

944 iterates through all the edges yielding the color attribute 

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

946 

947 Parameters 

948 ---------- 

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

950 The view will only report edges from these nodes. 

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

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

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

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

955 default : value, optional (default=None) 

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

957 Only relevant if data is not True or False. 

958 

959 Returns 

960 ------- 

961 edges : OutEdgeView 

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

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

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

965 

966 See Also 

967 -------- 

968 in_edges, out_edges 

969 

970 Notes 

971 ----- 

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

973 For directed graphs this returns the out-edges. 

974 

975 Examples 

976 -------- 

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

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

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

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

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

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

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

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

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

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

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

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

989 OutEdgeDataView([(0, 1)]) 

990 

991 """ 

992 return OutEdgeView(self) 

993 

994 # alias out_edges to edges 

995 @cached_property 

996 def out_edges(self): 

997 return OutEdgeView(self) 

998 

999 out_edges.__doc__ = edges.__doc__ 

1000 

1001 @cached_property 

1002 def in_edges(self): 

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

1004 

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

1006 

1007 Parameters 

1008 ---------- 

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

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

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

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

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

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

1015 default : value, optional (default=None) 

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

1017 Only relevant if data is not True or False. 

1018 

1019 Returns 

1020 ------- 

1021 in_edges : InEdgeView or InEdgeDataView 

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

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

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

1025 

1026 Examples 

1027 -------- 

1028 >>> G = nx.DiGraph() 

1029 >>> G.add_edge(1, 2, color='blue') 

1030 >>> G.in_edges() 

1031 InEdgeView([(1, 2)]) 

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

1033 InEdgeDataView([(1, 2)]) 

1034 

1035 See Also 

1036 -------- 

1037 edges 

1038 """ 

1039 return InEdgeView(self) 

1040 

1041 @cached_property 

1042 def degree(self): 

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

1044 

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

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

1047 edges incident to that node. 

1048 

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

1050 lookup for the degree for a single node. 

1051 

1052 Parameters 

1053 ---------- 

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

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

1056 

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

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

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

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

1061 

1062 Returns 

1063 ------- 

1064 DiDegreeView or int 

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

1066 mapping nodes to their degree. 

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

1068 

1069 See Also 

1070 -------- 

1071 in_degree, out_degree 

1072 

1073 Examples 

1074 -------- 

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

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

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

1078 1 

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

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

1081 

1082 """ 

1083 return DiDegreeView(self) 

1084 

1085 @cached_property 

1086 def in_degree(self): 

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

1088 

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

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

1091 edges incident to that node. 

1092 

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

1094 lookup for the degree for a single node. 

1095 

1096 Parameters 

1097 ---------- 

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

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

1100 

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

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

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

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

1105 

1106 Returns 

1107 ------- 

1108 If a single node is requested 

1109 deg : int 

1110 In-degree of the node 

1111 

1112 OR if multiple nodes are requested 

1113 nd_iter : iterator 

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

1115 

1116 See Also 

1117 -------- 

1118 degree, out_degree 

1119 

1120 Examples 

1121 -------- 

1122 >>> G = nx.DiGraph() 

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

1124 >>> G.in_degree(0) # node 0 with degree 0 

1125 0 

1126 >>> list(G.in_degree([0, 1, 2])) 

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

1128 

1129 """ 

1130 return InDegreeView(self) 

1131 

1132 @cached_property 

1133 def out_degree(self): 

1134 """An OutDegreeView for (node, out_degree) 

1135 

1136 The node out_degree is the number of edges pointing out of the node. 

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

1138 edges incident to that node. 

1139 

1140 This object provides an iterator over (node, out_degree) as well as 

1141 lookup for the degree for a single node. 

1142 

1143 Parameters 

1144 ---------- 

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

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

1147 

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

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

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

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

1152 

1153 Returns 

1154 ------- 

1155 If a single node is requested 

1156 deg : int 

1157 Out-degree of the node 

1158 

1159 OR if multiple nodes are requested 

1160 nd_iter : iterator 

1161 The iterator returns two-tuples of (node, out-degree). 

1162 

1163 See Also 

1164 -------- 

1165 degree, in_degree 

1166 

1167 Examples 

1168 -------- 

1169 >>> G = nx.DiGraph() 

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

1171 >>> G.out_degree(0) # node 0 with degree 1 

1172 1 

1173 >>> list(G.out_degree([0, 1, 2])) 

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

1175 

1176 """