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

1"""Base class for MultiGraph.""" 

2 

3from copy import deepcopy 

4from functools import cached_property 

5 

6import networkx as nx 

7from networkx import NetworkXError, convert 

8from networkx.classes.coreviews import MultiAdjacencyView 

9from networkx.classes.graph import Graph 

10from networkx.classes.reportviews import MultiDegreeView, MultiEdgeView 

11 

12__all__ = ["MultiGraph"] 

13 

14 

15class MultiGraph(Graph): 

16 """ 

17 An undirected graph class that can store multiedges. 

18 

19 Multiedges are multiple edges between two nodes. Each edge 

20 can hold optional data or attributes. 

21 

22 A MultiGraph holds undirected edges. Self loops are allowed. 

23 

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

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

26 

27 Edges are represented as links between nodes with optional 

28 key/value attributes, in a MultiGraph each edge has a key to 

29 distinguish between multiple edges that have the same source and 

30 destination nodes. 

31 

32 Parameters 

33 ---------- 

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

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

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

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

38 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array, 

39 SciPy sparse array, or PyGraphviz graph. 

40 

41 multigraph_input : bool or None (default None) 

42 Note: Only used when `incoming_graph_data` is a dict. 

43 If True, `incoming_graph_data` is assumed to be a 

44 dict-of-dict-of-dict-of-dict structure keyed by 

45 node to neighbor to edge keys to edge data for multi-edges. 

46 A NetworkXError is raised if this is not the case. 

47 If False, :func:`to_networkx_graph` is used to try to determine 

48 the dict's graph data structure as either a dict-of-dict-of-dict 

49 keyed by node to neighbor to edge data, or a dict-of-iterable 

50 keyed by node to neighbors. 

51 If None, the treatment for True is tried, but if it fails, 

52 the treatment for False is tried. 

53 

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

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

56 

57 See Also 

58 -------- 

59 Graph 

60 DiGraph 

61 MultiDiGraph 

62 

63 Examples 

64 -------- 

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

66 no edges. 

67 

68 >>> G = nx.MultiGraph() 

69 

70 G can be grown in several ways. 

71 

72 **Nodes:** 

73 

74 Add one node at a time: 

75 

76 >>> G.add_node(1) 

77 

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

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

80 

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

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

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

84 >>> G.add_nodes_from(H) 

85 

86 In addition to strings and integers any hashable Python object 

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

88 or even another Graph. 

89 

90 >>> G.add_node(H) 

91 

92 **Edges:** 

93 

94 G can also be grown by adding edges. 

95 

96 Add one edge, 

97 

98 >>> key = G.add_edge(1, 2) 

99 

100 a list of edges, 

101 

102 >>> keys = G.add_edges_from([(1, 2), (1, 3)]) 

103 

104 or a collection of edges, 

105 

106 >>> keys = G.add_edges_from(H.edges) 

107 

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

109 are added automatically. If an edge already exists, an additional 

110 edge is created and stored using a key to identify the edge. 

111 By default the key is the lowest unused integer. 

112 

113 >>> keys = G.add_edges_from([(4, 5, {"route": 28}), (4, 5, {"route": 37})]) 

114 >>> G[4] 

115 AdjacencyView({3: {0: {}}, 5: {0: {}, 1: {'route': 28}, 2: {'route': 37}}}) 

116 

117 **Attributes:** 

118 

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

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

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

122 add_edge, add_node or direct manipulation of the attribute 

123 dictionaries named graph, node and edge respectively. 

124 

125 >>> G = nx.MultiGraph(day="Friday") 

126 >>> G.graph 

127 {'day': 'Friday'} 

128 

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

130 

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

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

133 >>> G.nodes[1] 

134 {'time': '5pm'} 

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

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

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

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

139 

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

141 notation, or G.edges. 

142 

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

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

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

146 >>> G[1][2][0]["weight"] = 4.7 

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

148 

149 Warning: we protect the graph data structure by making `G.edges[1, 

150 2, 0]` a read-only dict-like structure. However, you can assign to 

151 attributes in e.g. `G.edges[1, 2, 0]`. Thus, use 2 sets of brackets 

152 to add/change data attributes: `G.edges[1, 2, 0]['weight'] = 4`. 

153 

154 **Shortcuts:** 

155 

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

157 

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

159 True 

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

161 [1, 2] 

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

163 5 

164 >>> G[1] # adjacency dict-like view mapping neighbor -> edge key -> edge attributes 

165 AdjacencyView({2: {0: {'weight': 4}, 1: {'color': 'blue'}}}) 

166 

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

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

169 

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

171 ... for nbr, keydict in nbrsdict.items(): 

172 ... for key, eattr in keydict.items(): 

173 ... if "weight" in eattr: 

174 ... # Do something useful with the edges 

175 ... pass 

176 

177 But the edges() method is often more convenient: 

178 

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

180 ... if weight is not None: 

181 ... # Do something useful with the edges 

182 ... pass 

183 

184 **Reporting:** 

185 

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

187 Reporting usually provides views instead of containers to reduce memory 

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

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

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

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

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

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

194 

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

196 

197 **Subclasses (Advanced):** 

198 

199 The MultiGraph class uses a dict-of-dict-of-dict-of-dict data structure. 

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

201 The next dict (adjlist_dict) represents the adjacency information 

202 and holds edge_key dicts keyed by neighbor. The edge_key dict holds 

203 each edge_attr dict keyed by edge key. The inner dict 

204 (edge_attr_dict) represents the edge data and holds edge attribute 

205 values keyed by attribute names. 

206 

207 Each of these four dicts in the dict-of-dict-of-dict-of-dict 

208 structure can be replaced by a user defined dict-like object. 

209 In general, the dict-like features should be maintained but 

210 extra features can be added. To replace one of the dicts create 

211 a new graph class by changing the class(!) variable holding the 

212 factory for that dict-like structure. The variable names are 

213 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory, 

214 adjlist_outer_dict_factory, edge_key_dict_factory, edge_attr_dict_factory 

215 and graph_attr_dict_factory. 

216 

217 node_dict_factory : function, (default: dict) 

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

219 attributes, keyed by node id. 

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

221 

222 node_attr_dict_factory: function, (default: dict) 

223 Factory function to be used to create the node attribute 

224 dict which holds attribute values keyed by attribute name. 

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

226 

227 adjlist_outer_dict_factory : function, (default: dict) 

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

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

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

231 

232 adjlist_inner_dict_factory : function, (default: dict) 

233 Factory function to be used to create the adjacency list 

234 dict which holds multiedge key dicts keyed by neighbor. 

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

236 

237 edge_key_dict_factory : function, (default: dict) 

238 Factory function to be used to create the edge key dict 

239 which holds edge data keyed by edge key. 

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

241 

242 edge_attr_dict_factory : function, (default: dict) 

243 Factory function to be used to create the edge attribute 

244 dict which holds attribute values keyed by attribute name. 

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

246 

247 graph_attr_dict_factory : function, (default: dict) 

248 Factory function to be used to create the graph attribute 

249 dict which holds attribute values keyed by attribute name. 

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

251 

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

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

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

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

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

257 

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

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

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

261 

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

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

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

265 

266 **Subclassing Example** 

267 

268 Create a low memory graph class that effectively disallows edge 

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

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

271 

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

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

274 ... 

275 ... def single_edge_dict(self): 

276 ... return self.all_edge_dict 

277 ... 

278 ... edge_attr_dict_factory = single_edge_dict 

279 >>> G = ThinGraph() 

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

281 >>> G[2][1] 

282 {'weight': 1} 

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

284 >>> G[2][1] is G[2][2] 

285 True 

286 """ 

