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

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 def __init__(self, incoming_graph_data=None, **attr): 

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

336 

337 Parameters 

338 ---------- 

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

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

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

342 NetworkX graph object. If the corresponding optional Python 

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

344 SciPy sparse array, or a PyGraphviz graph. 

345 

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

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

348 

349 See Also 

350 -------- 

351 convert 

352 

353 Examples 

354 -------- 

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

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

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

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

359 

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

361 

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

363 >>> G.graph 

364 {'day': 'Friday'} 

365 

366 """ 

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

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

369 # We store two adjacency lists: 

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

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

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

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

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

375 

376 self.__networkx_cache__ = {} 

377 # attempt to load graph with data 

378 if incoming_graph_data is not None: 

379 convert.to_networkx_graph(incoming_graph_data, create_using=self) 

380 # load graph attributes (must be after convert) 

381 self.graph.update(attr) 

382 

383 @cached_property 

384 def adj(self): 

385 """Graph adjacency object holding the neighbors 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.adj[3][2]['color'] = 'blue'` sets 

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

391 

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

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

394 

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

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

397 

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

399 """ 

400 return AdjacencyView(self._succ) 

401 

402 @cached_property 

403 def succ(self): 

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

405 

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

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

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

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

410 

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

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

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

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

415 

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

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

418 

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

420 """ 

421 return AdjacencyView(self._succ) 

422 

423 @cached_property 

424 def pred(self): 

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

426 

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

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

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

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

431 

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

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

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

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

436 """ 

437 return AdjacencyView(self._pred) 

438 

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

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

441 

442 Parameters 

443 ---------- 

444 node_for_adding : node 

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

446 attr : keyword arguments, optional 

447 Set or change node attributes using key=value. 

448 

449 See Also 

450 -------- 

451 add_nodes_from 

452 

453 Examples 

454 -------- 

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

456 >>> G.add_node(1) 

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

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

459 >>> G.add_node(K3) 

460 >>> G.number_of_nodes() 

461 3 

462 

463 Use keywords set/change node attributes: 

464 

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

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

467 

468 Notes 

469 ----- 

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

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

472 and numbers, etc. 

473 

474 On many platforms hashable items also include mutables such as 

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

476 doesn't change on mutables. 

477 """ 

478 if node_for_adding not in self._succ: 

479 if node_for_adding is None: 

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

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

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

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

484 attr_dict.update(attr) 

485 else: # update attr even if node already exists 

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

487 nx._clear_cache(self) 

488 

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

490 """Add multiple nodes. 

491 

492 Parameters 

493 ---------- 

494 nodes_for_adding : iterable container 

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

496 OR 

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

498 Node attributes are updated using the attribute dict. 

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

500 Update attributes for all nodes in nodes. 

501 Node attributes specified in nodes as a tuple take 

502 precedence over attributes specified via keyword arguments. 

503 

504 See Also 

505 -------- 

506 add_node 

507 

508 Notes 

509 ----- 

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

511 a `RuntimeError` can be raised with message: 

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

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

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

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

516 object to `G.add_nodes_from`. 

517 

518 Examples 

519 -------- 

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

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

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

523 >>> G.add_nodes_from(K3) 

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

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

526 

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

528 

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

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

531 

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

533 

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

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

536 11 

537 >>> H = nx.Graph() 

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

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

540 11 

541 

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

543 

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

545 >>> # wrong way - will raise RuntimeError 

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

547 >>> # correct way 

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

549 """ 

550 for n in nodes_for_adding: 

551 try: 

552 newnode = n not in self._node 

553 newdict = attr 

554 except TypeError: 

555 n, ndict = n 

556 newnode = n not in self._node 

557 newdict = attr.copy() 

558 newdict.update(ndict) 

559 if newnode: 

560 if n is None: 

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

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

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

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

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

566 nx._clear_cache(self) 

567 

568 def remove_node(self, n): 

569 """Remove node n. 

570 

571 Removes the node n and all adjacent edges. 

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

573 

574 Parameters 

575 ---------- 

576 n : node 

577 A node in the graph 

578 

579 Raises 

580 ------ 

581 NetworkXError 

582 If n is not in the graph. 

583 

584 See Also 

585 -------- 

586 remove_nodes_from 

587 

588 Examples 

589 -------- 

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

591 >>> list(G.edges) 

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

593 >>> G.remove_node(1) 

594 >>> list(G.edges) 

595 [] 

596 

597 """ 

598 try: 

599 nbrs = self._succ[n] 

600 del self._node[n] 

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

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

603 for u in nbrs: 

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

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

606 for u in self._pred[n]: 

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

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

609 nx._clear_cache(self) 

610 

611 def remove_nodes_from(self, nodes): 

612 """Remove multiple nodes. 

613 

614 Parameters 

615 ---------- 

616 nodes : iterable container 

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

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

619 

620 See Also 

621 -------- 

622 remove_node 

623 

624 Notes 

625 ----- 

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

627 a `RuntimeError` will be raised with message: 

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

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

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

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

632 object to `G.remove_nodes_from`. 

633 

634 Examples 

635 -------- 

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

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

638 >>> e 

639 [0, 1, 2] 

640 >>> G.remove_nodes_from(e) 

641 >>> list(G.nodes) 

642 [] 

643 

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

645 

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

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

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

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

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

651 """ 

652 for n in nodes: 

653 try: 

654 succs = self._succ[n] 

655 del self._node[n] 

656 for u in succs: 

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

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

659 for u in self._pred[n]: 

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

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

662 except KeyError: 

663 pass # silent failure on remove 

664 nx._clear_cache(self) 

665 

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

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

668 

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

670 not already in the graph. 

671 

672 Edge attributes can be specified with keywords or by directly 

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

674 

675 Parameters 

676 ---------- 

677 u_of_edge, v_of_edge : nodes 

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

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

680 attr : keyword arguments, optional 

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

682 keyword arguments. 

683 

684 See Also 

685 -------- 

686 add_edges_from : add a collection of edges 

687 

688 Notes 

689 ----- 

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

691 

692 Many NetworkX algorithms designed for weighted graphs use 

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

694 

695 Examples 

696 -------- 

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

698 

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

700 >>> e = (1, 2) 

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

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

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

704 

705 Associate data to edges using keywords: 

706 

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

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

709 

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

711 

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

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

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

715 """ 

716 u, v = u_of_edge, v_of_edge 

717 # add nodes 

718 if u not in self._succ: 

719 if u is None: 

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

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

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

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

724 if v not in self._succ: 

725 if v is None: 

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

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

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

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

730 # add the edge 

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

732 datadict.update(attr) 

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

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

735 nx._clear_cache(self) 

736 

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

738 """Add all the edges in ebunch_to_add. 

739 

740 Parameters 

741 ---------- 

742 ebunch_to_add : container of edges 

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

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

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

746 attr : keyword arguments, optional 

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

748 keyword arguments. 

749 

750 See Also 

751 -------- 

752 add_edge : add a single edge 

753 add_weighted_edges_from : convenient way to add weighted edges 

754 

755 Notes 

756 ----- 

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

758 will be updated when each duplicate edge is added. 

759 

760 Edge attributes specified in an ebunch take precedence over 

761 attributes specified via keyword arguments. 

762 

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

764 a `RuntimeError` can be raised with message: 

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

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

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

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

769 object to `G.add_edges_from`. 

770 

771 Examples 

772 -------- 

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

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

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

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

777 

778 Associate data to edges 

779 

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

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

782 

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

784 

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

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

787 >>> # wrong way - will raise RuntimeError 

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

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

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

791 """ 

792 for e in ebunch_to_add: 

793 ne = len(e) 

794 if ne == 3: 

795 u, v, dd = e 

796 elif ne == 2: 

797 u, v = e 

798 dd = {} 

799 else: 

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

801 if u not in self._succ: 

802 if u is None: 

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

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

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

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

807 if v not in self._succ: 

808 if v is None: 

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

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

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

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

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

814 datadict.update(attr) 

815 datadict.update(dd) 

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

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

818 nx._clear_cache(self) 

819 

820 def remove_edge(self, u, v): 

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

822 

823 Parameters 

824 ---------- 

825 u, v : nodes 

826 Remove the edge between nodes u and v. 

827 

828 Raises 

829 ------ 

830 NetworkXError 

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

832 

833 See Also 

834 -------- 

835 remove_edges_from : remove a collection of edges 

836 

837 Examples 

838 -------- 

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

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

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

842 >>> e = (1, 2) 

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

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

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

846 """ 

847 try: 

848 del self._succ[u][v] 

849 del self._pred[v][u] 

850 except KeyError as err: 

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

852 nx._clear_cache(self) 

853 

854 def remove_edges_from(self, ebunch): 

855 """Remove all edges specified in ebunch. 

856 

857 Parameters 

858 ---------- 

859 ebunch: list or container of edge tuples 

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

861 from the graph. The edges can be: 

862 

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

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

865 

866 See Also 

867 -------- 

868 remove_edge : remove a single edge 

869 

870 Notes 

871 ----- 

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

873 

874 Examples 

875 -------- 

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

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

878 >>> G.remove_edges_from(ebunch) 

879 """ 

880 for e in ebunch: 

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

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

883 del self._succ[u][v] 

884 del self._pred[v][u] 

885 nx._clear_cache(self) 

886 

887 def has_successor(self, u, v): 

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

889 

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

891 """ 

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

893 

894 def has_predecessor(self, u, v): 

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

896 

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

898 """ 

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

900 

901 def successors(self, n): 

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

903 

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

905 edge from n to m. 

906 

907 Parameters 

908 ---------- 

909 n : node 

910 A node in the graph 

911 

912 Raises 

913 ------ 

914 NetworkXError 

915 If n is not in the graph. 

916 

917 See Also 

918 -------- 

919 predecessors 

920 

921 Notes 

922 ----- 

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

924 """ 

925 try: 

926 return iter(self._succ[n]) 

927 except KeyError as err: 

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

929 

930 # digraph definitions 

931 neighbors = successors 

932 

933 def predecessors(self, n): 

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

935 

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

937 edge from m to n. 

938 

939 Parameters 

940 ---------- 

941 n : node 

942 A node in the graph 

943 

944 Raises 

945 ------ 

946 NetworkXError 

947 If n is not in the graph. 

948 

949 See Also 

950 -------- 

951 successors 

952 """ 

953 try: 

954 return iter(self._pred[n]) 

955 except KeyError as err: 

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

957 

958 @cached_property 

959 def edges(self): 

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

961 

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

963 

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

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

966 an EdgeDataView object which allows control of access to edge 

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

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

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

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

971 iterates through all the edges yielding the color attribute 

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

973 

974 Parameters 

975 ---------- 

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

977 The view will only report edges from these nodes. 

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

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

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

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

982 default : value, optional (default=None) 

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

984 Only relevant if data is not True or False. 

985 

986 Returns 

987 ------- 

988 edges : OutEdgeView 

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

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

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

992 

993 See Also 

994 -------- 

995 in_edges, out_edges 

996 

997 Notes 

998 ----- 

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

1000 For directed graphs this returns the out-edges. 

1001 

1002 Examples 

1003 -------- 

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

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

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

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

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

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

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

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

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

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

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

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

1016 OutEdgeDataView([(0, 1)]) 

1017 

1018 """ 

1019 return OutEdgeView(self) 

1020 

1021 # alias out_edges to edges 

1022 @cached_property 

1023 def out_edges(self): 

1024 return OutEdgeView(self) 

1025 

1026 out_edges.__doc__ = edges.__doc__ 

1027 

1028 @cached_property 

1029 def in_edges(self): 

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

1031 

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

1033 

1034 Parameters 

1035 ---------- 

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

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

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

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

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

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

1042 default : value, optional (default=None) 

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

1044 Only relevant if data is not True or False. 

1045 

1046 Returns 

1047 ------- 

1048 in_edges : InEdgeView or InEdgeDataView 

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

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

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

1052 

1053 Examples 

1054 -------- 

1055 >>> G = nx.DiGraph() 

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

1057 >>> G.in_edges() 

1058 InEdgeView([(1, 2)]) 

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

1060 InEdgeDataView([(1, 2)]) 

1061 

1062 See Also 

1063 -------- 

1064 edges 

1065 """ 

1066 return InEdgeView(self) 

1067 

1068 @cached_property 

1069 def degree(self): 

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

1071 

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

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

1074 edges incident to that node. 

1075 

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

1077 lookup for the degree for a single node. 

1078 

1079 Parameters 

1080 ---------- 

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

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

1083 

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

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

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

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

1088 

1089 Returns 

1090 ------- 

1091 DiDegreeView or int 

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

1093 mapping nodes to their degree. 

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

1095 

1096 See Also 

1097 -------- 

1098 in_degree, out_degree 

1099 

1100 Examples 

1101 -------- 

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

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

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

1105 1 

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

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

1108 

1109 """ 

1110 return DiDegreeView(self) 

1111 

1112 @cached_property 

1113 def in_degree(self): 

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

1115 

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

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

1118 edges incident to that node. 

1119 

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

1121 lookup for the degree for a single node. 

1122 

1123 Parameters 

1124 ---------- 

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

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

1127 

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

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

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

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

1132 

1133 Returns 

1134 ------- 

1135 If a single node is requested 

1136 deg : int 

1137 In-degree of the node 

1138 

1139 OR if multiple nodes are requested 

1140 nd_iter : iterator 

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

1142 

1143 See Also 

1144 -------- 

1145 degree, out_degree 

1146 

1147 Examples 

1148 -------- 

1149 >>> G = nx.DiGraph() 

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

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

1152 0 

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

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

1155 

1156 """ 

1157 return InDegreeView(self) 

1158 

1159 @cached_property 

1160 def out_degree(self): 

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

1162 

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

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

1165 edges incident to that node.