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

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

2from copy import deepcopy 

3from functools import cached_property 

4 

5import networkx as nx 

6from networkx import NetworkXError, convert 

7from networkx.classes.coreviews import MultiAdjacencyView 

8from networkx.classes.graph import Graph 

9from networkx.classes.reportviews import MultiDegreeView, MultiEdgeView 

10 

11__all__ = ["MultiGraph"] 

12 

13 

14class MultiGraph(Graph): 

15 """ 

16 An undirected graph class that can store multiedges. 

17 

18 Multiedges are multiple edges between two nodes. Each edge 

19 can hold optional data or attributes. 

20 

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

22 

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

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

25 

26 Edges are represented as links between nodes with optional 

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

28 distinguish between multiple edges that have the same source and 

29 destination nodes. 

30 

31 Parameters 

32 ---------- 

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

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

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

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

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

38 SciPy sparse array, or PyGraphviz graph. 

39 

40 multigraph_input : bool or None (default None) 

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

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

43 dict-of-dict-of-dict-of-dict structure keyed by 

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

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

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

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

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

49 keyed by node to neighbors. 

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

51 the treatment for False is tried. 

52 

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

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

55 

56 See Also 

57 -------- 

58 Graph 

59 DiGraph 

60 MultiDiGraph 

61 

62 Examples 

63 -------- 

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

65 no edges. 

66 

67 >>> G = nx.MultiGraph() 

68 

69 G can be grown in several ways. 

70 

71 **Nodes:** 

72 

73 Add one node at a time: 

74 

75 >>> G.add_node(1) 

76 

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

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

79 

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

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

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

83 >>> G.add_nodes_from(H) 

84 

85 In addition to strings and integers any hashable Python object 

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

87 or even another Graph. 

88 

89 >>> G.add_node(H) 

90 

91 **Edges:** 

92 

93 G can also be grown by adding edges. 

94 

95 Add one edge, 

96 

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

98 

99 a list of edges, 

100 

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

102 

103 or a collection of edges, 

104 

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

106 

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

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

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

110 By default the key is the lowest unused integer. 

111 

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

113 >>> G[4] 

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

115 

116 **Attributes:** 

117 

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

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

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

121 add_edge, add_node or direct manipulation of the attribute 

122 dictionaries named graph, node and edge respectively. 

123 

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

125 >>> G.graph 

126 {'day': 'Friday'} 

127 

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

129 

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

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

132 >>> G.nodes[1] 

133 {'time': '5pm'} 

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

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

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

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

138 

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

140 notation, or G.edges. 

141 

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

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

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

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

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

147 

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

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

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

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

152 

153 **Shortcuts:** 

154 

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

156 

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

158 True 

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

160 [1, 2] 

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

162 5 

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

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

165 

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

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

168 

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

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

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

172 ... if "weight" in eattr: 

173 ... # Do something useful with the edges 

174 ... pass 

175 

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

177 

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

179 ... if weight is not None: 

180 ... # Do something useful with the edges 

181 ... pass 

182 

183 **Reporting:** 

184 

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

186 Reporting usually provides views instead of containers to reduce memory 

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

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

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

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

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

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

193 

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

195 

196 **Subclasses (Advanced):** 

197 

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

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

200 The next dict (adjlist_dict) represents the adjacency information 

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

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

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

204 values keyed by attribute names. 

205 

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

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

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

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

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

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

212 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory, 

213 adjlist_outer_dict_factory, edge_key_dict_factory, edge_attr_dict_factory 

214 and graph_attr_dict_factory. 

215 

216 node_dict_factory : function, (default: dict) 

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

218 attributes, keyed by node id. 

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

220 

221 node_attr_dict_factory: function, (default: dict) 

222 Factory function to be used to create the node attribute 

223 dict which holds attribute values keyed by attribute name. 

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

225 

226 adjlist_outer_dict_factory : function, (default: dict) 

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

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

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

230 

231 adjlist_inner_dict_factory : function, (default: dict) 

232 Factory function to be used to create the adjacency list 

233 dict which holds multiedge key dicts keyed by neighbor. 

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

235 

236 edge_key_dict_factory : function, (default: dict) 

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

238 which holds edge data keyed by edge key. 

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

240 

241 edge_attr_dict_factory : function, (default: dict) 

242 Factory function to be used to create the edge attribute 

243 dict which holds attribute values keyed by attribute name. 

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

245 

246 graph_attr_dict_factory : function, (default: dict) 

247 Factory function to be used to create the graph attribute 

248 dict which holds attribute values keyed by attribute name. 

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

250 

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

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

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

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

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

256 

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

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

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

260 

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

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

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

264 

265 **Subclassing Example** 

266 

267 Create a low memory graph class that effectively disallows edge 

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

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

270 

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

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

273 ... 

274 ... def single_edge_dict(self): 

275 ... return self.all_edge_dict 

276 ... 

277 ... edge_attr_dict_factory = single_edge_dict 

278 >>> G = ThinGraph() 

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

280 >>> G[2][1] 

281 {'weight': 1} 

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

283 >>> G[2][1] is G[2][2] 

284 True 

285 """ 