287 

288 # node_dict_factory = dict # already assigned in Graph 

289 # adjlist_outer_dict_factory = dict 

290 # adjlist_inner_dict_factory = dict 

291 edge_key_dict_factory = dict 

292 # edge_attr_dict_factory = dict 

293 

294 def to_directed_class(self): 

295 """Returns the class to use for empty directed copies. 

296 

297 If you subclass the base classes, use this to designate 

298 what directed class to use for `to_directed()` copies. 

299 """ 

300 return nx.MultiDiGraph 

301 

302 def to_undirected_class(self): 

303 """Returns the class to use for empty undirected copies. 

304 

305 If you subclass the base classes, use this to designate 

306 what directed class to use for `to_directed()` copies. 

307 """ 

308 return MultiGraph 

309 

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

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

312 

313 Parameters 

314 ---------- 

315 incoming_graph_data : input graph 

316 Data to initialize graph. If incoming_graph_data=None (default) 

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

318 NetworkX graph object. If the corresponding optional Python 

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

320 SciPy sparse array, or a PyGraphviz graph. 

321 

322 multigraph_input : bool or None (default None) 

323 Note: Only used when `incoming_graph_data` is a dict. 

324 If True, `incoming_graph_data` is assumed to be a 

325 dict-of-dict-of-dict-of-dict structure keyed by 

326 node to neighbor to edge keys to edge data for multi-edges. 

327 A NetworkXError is raised if this is not the case. 

328 If False, :func:`to_networkx_graph` is used to try to determine 

329 the dict's graph data structure as either a dict-of-dict-of-dict 

330 keyed by node to neighbor to edge data, or a dict-of-iterable 

331 keyed by node to neighbors. 

332 If None, the treatment for True is tried, but if it fails, 

333 the treatment for False is tried. 

334 

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

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

337 

338 See Also 

339 -------- 

340 convert 

341 

342 Examples 

343 -------- 

344 >>> G = nx.MultiGraph() 

345 >>> G = nx.MultiGraph(name="my graph") 

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

347 >>> G = nx.MultiGraph(e) 

348 

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

350 

351 >>> G = nx.MultiGraph(e, day="Friday") 

352 >>> G.graph 

353 {'day': 'Friday'} 

354 

355 """ 

356 # multigraph_input can be None/True/False. So check "is not False" 

357 if isinstance(incoming_graph_data, dict) and multigraph_input is not False: 

358 Graph.__init__(self) 

359 try: 

360 convert.from_dict_of_dicts( 

361 incoming_graph_data, create_using=self, multigraph_input=True 

362 ) 

363 self.graph.update(attr) 

364 except Exception as err: 

365 if multigraph_input is True: 

366 raise nx.NetworkXError( 

367 f"converting multigraph_input raised:\n{type(err)}: {err}" 

368 ) 

369 Graph.__init__(self, incoming_graph_data, **attr) 

370 else: 

371 Graph.__init__(self, incoming_graph_data, **attr) 

372 

373 @cached_property 

374 def adj(self): 

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

376 

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

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

379 to the edgekey-data-dict. So `G.adj[3][2][0]['color'] = 'blue'` sets 

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

381 

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

383 `for nbr, edgesdict in G.adj[n].items():`. 

384 

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

386 

387 Examples 

388 -------- 

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

390 >>> G = nx.MultiGraph(e) 

391 >>> G.edges[1, 2, 0]["weight"] = 3 

392 >>> result = set() 

393 >>> for edgekey, data in G[1][2].items(): 

394 ... result.add(data.get("weight", 1)) 

395 >>> result 

396 {1, 3} 

397 

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

399 """ 

400 return MultiAdjacencyView(self._adj) 

401 

402 def new_edge_key(self, u, v): 

403 """Returns an unused key for edges between nodes `u` and `v`. 

404 

405 The nodes `u` and `v` do not need to be already in the graph. 

406 

407 Notes 

408 ----- 

409 In the standard MultiGraph class the new key is the number of existing 

410 edges between `u` and `v` (increased if necessary to ensure unused). 

411 The first edge will have key 0, then 1, etc. If an edge is removed 

412 further new_edge_keys may not be in this order. 

413 

414 Parameters 

415 ---------- 

416 u, v : nodes 

417 

418 Returns 

419 ------- 

420 key : int 

421 """ 

422 try: 

423 keydict = self._adj[u][v] 

424 except KeyError: 

425 return 0 

426 key = len(keydict) 

427 while key in keydict: 

428 key += 1 

429 return key 

430 

431 def add_edge(self, u_for_edge, v_for_edge, key=None, **attr): 

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

433 

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

435 not already in the graph. 

436 

437 Edge attributes can be specified with keywords or by directly 

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

439 

440 Parameters 

441 ---------- 

442 u_for_edge, v_for_edge : nodes 

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

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

445 key : hashable identifier, optional (default=lowest unused integer) 

446 Used to distinguish multiedges between a pair of nodes. 

447 attr : keyword arguments, optional 

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

449 keyword arguments. 

450 

451 Returns 

452 ------- 

453 The edge key assigned to the edge. 

454 

455 See Also 

456 -------- 

457 add_edges_from : add a collection of edges 

458 

459 Notes 

460 ----- 

461 To replace/update edge data, use the optional key argument 

462 to identify a unique edge. Otherwise a new edge will be created. 

463 

464 NetworkX algorithms designed for weighted graphs cannot use 

465 multigraphs directly because it is not clear how to handle 

466 multiedge weights. Convert to Graph using edge attribute 

467 'weight' to enable weighted graph algorithms. 

468 

469 Default keys are generated using the method `new_edge_key()`. 

470 This method can be overridden by subclassing the base class and 

471 providing a custom `new_edge_key()` method. 

472 

473 Examples 

474 -------- 

475 The following each add an additional edge e=(1, 2) to graph G: 

476 

477 >>> G = nx.MultiGraph() 

478 >>> e = (1, 2) 

479 >>> ekey = G.add_edge(1, 2) # explicit two-node form 

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

481 1 

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

483 [2] 

484 

485 Associate data to edges using keywords: 

486 

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

488 >>> ekey = G.add_edge(1, 2, key=0, weight=4) # update data for key=0 

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

490 

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

492 

493 >>> ekey = G.add_edge(1, 2) 

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

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