286 

287 # node_dict_factory = dict # already assigned in Graph 

288 # adjlist_outer_dict_factory = dict 

289 # adjlist_inner_dict_factory = dict 

290 edge_key_dict_factory = dict 

291 # edge_attr_dict_factory = dict 

292 

293 def to_directed_class(self): 

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

295 

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

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

298 """ 

299 return nx.MultiDiGraph 

300 

301 def to_undirected_class(self): 

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

303 

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

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

306 """ 

307 return MultiGraph 

308 

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

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

311 

312 Parameters 

313 ---------- 

314 incoming_graph_data : input graph 

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

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

317 NetworkX graph object. If the corresponding optional Python 

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

319 SciPy sparse array, or a PyGraphviz graph. 

320 

321 multigraph_input : bool or None (default None) 

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

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

324 dict-of-dict-of-dict-of-dict structure keyed by 

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

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

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

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

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

330 keyed by node to neighbors. 

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

332 the treatment for False is tried. 

333 

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

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

336 

337 See Also 

338 -------- 

339 convert 

340 

341 Examples 

342 -------- 

343 >>> G = nx.MultiGraph() 

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

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

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

347 

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

349 

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

351 >>> G.graph 

352 {'day': 'Friday'} 

353 

354 """ 

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

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

357 Graph.__init__(self) 

358 try: 

359 convert.from_dict_of_dicts( 

360 incoming_graph_data, create_using=self, multigraph_input=True 

361 ) 

362 self.graph.update(attr) 

363 except Exception as err: 

364 if multigraph_input is True: 

365 raise nx.NetworkXError( 

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

367 ) 

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

369 else: 

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

371 

372 @cached_property 

373 def adj(self): 

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

375 

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

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

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

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

380 

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

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

383 

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

385 

386 Examples 

387 -------- 

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

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

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

391 >>> result = set() 

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

393 ... result.add(data.get('weight', 1)) 

394 >>> result 

395 {1, 3} 

396 

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

398 """ 

399 return MultiAdjacencyView(self._adj) 

400 

401 def new_edge_key(self, u, v): 

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

403 

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

405 

406 Notes 

407 ----- 

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

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

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

411 further new_edge_keys may not be in this order. 

412 

413 Parameters 

414 ---------- 

415 u, v : nodes 

416 

417 Returns 

418 ------- 

419 key : int 

420 """ 

421 try: 

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

423 except KeyError: 

424 return 0 

425 key = len(keydict) 

426 while key in keydict: 

427 key += 1 

428 return key 

429 

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

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

432 

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

434 not already in the graph. 

435 

436 Edge attributes can be specified with keywords or by directly 

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

438 

439 Parameters 

440 ---------- 

441 u_for_edge, v_for_edge : nodes 

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

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

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

445 Used to distinguish multiedges between a pair of nodes. 

446 attr : keyword arguments, optional 

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

448 keyword arguments. 

449 

450 Returns 

451 ------- 

452 The edge key assigned to the edge. 

453 

454 See Also 

455 -------- 

456 add_edges_from : add a collection of edges 

457 

458 Notes 

459 ----- 

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

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

462 

463 NetworkX algorithms designed for weighted graphs cannot use 

464 multigraphs directly because it is not clear how to handle 

465 multiedge weights. Convert to Graph using edge attribute 

466 'weight' to enable weighted graph algorithms. 

467 

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

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

470 providing a custom `new_edge_key()` method. 

471 

472 Examples 

473 -------- 

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

475 

476 >>> G = nx.MultiGraph() 

477 >>> e = (1, 2) 

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

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

480 1 

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

482 [2] 

483 

484 Associate data to edges using keywords: 

485 

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

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

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

489 

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

491 

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

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

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

495 """ 