496 """ 

497 u, v = u_for_edge, v_for_edge 

498 # add nodes 

499 if u not in self._adj: 

500 if u is None: 

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

502 self._adj[u] = self.adjlist_inner_dict_factory() 

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

504 if v not in self._adj: 

505 if v is None: 

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

507 self._adj[v] = self.adjlist_inner_dict_factory() 

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

509 if key is None: 

510 key = self.new_edge_key(u, v) 

511 if v in self._adj[u]: 

512 keydict = self._adj[u][v] 

513 datadict = keydict.get(key, self.edge_attr_dict_factory()) 

514 datadict.update(attr) 

515 keydict[key] = datadict 

516 else: 

517 # selfloops work this way without special treatment 

518 datadict = self.edge_attr_dict_factory() 

519 datadict.update(attr) 

520 keydict = self.edge_key_dict_factory() 

521 keydict[key] = datadict 

522 self._adj[u][v] = keydict 

523 self._adj[v][u] = keydict 

524 nx._clear_cache(self) 

525 return key 

526 

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

528 """Add all the edges in ebunch_to_add. 

529 

530 Parameters 

531 ---------- 

532 ebunch_to_add : container of edges 

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

534 graph. The edges can be: 

535 

536 - 2-tuples (u, v) or 

537 - 3-tuples (u, v, d) for an edge data dict d, or 

538 - 3-tuples (u, v, k) for not iterable key k, or 

539 - 4-tuples (u, v, k, d) for an edge with data and key k 

540 

541 attr : keyword arguments, optional 

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

543 keyword arguments. 

544 

545 Returns 

546 ------- 

547 A list of edge keys assigned to the edges in `ebunch`. 

548 

549 See Also 

550 -------- 

551 add_edge : add a single edge 

552 add_weighted_edges_from : convenient way to add weighted edges 

553 

554 Notes 

555 ----- 

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

557 will be updated when each duplicate edge is added. 

558 

559 Edge attributes specified in an ebunch take precedence over 

560 attributes specified via keyword arguments. 

561 

562 Default keys are generated using the method ``new_edge_key()``. 

563 This method can be overridden by subclassing the base class and 

564 providing a custom ``new_edge_key()`` method. 

565 

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

567 a `RuntimeError` can be raised with message: 

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

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

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

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

572 object to `G.add_edges_from`. 

573 

574 Examples 

575 -------- 

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

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

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

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

580 

581 Associate data to edges 

582 

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

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

585 

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

587 

588 >>> G = nx.MultiGraph([(1, 2), (2, 3), (3, 4)]) 

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

590 >>> # wrong way - will raise RuntimeError 

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

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

593 >>> assigned_keys = G.add_edges_from(list((5, n) for n in G.nodes)) 

594 """ 

595 keylist = [] 

596 for e in ebunch_to_add: 

597 ne = len(e) 

598 if ne == 4: 

599 u, v, key, dd = e 

600 elif ne == 3: 

601 u, v, dd = e 

602 key = None 

603 elif ne == 2: 

604 u, v = e 

605 dd = {} 

606 key = None 

607 else: 

608 msg = f"Edge tuple {e} must be a 2-tuple, 3-tuple or 4-tuple." 

609 raise NetworkXError(msg) 

610 ddd = {} 

611 ddd.update(attr) 

612 try: 

613 ddd.update(dd) 

614 except (TypeError, ValueError): 

615 if ne != 3: 

616 raise 

617 key = dd # ne == 3 with 3rd value not dict, must be a key 

618 key = self.add_edge(u, v, key) 

619 self[u][v][key].update(ddd) 

620 keylist.append(key) 

621 nx._clear_cache(self) 

622 return keylist 

623 

624 def remove_edge(self, u, v, key=None): 

625 """Remove an edge between u and v. 

626 

627 Parameters 

628 ---------- 

629 u, v : nodes 

630 Remove an edge between nodes u and v. 

631 key : hashable identifier, optional (default=None) 

632 Used to distinguish multiple edges between a pair of nodes. 

633 If None, remove a single edge between u and v. If there are 

634 multiple edges, removes the last edge added in terms of 

635 insertion order. 

636 

637 Raises 

638 ------ 

639 NetworkXError 

640 If there is not an edge between u and v, or 

641 if there is no edge with the specified key. 

642 

643 See Also 

644 -------- 

645 remove_edges_from : remove a collection of edges 

646 

647 Examples 

648 -------- 

649 >>> G = nx.MultiGraph() 

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

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

652 >>> e = (1, 2) 

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

654 

655 For multiple edges 

656 

657 >>> G = nx.MultiGraph() # or MultiDiGraph, etc 

658 >>> G.add_edges_from([(1, 2), (1, 2), (1, 2)]) # key_list returned 

659 [0, 1, 2] 

660 

661 When ``key=None`` (the default), edges are removed in the opposite 

662 order that they were added: 

663 

664 >>> G.remove_edge(1, 2) 

665 >>> G.edges(keys=True) 

666 MultiEdgeView([(1, 2, 0), (1, 2, 1)]) 

667 >>> G.remove_edge(2, 1) # edges are not directed 

668 >>> G.edges(keys=True) 

669 MultiEdgeView([(1, 2, 0)]) 

670 

671 For edges with keys 

672 

673 >>> G = nx.MultiGraph() 

674 >>> G.add_edge(1, 2, key="first") 

675 'first' 

676 >>> G.add_edge(1, 2, key="second") 

677 'second' 

678 >>> G.remove_edge(1, 2, key="first") 

679 >>> G.edges(keys=True) 

680 MultiEdgeView([(1, 2, 'second')]) 

681 

682 """ 

683 try: 

684 d = self._adj[u][v] 

685 except KeyError as err: 

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

687 # remove the edge with specified data 

688 if key is None: 

689 d.popitem() 

690 else: 

691 try: 

692 del d[key] 

693 except KeyError as err: 

694 msg = f"The edge {u}-{v} with key {key} is not in the graph." 

695 raise NetworkXError(msg) from err 

696 if len(d) == 0: 

697 # remove the key entries if last edge 

698 del self._adj[u][v] 

699 if u != v: # check for selfloop 

700 del self._adj[v][u] 

701 nx._clear_cache(self) 

702 

703 def remove_edges_from(self, ebunch): 

704 """Remove all edges specified in ebunch. 

705 

706 Parameters 

707 ---------- 

708 ebunch: list or container of edge tuples 

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

710 from the graph. The edges can be: 

711 

712 - 2-tuples (u, v) A single edge between u and v is removed. 

713 - 3-tuples (u, v, key) The edge identified by key is removed. 

714 - 4-tuples (u, v, key, data) where data is ignored. 

715 

716 See Also 

717 -------- 

718 remove_edge : remove a single edge 

719 

720 Notes 

721 ----- 

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

723 

724 Examples 

725 -------- 

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

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

728 >>> G.remove_edges_from(ebunch) 

729 

730 Removing multiple copies of edges 

731 

732 >>> G = nx.MultiGraph() 

733 >>> keys = G.add_edges_from([(1, 2), (1, 2), (1, 2)]) 

734 >>> G.remove_edges_from([(1, 2), (2, 1)]) # edges aren't directed 

735 >>> list(G.edges()) 

736 [(1, 2)] 

737 >>> G.remove_edges_from([(1, 2), (1, 2)]) # silently ignore extra copy 

738 >>> list(G.edges) # now empty graph 

739 [] 

740 

741 When the edge is a 2-tuple ``(u, v)`` but there are multiple edges between 

742 u and v in the graph, the most recent edge (in terms of insertion 

743 order) is removed. 

744 

745 >>> G = nx.MultiGraph() 

746 >>> for key in ("x", "y", "a"): 

747 ... k = G.add_edge(0, 1, key=key) 

748 >>> G.edges(keys=True) 

749 MultiEdgeView([(0, 1, 'x'), (0, 1, 'y'), (0, 1, 'a')]) 

750 >>> G.remove_edges_from([(0, 1)]) 

751 >>> G.edges(keys=True) 

752 MultiEdgeView([(0, 1, 'x'), (0, 1, 'y')]) 

753 

754 """ 

755 for e in ebunch: 

756 try: 

757 self.remove_edge(*e[:3]) 

758 except NetworkXError: 

759 pass 

760 nx._clear_cache(self) 

761 

762 def has_edge(self, u, v, key=None): 

763 """Returns True if the graph has an edge between nodes u and v. 

764 

765 This is the same as `v in G[u] or key in G[u][v]` 

766 without KeyError exceptions. 

767 

768 Parameters 

769 ---------- 

770 u, v : nodes 

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

772 

773 key : hashable identifier, optional (default=None) 

774 If specified return True only if the edge with 

775 key is found. 

776 

777 Returns 

778 ------- 

779 edge_ind : bool 

780 True if edge is in the graph, False otherwise. 

781 

782 Examples 

783 -------- 

784 Can be called either using two nodes u, v, an edge tuple (u, v), 

785 or an edge tuple (u, v, key). 

786 

787 >>> G = nx.MultiGraph() # or MultiDiGraph 

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

789 >>> G.has_edge(0, 1) # using two nodes 

790 True 

791 >>> e = (0, 1) 

792 >>> G.has_edge(*e) # e is a 2-tuple (u, v) 

793 True 

794 >>> G.add_edge(0, 1, key="a") 

795 'a' 

796 >>> G.has_edge(0, 1, key="a") # specify key 

797 True 

798 >>> G.has_edge(1, 0, key="a") # edges aren't directed 

799 True 

800 >>> e = (0, 1, "a") 

801 >>> G.has_edge(*e) # e is a 3-tuple (u, v, 'a') 

802 True 

803 

804 The following syntax are equivalent: 

805 

806 >>> G.has_edge(0, 1) 

807 True 

808 >>> 1 in G[0] # though this gives :exc:`KeyError` if 0 not in G 