496 u, v = u_for_edge, v_for_edge 

497 # add nodes 

498 if u not in self._adj: 

499 if u is None: 

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

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

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

503 if v not in self._adj: 

504 if v is None: 

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

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

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

508 if key is None: 

509 key = self.new_edge_key(u, v) 

510 if v in self._adj[u]: 

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

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

513 datadict.update(attr) 

514 keydict[key] = datadict 

515 else: 

516 # selfloops work this way without special treatment 

517 datadict = self.edge_attr_dict_factory() 

518 datadict.update(attr) 

519 keydict = self.edge_key_dict_factory() 

520 keydict[key] = datadict 

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

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

523 return key 

524 

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

526 """Add all the edges in ebunch_to_add. 

527 

528 Parameters 

529 ---------- 

530 ebunch_to_add : container of edges 

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

532 graph. The edges can be: 

533 

534 - 2-tuples (u, v) or 

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

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

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

538 

539 attr : keyword arguments, optional 

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

541 keyword arguments. 

542 

543 Returns 

544 ------- 

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

546 

547 See Also 

548 -------- 

549 add_edge : add a single edge 

550 add_weighted_edges_from : convenient way to add weighted edges 

551 

552 Notes 

553 ----- 

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

555 will be updated when each duplicate edge is added. 

556 

557 Edge attributes specified in an ebunch take precedence over 

558 attributes specified via keyword arguments. 

559 

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

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

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

563 

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

565 a `RuntimeError` can be raised with message: 

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

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

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

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

570 object to `G.add_edges_from`. 

571 

572 Examples 

573 -------- 

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

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

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

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

578 

579 Associate data to edges 

580 

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

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

583 

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

585 

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

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

588 >>> # wrong way - will raise RuntimeError 

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

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

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

592 """ 

593 keylist = [] 

594 for e in ebunch_to_add: 

595 ne = len(e) 

596 if ne == 4: 

597 u, v, key, dd = e 

598 elif ne == 3: 

599 u, v, dd = e 

600 key = None 

601 elif ne == 2: 

602 u, v = e 

603 dd = {} 

604 key = None 

605 else: 

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

607 raise NetworkXError(msg) 

608 ddd = {} 

609 ddd.update(attr) 

610 try: 

611 ddd.update(dd) 

612 except (TypeError, ValueError): 

613 if ne != 3: 

614 raise 

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

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

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

618 keylist.append(key) 

619 return keylist 

620 

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

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

623 

624 Parameters 

625 ---------- 

626 u, v : nodes 

627 Remove an edge between nodes u and v. 

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

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

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

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

632 insertion order. 

633 

634 Raises 

635 ------ 

636 NetworkXError 

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

638 if there is no edge with the specified key. 

639 

640 See Also 

641 -------- 

642 remove_edges_from : remove a collection of edges 

643 

644 Examples 

645 -------- 

646 >>> G = nx.MultiGraph() 

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

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

649 >>> e = (1, 2) 

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

651 

652 For multiple edges 

653 

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

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

656 [0, 1, 2] 

657 

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

659 order that they were added: 

660 

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

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

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

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

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

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

667 

668 For edges with keys 

669 

670 >>> G = nx.MultiGraph() 

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

672 'first' 

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

674 'second' 

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

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

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

678 

679 """ 

680 try: 

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

682 except KeyError as err: 

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

684 # remove the edge with specified data 

685 if key is None: 

686 d.popitem() 

687 else: 

688 try: 

689 del d[key] 

690 except KeyError as err: 

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

692 raise NetworkXError(msg) from err 

693 if len(d) == 0: 

694 # remove the key entries if last edge 

695 del self._adj[u][v] 

696 if u != v: # check for selfloop 

697 del self._adj[v][u] 

698 

699 def remove_edges_from(self, ebunch): 

700 """Remove all edges specified in ebunch. 

701 

702 Parameters 

703 ---------- 

704 ebunch: list or container of edge tuples 

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