809 True 

810 >>> 0 in G[1] # other order; also gives :exc:`KeyError` if 0 not in G 

811 True 

812 

813 """ 

814 try: 

815 if key is None: 

816 return v in self._adj[u] 

817 else: 

818 return key in self._adj[u][v] 

819 except KeyError: 

820 return False 

821 

822 @cached_property 

823 def edges(self): 

824 """Returns an iterator over the edges. 

825 

826 edges(self, nbunch=None, data=False, keys=False, default=None) 

827 

828 The MultiEdgeView provides set-like operations on the edge-tuples 

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

830 an EdgeDataView object which allows control of access to edge 

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

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

833 attribute for the edge from ``u`` to ``v`` with key ``k`` while 

834 ``for (u, v, k, c) in G.edges(data='color', keys=True, default="red"):`` 

835 iterates through all the edges yielding the color attribute with 

836 default `'red'` if no color attribute exists. 

837 

838 Edges are returned as tuples with optional data and keys 

839 in the order (node, neighbor, key, data). If ``keys=True`` is not 

840 provided, the tuples will just be (node, neighbor, data), but 

841 multiple tuples with the same node and neighbor will be generated 

842 when multiple edges exist between two nodes. 

843 

844 Parameters 

845 ---------- 

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

847 The view will only report edges from these nodes. 

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

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

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

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

852 keys : bool, optional (default=False) 

853 If True, return edge keys with each edge, creating (u, v, k) 

854 tuples or (u, v, k, d) tuples if data is also requested. 

855 default : value, optional (default=None) 

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

857 Only relevant if data is not True or False. 

858 

859 Returns 

860 ------- 

861 edges : MultiEdgeView 

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

863 (u, v, k) or (u, v, k, d) tuples of edges, but can also be 

864 used for attribute lookup as ``edges[u, v, k]['foo']``. 

865 

866 Notes 

867 ----- 

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

869 For directed graphs this returns the out-edges. 

870 

871 Examples 

872 -------- 

873 >>> G = nx.MultiGraph() 

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

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

876 >>> key2 = G.add_edge(2, 1, weight=2) # multi-edge 

877 >>> [e for e in G.edges()] 

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

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

880 MultiEdgeDataView([(0, 1, {}), (1, 2, {}), (1, 2, {'weight': 2}), (2, 3, {'weight': 5})]) 

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

882 MultiEdgeDataView([(0, 1, 1), (1, 2, 1), (1, 2, 2), (2, 3, 5)]) 

883 >>> G.edges(keys=True) # default keys are integers 

884 MultiEdgeView([(0, 1, 0), (1, 2, 0), (1, 2, 1), (2, 3, 0)]) 

885 >>> G.edges.data(keys=True) 

886 MultiEdgeDataView([(0, 1, 0, {}), (1, 2, 0, {}), (1, 2, 1, {'weight': 2}), (2, 3, 0, {'weight': 5})]) 

887 >>> G.edges.data("weight", default=1, keys=True) 

888 MultiEdgeDataView([(0, 1, 0, 1), (1, 2, 0, 1), (1, 2, 1, 2), (2, 3, 0, 5)]) 

889 >>> G.edges([0, 3]) # Note ordering of tuples from listed sources 

890 MultiEdgeDataView([(0, 1), (3, 2)]) 

891 >>> G.edges([0, 3, 2, 1]) # Note ordering of tuples 

892 MultiEdgeDataView([(0, 1), (3, 2), (2, 1), (2, 1)]) 

893 >>> G.edges(0) 

894 MultiEdgeDataView([(0, 1)]) 

895 """ 

896 return MultiEdgeView(self) 

897 

898 def get_edge_data(self, u, v, key=None, default=None): 

899 """Returns the attribute dictionary associated with edge (u, v, 

900 key). 

901 

902 If a key is not provided, returns a dictionary mapping edge keys 

903 to attribute dictionaries for each edge between u and v. 

904 

905 This is identical to `G[u][v][key]` except the default is returned 

906 instead of an exception is the edge doesn't exist. 

907 

908 Parameters 

909 ---------- 

910 u, v : nodes 

911 

912 default : any Python object (default=None) 

913 Value to return if the specific edge (u, v, key) is not 

914 found, OR if there are no edges between u and v and no key 

915 is specified. 

916 

917 key : hashable identifier, optional (default=None) 

918 Return data only for the edge with specified key, as an 

919 attribute dictionary (rather than a dictionary mapping keys 

920 to attribute dictionaries). 

921 

922 Returns 

923 ------- 

924 edge_dict : dictionary 

925 The edge attribute dictionary, OR a dictionary mapping edge 

926 keys to attribute dictionaries for each of those edges if no 

927 specific key is provided (even if there's only one edge 

928 between u and v). 

929 

930 Examples 

931 -------- 

932 >>> G = nx.MultiGraph() # or MultiDiGraph 

933 >>> key = G.add_edge(0, 1, key="a", weight=7) 

934 >>> G[0][1]["a"] # key='a' 

935 {'weight': 7} 

936 >>> G.edges[0, 1, "a"] # key='a' 

937 {'weight': 7} 

938 

939 Warning: we protect the graph data structure by making 

940 `G.edges` and `G[1][2]` read-only dict-like structures. 

941 However, you can assign values to attributes in e.g. 

942 `G.edges[1, 2, 'a']` or `G[1][2]['a']` using an additional 

943 bracket as shown next. You need to specify all edge info 

944 to assign to the edge data associated with an edge. 

945 

946 >>> G[0][1]["a"]["weight"] = 10 

947 >>> G.edges[0, 1, "a"]["weight"] = 10 

948 >>> G[0][1]["a"]["weight"] 

949 10 

950 >>> G.edges[1, 0, "a"]["weight"] 

951 10 

952 

953 >>> G = nx.MultiGraph() # or MultiDiGraph 

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

955 >>> G.edges[0, 1, 0]["weight"] = 5 

956 >>> G.get_edge_data(0, 1) 

957 {0: {'weight': 5}} 

958 >>> e = (0, 1) 

959 >>> G.get_edge_data(*e) # tuple form 

960 {0: {'weight': 5}} 

961 >>> G.get_edge_data(3, 0) # edge not in graph, returns None 

962 >>> G.get_edge_data(3, 0, default=0) # edge not in graph, return default 

963 0 

964 >>> G.get_edge_data(1, 0, 0) # specific key gives back 

965 {'weight': 5} 

966 """ 

967 try: 

968 if key is None: 

969 return self._adj[u][v] 

970 else: 

971 return self._adj[u][v][key] 

972 except KeyError: 

973 return default 

974 

975 @cached_property 

976 def degree(self): 

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

978 

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

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

981 edges incident to that node. 

982 

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

984 lookup for the degree for a single node. 

985 

986 Parameters 

987 ---------- 

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

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

990 

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

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

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

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

995 

996 Returns 

997 ------- 

998 MultiDegreeView or int 

999 If multiple nodes are requested (the default), returns a `MultiDegreeView` 

1000 mapping nodes to their degree. 

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

1002 

1003 Examples 

1004 -------- 

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

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

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

1008 1 

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

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

1011 

1012 """ 

1013 return MultiDegreeView(self) 

1014 

1015 def is_multigraph(self): 

1016 """Returns True if graph is a multigraph, False otherwise.""" 

1017 return True 

1018 

1019 def is_directed(self): 

1020 """Returns True if graph is directed, False otherwise.""" 

1021 return False 

1022 

1023 def copy(self, as_view=False): 

1024 """Returns a copy of the graph. 

1025 

1026 The copy method by default returns an independent shallow copy 

1027 of the graph and attributes. That is, if an attribute is a 

1028 container, that container is shared by the original an the copy. 

1029 Use Python's `copy.deepcopy` for new containers. 

1030 

1031 If `as_view` is True then a view is returned instead of a copy. 

1032 

1033 Notes 

1034 ----- 

1035 All copies reproduce the graph structure, but data attributes 

1036 may be handled in different ways. There are four types of copies 

1037 of a graph that people might want. 

1038 

1039 Deepcopy -- A "deepcopy" copies the graph structure as well as 

1040 all data attributes and any objects they might contain. 

1041 The entire graph object is new so that changes in the copy 

1042 do not affect the original object. (see Python's copy.deepcopy) 

1043 

1044 Data Reference (Shallow) -- For a shallow copy the graph structure 

1045 is copied but the edge, node and graph attribute dicts are 

1046 references to those in the original graph. This saves 

1047 time and memory but could cause confusion if you change an attribute 

1048 in one graph and it changes the attribute in the other. 

1049 NetworkX does not provide this level of shallow copy. 

1050 

1051 Independent Shallow -- This copy creates new independent attribute 

1052 dicts and then does a shallow copy of the attributes. That is, any 

1053 attributes that are containers are shared between the new graph 

1054 and the original. This is exactly what `dict.copy()` provides. 

1055 You can obtain this style copy using: 

1056 

1057 >>> G = nx.path_graph(5) 

1058 >>> H = G.copy() 

1059 >>> H = G.copy(as_view=False) 

1060 >>> H = nx.Graph(G) 

1061 >>> H = G.__class__(G) 

1062 

1063 Fresh Data -- For fresh data, the graph structure is copied while 

1064 new empty data attribute dicts are created. The resulting graph 

1065 is independent of the original and it has no edge, node or graph 

1066 attributes. Fresh copies are not enabled. Instead use: 

1067 

1068 >>> H = G.__class__() 

1069 >>> H.add_nodes_from(G) 

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

1071 

1072 View -- Inspired by dict-views, graph-views act like read-only 

1073 versions of the original graph, providing a copy of the original 

1074 structure without requiring any memory for copying the information. 

1075 

1076 See the Python copy module for more information on shallow 

1077 and deep copies, https://docs.python.org/3/library/copy.html. 

1078 

1079 Parameters 

1080 ---------- 

1081 as_view : bool, optional (default=False) 

1082 If True, the returned graph-view provides a read-only view 

1083 of the original graph without actually copying any data. 

1084 

1085 Returns 

1086 ------- 

1087 G : Graph 

1088 A copy of the graph. 

1089 

1090 See Also 

1091 -------- 

1092 to_directed: return a directed copy of the graph. 

1093 

1094 Examples 

1095 -------- 

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

1097 >>> H = G.copy() 

1098 

1099 """ 