706 from the graph. The edges can be: 

707 

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

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

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

711 

712 See Also 

713 -------- 

714 remove_edge : remove a single edge 

715 

716 Notes 

717 ----- 

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

719 

720 Examples 

721 -------- 

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

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

724 >>> G.remove_edges_from(ebunch) 

725 

726 Removing multiple copies of edges 

727 

728 >>> G = nx.MultiGraph() 

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

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

731 >>> list(G.edges()) 

732 [(1, 2)] 

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

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

735 [] 

736 

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

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

739 order) is removed. 

740 

741 >>> G = nx.MultiGraph() 

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

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

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

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

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

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

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

749 

750 """ 

751 for e in ebunch: 

752 try: 

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

754 except NetworkXError: 

755 pass 

756 

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

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

759 

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

761 without KeyError exceptions. 

762 

763 Parameters 

764 ---------- 

765 u, v : nodes 

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

767 

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

769 If specified return True only if the edge with 

770 key is found. 

771 

772 Returns 

773 ------- 

774 edge_ind : bool 

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

776 

777 Examples 

778 -------- 

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

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

781 

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

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

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

785 True 

786 >>> e = (0, 1) 

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

788 True 

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

790 'a' 

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

792 True 

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

794 True 

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

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

797 True 

798 

799 The following syntax are equivalent: 

800 

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

802 True 

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

804 True 

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

806 True 

807 

808 """ 

809 try: 

810 if key is None: 

811 return v in self._adj[u] 

812 else: 

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

814 except KeyError: 

815 return False 

816 

817 @cached_property 

818 def edges(self): 

819 """Returns an iterator over the edges. 

820 

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

822 

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

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

825 an EdgeDataView object which allows control of access to edge 

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

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

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

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

830 iterates through all the edges yielding the color attribute with 

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

832 

833 Edges are returned as tuples with optional data and keys 

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

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

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

837 when multiple edges exist between two nodes. 

838 

839 Parameters 

840 ---------- 

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

842 The view will only report edges from these nodes. 

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

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

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

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

847 keys : bool, optional (default=False) 

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

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

850 default : value, optional (default=None) 

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

852 Only relevant if data is not True or False. 

853 

854 Returns 

855 ------- 

856 edges : MultiEdgeView 

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

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

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

860 

861 Notes 

862 ----- 

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

864 For directed graphs this returns the out-edges. 

865 

866 Examples 

867 -------- 

868 >>> G = nx.MultiGraph() 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

888 >>> G.edges(0) 

889 MultiEdgeDataView([(0, 1)]) 

890 """ 

891 return MultiEdgeView(self) 

892 

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

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

895 key). 

896 

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

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

899 

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

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

902 

903 Parameters 

904 ---------- 

905 u, v : nodes 

906 

907 default : any Python object (default=None) 

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

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

910 is specified. 

911 

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

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

914 attribute dictionary (rather than a dictionary mapping keys 

915 to attribute dictionaries). 

916 

917 Returns 

918 ------- 

919 edge_dict : dictionary 

920 The edge attribute dictionary, OR a dictionary mapping edge 

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

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

923 between u and v). 

924 

925 Examples 

926 -------- 

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

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

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

930 {'weight': 7} 

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

932 {'weight': 7} 

933 

934 Warning: we protect the graph data structure by making 

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

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

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

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

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

940 

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

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

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

944 10 

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

946 10 

947 

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

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

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

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

952 {0: {'weight': 5}} 

953 >>> e = (0, 1) 

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

955 {0: {'weight': 5}} 

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

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

958 0 

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

960 {'weight': 5} 

961 """ 

962 try: 

963 if key is None: 

964 return self._adj[u][v] 

965 else: 

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

967 except KeyError: 

968 return default 

969 

970 @cached_property 

971 def degree(self): 

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

973 

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

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

976 edges incident to that node. 

977 

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

979 lookup for the degree for a single node. 

980 

981 Parameters 

982 ---------- 

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

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

985 

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

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

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

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

990 

991 Returns 

992 ------- 

993 MultiDegreeView or int 

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

995 mapping nodes to their degree. 

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

997 

998 Examples 

999 -------- 

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

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

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

1003 1 

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

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

1006 

1007 """ 

1008 return MultiDegreeView(self) 

1009 