1100 if as_view is True: 

1101 return nx.graphviews.generic_graph_view(self) 

1102 G = self.__class__() 

1103 G.graph.update(self.graph) 

1104 G.add_nodes_from((n, d.copy()) for n, d in self._node.items()) 

1105 G.add_edges_from( 

1106 (u, v, key, datadict.copy()) 

1107 for u, nbrs in self._adj.items() 

1108 for v, keydict in nbrs.items() 

1109 for key, datadict in keydict.items() 

1110 ) 

1111 return G 

1112 

1113 def to_directed(self, as_view=False): 

1114 """Returns a directed representation of the graph. 

1115 

1116 Returns 

1117 ------- 

1118 G : MultiDiGraph 

1119 A directed graph with the same name, same nodes, and with 

1120 each edge (u, v, k, data) replaced by two directed edges 

1121 (u, v, k, data) and (v, u, k, data). 

1122 

1123 Notes 

1124 ----- 

1125 This returns a "deepcopy" of the edge, node, and 

1126 graph attributes which attempts to completely copy 

1127 all of the data and references. 

1128 

1129 This is in contrast to the similar D=MultiDiGraph(G) which 

1130 returns a shallow copy of the data. 

1131 

1132 See the Python copy module for more information on shallow 

1133 and deep copies, https://docs.python.org/3/library/copy.html. 

1134 

1135 Warning: If you have subclassed MultiGraph to use dict-like objects 

1136 in the data structure, those changes do not transfer to the 

1137 MultiDiGraph created by this method. 

1138 

1139 Examples 

1140 -------- 

1141 >>> G = nx.MultiGraph() 

1142 >>> G.add_edge(0, 1) 

1143 0 

1144 >>> G.add_edge(0, 1) 

1145 1 

1146 >>> H = G.to_directed() 

1147 >>> list(H.edges) 

1148 [(0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1)] 

1149 

1150 If already directed, return a (deep) copy 

1151 

1152 >>> G = nx.MultiDiGraph() 

1153 >>> G.add_edge(0, 1) 

1154 0 

1155 >>> H = G.to_directed() 

1156 >>> list(H.edges) 

1157 [(0, 1, 0)] 

1158 """ 

1159 graph_class = self.to_directed_class() 

1160 if as_view is True: 

1161 return nx.graphviews.generic_graph_view(self, graph_class) 

1162 # deepcopy when not a view 

1163 G = graph_class() 

1164 G.graph.update(deepcopy(self.graph)) 

1165 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) 

1166 G.add_edges_from( 

1167 (u, v, key, deepcopy(datadict)) 

1168 for u, nbrs in self.adj.items() 

1169 for v, keydict in nbrs.items() 

1170 for key, datadict in keydict.items() 

1171 ) 

1172 return G 

1173 

1174 def to_undirected(self, as_view=False): 

1175 """Returns an undirected copy of the graph. 

1176 

1177 Returns 

1178 ------- 

1179 G : Graph/MultiGraph 

1180 A deepcopy of the graph. 

1181 

1182 See Also 

1183 -------- 

1184 copy, add_edge, add_edges_from 

1185 

1186 Notes 

1187 ----- 

1188 This returns a "deepcopy" of the edge, node, and 

1189 graph attributes which attempts to completely copy 

1190 all of the data and references. 

1191 

1192 This is in contrast to the similar `G = nx.MultiGraph(D)` 

1193 which returns a shallow copy of the data. 

1194 

1195 See the Python copy module for more information on shallow 

1196 and deep copies, https://docs.python.org/3/library/copy.html. 

1197 

1198 Warning: If you have subclassed MultiGraph to use dict-like 

1199 objects in the data structure, those changes do not transfer 

1200 to the MultiGraph created by this method. 

1201 

1202 Examples 

1203 -------- 

1204 >>> G = nx.MultiGraph([(0, 1), (0, 1), (1, 2)])