1010 def is_multigraph(self): 

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

1012 return True 

1013 

1014 def is_directed(self): 

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

1016 return False 

1017 

1018 def copy(self, as_view=False): 

1019 """Returns a copy of the graph. 

1020 

1021 The copy method by default returns an independent shallow copy 

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

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

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

1025 

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

1027 

1028 Notes 

1029 ----- 

1030 All copies reproduce the graph structure, but data attributes 

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

1032 of a graph that people might want. 

1033 

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

1035 all data attributes and any objects they might contain. 

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

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

1038 

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

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

1041 references to those in the original graph. This saves 

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

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

1044 NetworkX does not provide this level of shallow copy. 

1045 

1046 Independent Shallow -- This copy creates new independent attribute 

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

1048 attributes that are containers are shared between the new graph 

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

1050 You can obtain this style copy using: 

1051 

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

1053 >>> H = G.copy() 

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

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

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

1057 

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

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

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

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

1062 

1063 >>> H = G.__class__() 

1064 >>> H.add_nodes_from(G) 

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

1066 

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

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

1069 structure without requiring any memory for copying the information. 

1070 

1071 See the Python copy module for more information on shallow 

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

1073 

1074 Parameters 

1075 ---------- 

1076 as_view : bool, optional (default=False) 

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

1078 of the original graph without actually copying any data. 

1079 

1080 Returns 

1081 ------- 

1082 G : Graph 

1083 A copy of the graph. 

1084 

1085 See Also 

1086 -------- 

1087 to_directed: return a directed copy of the graph. 

1088 

1089 Examples 

1090 -------- 

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

1092 >>> H = G.copy() 

1093 

1094 """ 

1095 if as_view is True: 

1096 return nx.graphviews.generic_graph_view(self) 

1097 G = self.__class__() 

1098 G.graph.update(self.graph) 

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

1100 G.add_edges_from( 

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

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

1103 for v, keydict in nbrs.items() 

1104 for key, datadict in keydict.items() 

1105 ) 

1106 return G 

1107 

1108 def to_directed(self, as_view=False): 

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

1110 

1111 Returns 

1112 ------- 

1113 G : MultiDiGraph 

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

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

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

1117 

1118 Notes 

1119 ----- 

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

1121 graph attributes which attempts to completely copy 

1122 all of the data and references. 

1123 

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

1125 returns a shallow copy of the data. 

1126 

1127 See the Python copy module for more information on shallow 

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

1129 

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

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

1132 MultiDiGraph created by this method. 

1133 

1134 Examples 

1135 -------- 

1136 >>> G = nx.MultiGraph() 

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

1138 0 

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

1140 1 

1141 >>> H = G.to_directed() 

1142 >>> list(H.edges) 

1143 [(0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1)] 

1144 

1145 If already directed, return a (deep) copy 

1146 

1147 >>> G = nx.MultiDiGraph() 

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

1149 0 

1150 >>> H = G.to_directed() 

1151 >>> list(H.edges) 

1152 [(0, 1, 0)] 

1153 """ 

1154 graph_class = self.to_directed_class() 

1155 if as_view is True: 

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

1157 # deepcopy when not a view 

1158 G = graph_class() 

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

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

1161 G.add_edges_from( 

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

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

1164 for v, keydict in nbrs.items() 

1165 for key, datadict in keydict.items() 

1166 ) 

1167 return G 

1168 

1169 def to_undirected(self, as_view=False): 

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

1171 

1172 Returns 

1173 ------- 

1174 G : Graph/MultiGraph 

1175 A deepcopy of the graph. 

1176 

1177 See Also 

1178 -------- 

1179 copy, add_edge, add_edges_from 

1180 

1181 Notes 

1182 ----- 

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

1184 graph attributes which attempts to completely copy 

1185 all of the data and references. 

1186 

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

1188 which returns a shallow copy of the data. 

1189 

1190 See the Python copy module for more information on shallow 

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

1192 

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

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

1195 to the MultiGraph created by this method. 

1196 

1197 Examples 

1198 -------- 

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

1200 >>> H = G.to_directed() 

1201 >>> list(H.edges) 

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

1203 >>> G2 = H.to_undirected() 

1204 >>> list(G2.edges) 

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

1206 """ 

1207 graph_class = self.to_undirected_class()