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

1"""Functional interface to graph methods and assorted utilities.""" 

2 

3from collections import Counter 

4from itertools import chain 

5 

6import networkx as nx 

7from networkx.utils import not_implemented_for, pairwise 

8 

9__all__ = [ 

10 "nodes", 

11 "edges", 

12 "degree", 

13 "degree_histogram", 

14 "neighbors", 

15 "number_of_nodes", 

16 "number_of_edges", 

17 "density", 

18 "is_directed", 

19 "freeze", 

20 "is_frozen", 

21 "subgraph", 

22 "induced_subgraph", 

23 "edge_subgraph", 

24 "restricted_view", 

25 "to_directed", 

26 "to_undirected", 

27 "add_star", 

28 "add_path", 

29 "add_cycle", 

30 "create_empty_copy", 

31 "set_node_attributes", 

32 "get_node_attributes", 

33 "remove_node_attributes", 

34 "set_edge_attributes", 

35 "get_edge_attributes", 

36 "remove_edge_attributes", 

37 "all_neighbors", 

38 "non_neighbors", 

39 "non_edges", 

40 "common_neighbors", 

41 "is_weighted", 

42 "is_negatively_weighted", 

43 "is_empty", 

44 "selfloop_edges", 

45 "nodes_with_selfloops", 

46 "number_of_selfloops", 

47 "path_weight", 

48 "is_path", 

49] 

50 

51 

52def nodes(G): 

53 """Returns a NodeView over the graph nodes. 

54 

55 This function wraps the :func:`G.nodes <networkx.Graph.nodes>` property. 

56 """ 

57 return G.nodes() 

58 

59 

60def edges(G, nbunch=None): 

61 """Returns an edge view of edges incident to nodes in nbunch. 

62 

63 Return all edges if nbunch is unspecified or nbunch=None. 

64 

65 For digraphs, edges=out_edges 

66 

67 This function wraps the :func:`G.edges <networkx.Graph.edges>` property. 

68 """ 

69 return G.edges(nbunch) 

70 

71 

72def degree(G, nbunch=None, weight=None): 

73 """Returns a degree view of single node or of nbunch of nodes. 

74 If nbunch is omitted, then return degrees of *all* nodes. 

75 

76 This function wraps the :func:`G.degree <networkx.Graph.degree>` property. 

77 """ 

78 return G.degree(nbunch, weight) 

79 

80 

81def neighbors(G, n): 

82 """Returns an iterator over all neighbors of node n. 

83 

84 This function wraps the :func:`G.neighbors <networkx.Graph.neighbors>` function. 

85 """ 

86 return G.neighbors(n) 

87 

88 

89def number_of_nodes(G): 

90 """Returns the number of nodes in the graph. 

91 

92 This function wraps the :func:`G.number_of_nodes <networkx.Graph.number_of_nodes>` function. 

93 """ 

94 return G.number_of_nodes() 

95 

96 

97def number_of_edges(G): 

98 """Returns the number of edges in the graph. 

99 

100 This function wraps the :func:`G.number_of_edges <networkx.Graph.number_of_edges>` function. 

101 """ 

102 return G.number_of_edges() 

103 

104 

105def density(G): 

106 r"""Returns the density of a graph. 

107 

108 The density for undirected graphs is 

109 

110 .. math:: 

111 

112 d = \frac{2m}{n(n-1)}, 

113 

114 and for directed graphs is 

115 

116 .. math:: 

117 

118 d = \frac{m}{n(n-1)}, 

119 

120 where `n` is the number of nodes and `m` is the number of edges in `G`. 

121 

122 Notes 

123 ----- 

124 The density is 0 for a graph without edges and 1 for a complete graph. 

125 The density of multigraphs can be higher than 1. 

126 

127 Self loops are counted in the total number of edges so graphs with self 

128 loops can have density higher than 1. 

129 """ 

130 n = number_of_nodes(G) 

131 m = number_of_edges(G) 

132 if m == 0 or n <= 1: 

133 return 0 

134 d = m / (n * (n - 1)) 

135 if not G.is_directed(): 

136 d *= 2 

137 return d 

138 

139 

140def degree_histogram(G): 

141 """Returns a list of the frequency of each degree value. 

142 

143 Parameters 

144 ---------- 

145 G : Networkx graph 

146 A graph 

147 

148 Returns 

149 ------- 

150 hist : list 

151 A list of frequencies of degrees. 

152 The degree values are the index in the list. 

153 

154 Notes 

155 ----- 

156 Note: the bins are width one, hence len(list) can be large 

157 (Order(number_of_edges)) 

158 """ 

159 counts = Counter(d for n, d in G.degree()) 

160 return [counts.get(i, 0) for i in range(max(counts) + 1 if counts else 0)] 

161 

162 

163def is_directed(G): 

164 """Return True if graph is directed.""" 

165 return G.is_directed() 

166 

167 

168def frozen(*args, **kwargs): 

169 """Dummy method for raising errors when trying to modify frozen graphs""" 

170 raise nx.NetworkXError("Frozen graph can't be modified") 

171 

172 

173def freeze(G): 

174 """Modify graph to prevent further change by adding or removing 

175 nodes or edges. 

176 

177 Node and edge data can still be modified. 

178 

179 Parameters 

180 ---------- 

181 G : graph 

182 A NetworkX graph 

183 

184 Examples 

185 -------- 

186 >>> G = nx.path_graph(4) 

187 >>> G = nx.freeze(G) 

188 >>> try: 

189 ... G.add_edge(4, 5) 

190 ... except nx.NetworkXError as err: 

191 ... print(str(err)) 

192 Frozen graph can't be modified 

193 

194 Notes 

195 ----- 

196 To "unfreeze" a graph you must make a copy by creating a new graph object: 

197 

198 >>> graph = nx.path_graph(4) 

199 >>> frozen_graph = nx.freeze(graph) 

200 >>> unfrozen_graph = nx.Graph(frozen_graph) 

201 >>> nx.is_frozen(unfrozen_graph) 

202 False 

203 

204 See Also 

205 -------- 

206 is_frozen 

207 """ 

208 G.add_node = frozen 

209 G.add_nodes_from = frozen 

210 G.remove_node = frozen 

211 G.remove_nodes_from = frozen 

212 G.add_edge = frozen 

213 G.add_edges_from = frozen 

214 G.add_weighted_edges_from = frozen 

215 G.remove_edge = frozen 

216 G.remove_edges_from = frozen 

217 G.clear = frozen 

218 G.clear_edges = frozen 

219 G.frozen = True 

220 return G 

221 

222 

223def is_frozen(G): 

224 """Returns True if graph is frozen. 

225 

226 Parameters 

227 ---------- 

228 G : graph 

229 A NetworkX graph 

230 

231 See Also 

232 -------- 

233 freeze 

234 """ 

235 try: 

236 return G.frozen 

237 except AttributeError: 

238 return False 

239 

240 

241def add_star(G_to_add_to, nodes_for_star, **attr): 

242 """Add a star to Graph G_to_add_to. 

243 

244 The first node in `nodes_for_star` is the middle of the star. 

245 It is connected to all other nodes. 

246 

247 Parameters 

248 ---------- 

249 G_to_add_to : graph 

250 A NetworkX graph 

251 nodes_for_star : iterable container 

252 A container of nodes. 

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

254 Attributes to add to every edge in star. 

255 

256 See Also 

257 -------- 

258 add_path, add_cycle 

259 

260 Examples 

261 -------- 

262 >>> G = nx.Graph() 

263 >>> nx.add_star(G, [0, 1, 2, 3]) 

264 >>> nx.add_star(G, [10, 11, 12], weight=2) 

265 """ 

266 nlist = iter(nodes_for_star) 

267 try: 

268 v = next(nlist) 

269 except StopIteration: 

270 return 

271 G_to_add_to.add_node(v) 

272 edges = ((v, n) for n in nlist) 

273 G_to_add_to.add_edges_from(edges, **attr) 

274 

275 

276def add_path(G_to_add_to, nodes_for_path, **attr): 

277 """Add a path to the Graph G_to_add_to. 

278 

279 Parameters 

280 ---------- 

281 G_to_add_to : graph 

282 A NetworkX graph 

283 nodes_for_path : iterable container 

284 A container of nodes. A path will be constructed from 

285 the nodes (in order) and added to the graph. 

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

287 Attributes to add to every edge in path. 

288 

289 See Also 

290 -------- 

291 add_star, add_cycle 

292 

293 Examples 

294 -------- 

295 >>> G = nx.Graph() 

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

297 >>> nx.add_path(G, [10, 11, 12], weight=7) 

298 """ 

299 nlist = iter(nodes_for_path) 

300 try: 

301 first_node = next(nlist) 

302 except StopIteration: 

303 return 

304 G_to_add_to.add_node(first_node) 

305 G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist)), **attr) 

306 

307 

308def add_cycle(G_to_add_to, nodes_for_cycle, **attr): 

309 """Add a cycle to the Graph G_to_add_to. 

310 

311 Parameters 

312 ---------- 

313 G_to_add_to : graph 

314 A NetworkX graph 

315 nodes_for_cycle: iterable container 

316 A container of nodes. A cycle will be constructed from 

317 the nodes (in order) and added to the graph. 

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

319 Attributes to add to every edge in cycle. 

320 

321 See Also 

322 -------- 

323 add_path, add_star 

324 

325 Examples 

326 -------- 

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

328 >>> nx.add_cycle(G, [0, 1, 2, 3]) 

329 >>> nx.add_cycle(G, [10, 11, 12], weight=7) 

330 """ 

331 nlist = iter(nodes_for_cycle) 

332 try: 

333 first_node = next(nlist) 

334 except StopIteration: 

335 return 

336 G_to_add_to.add_node(first_node) 

337 G_to_add_to.add_edges_from( 

338 pairwise(chain((first_node,), nlist), cyclic=True), **attr 

339 ) 

340 

341 

342def subgraph(G, nbunch): 

343 """Returns the subgraph induced on nodes in nbunch. 

344 

345 Parameters 

346 ---------- 

347 G : graph 

348 A NetworkX graph 

349 

350 nbunch : list, iterable 

351 A container of nodes that will be iterated through once (thus 

352 it should be an iterator or be iterable). Each element of the 

353 container should be a valid node type: any hashable type except 

354 None. If nbunch is None, return all edges data in the graph. 

355 Nodes in nbunch that are not in the graph will be (quietly) 

356 ignored. 

357 

358 Notes 

359 ----- 

360 subgraph(G) calls G.subgraph() 

361 """ 

362 return G.subgraph(nbunch) 

363 

364 

365def induced_subgraph(G, nbunch): 

366 """Returns a SubGraph view of `G` showing only nodes in nbunch. 

367 

368 The induced subgraph of a graph on a set of nodes N is the 

369 graph with nodes N and edges from G which have both ends in N. 

370 

371 Parameters 

372 ---------- 

373 G : NetworkX Graph 

374 nbunch : node, container of nodes or None (for all nodes) 

375 

376 Returns 

377 ------- 

378 subgraph : SubGraph View 

379 A read-only view of the subgraph in `G` induced by the nodes. 

380 Changes to the graph `G` will be reflected in the view. 

381 

382 Notes 

383 ----- 

384 To create a mutable subgraph with its own copies of nodes 

385 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` 

386 

387 For an inplace reduction of a graph to a subgraph you can remove nodes: 

388 `G.remove_nodes_from(n in G if n not in set(nbunch))` 

389 

390 If you are going to compute subgraphs of your subgraphs you could 

391 end up with a chain of views that can be very slow once the chain 

392 has about 15 views in it. If they are all induced subgraphs, you 

393 can short-cut the chain by making them all subgraphs of the original 

394 graph. The graph class method `G.subgraph` does this when `G` is 

395 a subgraph. In contrast, this function allows you to choose to build 

396 chains or not, as you wish. The returned subgraph is a view on `G`. 

397 

398 Examples 

399 -------- 

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

401 >>> H = nx.induced_subgraph(G, [0, 1, 3]) 

402 >>> list(H.edges) 

403 [(0, 1)] 

404 >>> list(H.nodes) 

405 [0, 1, 3] 

406 """ 

407 induced_nodes = nx.filters.show_nodes(G.nbunch_iter(nbunch)) 

408 return nx.subgraph_view(G, filter_node=induced_nodes) 

409 

410 

411def edge_subgraph(G, edges): 

412 """Returns a view of the subgraph induced by the specified edges. 

413 

414 The induced subgraph contains each edge in `edges` and each 

415 node incident to any of those edges. 

416 

417 Parameters 

418 ---------- 

419 G : NetworkX Graph 

420 edges : iterable 

421 An iterable of edges. Edges not present in `G` are ignored. 

422 

423 Returns 

424 ------- 

425 subgraph : SubGraph View 

426 A read-only edge-induced subgraph of `G`. 

427 Changes to `G` are reflected in the view. 

428 

429 Notes 

430 ----- 

431 To create a mutable subgraph with its own copies of nodes 

432 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` 

433 

434 If you create a subgraph of a subgraph recursively you can end up 

435 with a chain of subgraphs that becomes very slow with about 15 

436 nested subgraph views. Luckily the edge_subgraph filter nests 

437 nicely so you can use the original graph as G in this function 

438 to avoid chains. We do not rule out chains programmatically so 

439 that odd cases like an `edge_subgraph` of a `restricted_view` 

440 can be created. 

441 

442 Examples 

443 -------- 

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

445 >>> H = G.edge_subgraph([(0, 1), (3, 4)]) 

446 >>> list(H.nodes) 

447 [0, 1, 3, 4] 

448 >>> list(H.edges) 

449 [(0, 1), (3, 4)] 

450 """ 

451 nxf = nx.filters 

452 edges = set(edges) 

453 nodes = set() 

454 for e in edges: 

455 nodes.update(e[:2]) 

456 induced_nodes = nxf.show_nodes(nodes) 

457 if G.is_multigraph(): 

458 if G.is_directed(): 

459 induced_edges = nxf.show_multidiedges(edges) 

460 else: 

461 induced_edges = nxf.show_multiedges(edges) 

462 else: 

463 if G.is_directed(): 

464 induced_edges = nxf.show_diedges(edges) 

465 else: 

466 induced_edges = nxf.show_edges(edges) 

467 return nx.subgraph_view(G, filter_node=induced_nodes, filter_edge=induced_edges) 

468 

469 

470def restricted_view(G, nodes, edges): 

471 """Returns a view of `G` with hidden nodes and edges. 

472 

473 The resulting subgraph filters out node `nodes` and edges `edges`. 

474 Filtered out nodes also filter out any of their edges. 

475 

476 Parameters 

477 ---------- 

478 G : NetworkX Graph 

479 nodes : iterable 

480 An iterable of nodes. Nodes not present in `G` are ignored. 

481 edges : iterable 

482 An iterable of edges. Edges not present in `G` are ignored. 

483 

484 Returns 

485 ------- 

486 subgraph : SubGraph View 

487 A read-only restricted view of `G` filtering out nodes and edges. 

488 Changes to `G` are reflected in the view. 

489 

490 Notes 

491 ----- 

492 To create a mutable subgraph with its own copies of nodes 

493 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` 

494 

495 If you create a subgraph of a subgraph recursively you may end up 

496 with a chain of subgraph views. Such chains can get quite slow 

497 for lengths near 15. To avoid long chains, try to make your subgraph 

498 based on the original graph. We do not rule out chains programmatically 

499 so that odd cases like an `edge_subgraph` of a `restricted_view` 

500 can be created. 

501 

502 Examples 

503 -------- 

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

505 >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)]) 

506 >>> list(H.nodes) 

507 [1, 2, 3, 4] 

508 >>> list(H.edges) 

509 [(2, 3)] 

510 """ 

511 nxf = nx.filters 

512 hide_nodes = nxf.hide_nodes(nodes) 

513 if G.is_multigraph(): 

514 if G.is_directed(): 

515 hide_edges = nxf.hide_multidiedges(edges) 

516 else: 

517 hide_edges = nxf.hide_multiedges(edges) 

518 else: 

519 if G.is_directed(): 

520 hide_edges = nxf.hide_diedges(edges) 

521 else: 

522 hide_edges = nxf.hide_edges(edges) 

523 return nx.subgraph_view(G, filter_node=hide_nodes, filter_edge=hide_edges) 

524 

525 

526def to_directed(graph): 

527 """Returns a directed view of the graph `graph`. 

528 

529 Identical to graph.to_directed(as_view=True) 

530 Note that graph.to_directed defaults to `as_view=False` 

531 while this function always provides a view. 

532 """ 

533 return graph.to_directed(as_view=True) 

534 

535 

536def to_undirected(graph): 

537 """Returns an undirected view of the graph `graph`. 

538 

539 Identical to graph.to_undirected(as_view=True) 

540 Note that graph.to_undirected defaults to `as_view=False` 

541 while this function always provides a view. 

542 """ 

543 return graph.to_undirected(as_view=True) 

544 

545 

546def create_empty_copy(G, with_data=True): 

547 """Returns a copy of the graph G with all of the edges removed. 

548 

549 Parameters 

550 ---------- 

551 G : graph 

552 A NetworkX graph 

553 

554 with_data : bool (default=True) 

555 Propagate Graph and Nodes data to the new graph. 

556 

557 See Also 

558 -------- 

559 empty_graph 

560 

561 """ 

562 H = G.__class__() 

563 H.add_nodes_from(G.nodes(data=with_data)) 

564 if with_data: 

565 H.graph.update(G.graph) 

566 return H 

567 

568 

569@nx._dispatchable(preserve_node_attrs=True, mutates_input=True) 

570def set_node_attributes(G, values, name=None): 

571 """Sets node attributes from a given value or dictionary of values. 

572 

573 .. Warning:: The call order of arguments `values` and `name` 

574 switched between v1.x & v2.x. 

575 

576 Parameters 

577 ---------- 

578 G : NetworkX Graph 

579 

580 values : scalar value, dict-like 

581 What the node attribute should be set to. If `values` is 

582 not a dictionary, then it is treated as a single attribute value 

583 that is then applied to every node in `G`. This means that if 

584 you provide a mutable object, like a list, updates to that object 

585 will be reflected in the node attribute for every node. 

586 The attribute name will be `name`. 

587 

588 If `values` is a dict or a dict of dict, it should be keyed 

589 by node to either an attribute value or a dict of attribute key/value 

590 pairs used to update the node's attributes. 

591 

592 name : string (optional, default=None) 

593 Name of the node attribute to set if values is a scalar. 

594 

595 Examples 

596 -------- 

597 After computing some property of the nodes of a graph, you may want 

598 to assign a node attribute to store the value of that property for 

599 each node:: 

600 

601 >>> G = nx.path_graph(3) 

602 >>> bb = nx.betweenness_centrality(G) 

603 >>> isinstance(bb, dict) 

604 True 

605 >>> nx.set_node_attributes(G, bb, "betweenness") 

606 >>> G.nodes[1]["betweenness"] 

607 1.0 

608 

609 If you provide a list as the second argument, updates to the list 

610 will be reflected in the node attribute for each node:: 

611 

612 >>> G = nx.path_graph(3) 

613 >>> labels = [] 

614 >>> nx.set_node_attributes(G, labels, "labels") 

615 >>> labels.append("foo") 

616 >>> G.nodes[0]["labels"] 

617 ['foo'] 

618 >>> G.nodes[1]["labels"] 

619 ['foo'] 

620 >>> G.nodes[2]["labels"] 

621 ['foo'] 

622 

623 If you provide a dictionary of dictionaries as the second argument, 

624 the outer dictionary is assumed to be keyed by node to an inner 

625 dictionary of node attributes for that node:: 

626 

627 >>> G = nx.path_graph(3) 

628 >>> attrs = {0: {"attr1": 20, "attr2": "nothing"}, 1: {"attr2": 3}} 

629 >>> nx.set_node_attributes(G, attrs) 

630 >>> G.nodes[0]["attr1"] 

631 20 

632 >>> G.nodes[0]["attr2"] 

633 'nothing' 

634 >>> G.nodes[1]["attr2"] 

635 3 

636 >>> G.nodes[2] 

637 {} 

638 

639 Note that if the dictionary contains nodes that are not in `G`, the 

640 values are silently ignored:: 

641 

642 >>> G = nx.Graph() 

643 >>> G.add_node(0) 

644 >>> nx.set_node_attributes(G, {0: "red", 1: "blue"}, name="color") 

645 >>> G.nodes[0]["color"] 

646 'red' 

647 >>> 1 in G.nodes 

648 False 

649 

650 """ 

651 # Set node attributes based on type of `values` 

652 if name is not None: # `values` must not be a dict of dict 

653 try: # `values` is a dict 

654 for n, v in values.items(): 

655 try: 

656 G.nodes[n][name] = values[n] 

657 except KeyError: 

658 pass 

659 except AttributeError: # `values` is a constant 

660 for n in G: 

661 G.nodes[n][name] = values 

662 else: # `values` must be dict of dict 

663 for n, d in values.items(): 

664 try: 

665 G.nodes[n].update(d) 

666 except KeyError: 

667 pass 

668 nx._clear_cache(G) 

669 

670 

671@nx._dispatchable(node_attrs={"name": "default"}) 

672def get_node_attributes(G, name, default=None): 

673 """Get node attributes from graph 

674 

675 Parameters 

676 ---------- 

677 G : NetworkX Graph 

678 

679 name : string 

680 Attribute name 

681 

682 default: object (default=None) 

683 Default value of the node attribute if there is no value set for that 

684 node in graph. If `None` then nodes without this attribute are not 

685 included in the returned dict. 

686 

687 Returns 

688 ------- 

689 Dictionary of attributes keyed by node. 

690 

691 Examples 

692 -------- 

693 >>> G = nx.Graph() 

694 >>> G.add_nodes_from([1, 2, 3], color="red") 

695 >>> color = nx.get_node_attributes(G, "color") 

696 >>> color[1] 

697 'red' 

698 >>> G.add_node(4) 

699 >>> color = nx.get_node_attributes(G, "color", default="yellow") 

700 >>> color[4] 

701 'yellow' 

702 """ 

703 if default is not None: 

704 return {n: d.get(name, default) for n, d in G.nodes.items()} 

705 return {n: d[name] for n, d in G.nodes.items() if name in d} 

706 

707 

708@nx._dispatchable(preserve_node_attrs=True, mutates_input=True) 

709def remove_node_attributes(G, *attr_names, nbunch=None): 

710 """Remove node attributes from all nodes in the graph. 

711 

712 Parameters 

713 ---------- 

714 G : NetworkX Graph 

715 

716 *attr_names : List of Strings 

717 The attribute names to remove from the graph. 

718 

719 nbunch : List of Nodes 

720 Remove the node attributes only from the nodes in this list. 

721 

722 Examples 

723 -------- 

724 >>> G = nx.Graph() 

725 >>> G.add_nodes_from([1, 2, 3], color="blue") 

726 >>> nx.get_node_attributes(G, "color") 

727 {1: 'blue', 2: 'blue', 3: 'blue'} 

728 >>> nx.remove_node_attributes(G, "color") 

729 >>> nx.get_node_attributes(G, "color") 

730 {} 

731 """ 

732 

733 if nbunch is None: 

734 nbunch = G.nodes() 

735 

736 for attr in attr_names: 

737 for n, d in G.nodes(data=True): 

738 if n in nbunch: 

739 try: 

740 del d[attr] 

741 except KeyError: 

742 pass 

743 

744 

745@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True) 

746def set_edge_attributes(G, values, name=None): 

747 """Sets edge attributes from a given value or dictionary of values. 

748 

749 .. Warning:: The call order of arguments `values` and `name` 

750 switched between v1.x & v2.x. 

751 

752 Parameters 

753 ---------- 

754 G : NetworkX Graph 

755 

756 values : scalar value, dict-like 

757 What the edge attribute should be set to. If `values` is 

758 not a dictionary, then it is treated as a single attribute value 

759 that is then applied to every edge in `G`. This means that if 

760 you provide a mutable object, like a list, updates to that object 

761 will be reflected in the edge attribute for each edge. The attribute 

762 name will be `name`. 

763 

764 If `values` is a dict or a dict of dict, it should be keyed 

765 by edge tuple to either an attribute value or a dict of attribute 

766 key/value pairs used to update the edge's attributes. 

767 For multigraphs, the edge tuples must be of the form ``(u, v, key)``, 

768 where `u` and `v` are nodes and `key` is the edge key. 

769 For non-multigraphs, the keys must be tuples of the form ``(u, v)``. 

770 

771 name : string (optional, default=None) 

772 Name of the edge attribute to set if values is a scalar. 

773 

774 Examples 

775 -------- 

776 After computing some property of the edges of a graph, you may want 

777 to assign a edge attribute to store the value of that property for 

778 each edge:: 

779 

780 >>> G = nx.path_graph(3) 

781 >>> bb = nx.edge_betweenness_centrality(G, normalized=False) 

782 >>> nx.set_edge_attributes(G, bb, "betweenness") 

783 >>> G.edges[1, 2]["betweenness"] 

784 2.0 

785 

786 If you provide a list as the second argument, updates to the list 

787 will be reflected in the edge attribute for each edge:: 

788 

789 >>> labels = [] 

790 >>> nx.set_edge_attributes(G, labels, "labels") 

791 >>> labels.append("foo") 

792 >>> G.edges[0, 1]["labels"] 

793 ['foo'] 

794 >>> G.edges[1, 2]["labels"] 

795 ['foo'] 

796 

797 If you provide a dictionary of dictionaries as the second argument, 

798 the entire dictionary will be used to update edge attributes:: 

799 

800 >>> G = nx.path_graph(3) 

801 >>> attrs = {(0, 1): {"attr1": 20, "attr2": "nothing"}, (1, 2): {"attr2": 3}} 

802 >>> nx.set_edge_attributes(G, attrs) 

803 >>> G[0][1]["attr1"] 

804 20 

805 >>> G[0][1]["attr2"] 

806 'nothing' 

807 >>> G[1][2]["attr2"] 

808 3 

809 

810 The attributes of one Graph can be used to set those of another. 

811 

812 >>> H = nx.path_graph(3) 

813 >>> nx.set_edge_attributes(H, G.edges) 

814 

815 Note that if the dict contains edges that are not in `G`, they are 

816 silently ignored:: 

817 

818 >>> G = nx.Graph([(0, 1)]) 

819 >>> nx.set_edge_attributes(G, {(1, 2): {"weight": 2.0}}) 

820 >>> (1, 2) in G.edges() 

821 False 

822 

823 For multigraphs, the `values` dict is expected to be keyed by 3-tuples 

824 including the edge key:: 

825 

826 >>> MG = nx.MultiGraph() 

827 >>> edges = [(0, 1), (0, 1)] 

828 >>> MG.add_edges_from(edges) # Returns list of edge keys 

829 [0, 1] 

830 >>> attributes = {(0, 1, 0): {"cost": 21}, (0, 1, 1): {"cost": 7}} 

831 >>> nx.set_edge_attributes(MG, attributes) 

832 >>> MG[0][1][0]["cost"] 

833 21 

834 >>> MG[0][1][1]["cost"] 

835 7 

836 

837 If MultiGraph attributes are desired for a Graph, you must convert the 3-tuple 

838 multiedge to a 2-tuple edge and the last multiedge's attribute value will 

839 overwrite the previous values. Continuing from the previous case we get:: 

840 

841 >>> H = nx.path_graph([0, 1, 2]) 

842 >>> nx.set_edge_attributes(H, {(u, v): ed for u, v, ed in MG.edges.data()}) 

843 >>> nx.get_edge_attributes(H, "cost") 

844 {(0, 1): 7} 

845 

846 """ 

847 if name is not None: 

848 # `values` does not contain attribute names 

849 try: 

850 # if `values` is a dict using `.items()` => {edge: value} 

851 if G.is_multigraph(): 

852 for (u, v, key), value in values.items(): 

853 try: 

854 G._adj[u][v][key][name] = value 

855 except KeyError: 

856 pass 

857 else: 

858 for (u, v), value in values.items(): 

859 try: 

860 G._adj[u][v][name] = value 

861 except KeyError: 

862 pass 

863 except AttributeError: 

864 # treat `values` as a constant 

865 for u, v, data in G.edges(data=True): 

866 data[name] = values 

867 else: 

868 # `values` consists of doct-of-dict {edge: {attr: value}} shape 

869 if G.is_multigraph(): 

870 for (u, v, key), d in values.items(): 

871 try: 

872 G._adj[u][v][key].update(d) 

873 except KeyError: 

874 pass 

875 else: 

876 for (u, v), d in values.items(): 

877 try: 

878 G._adj[u][v].update(d) 

879 except KeyError: 

880 pass 

881 nx._clear_cache(G) 

882 

883 

884@nx._dispatchable(edge_attrs={"name": "default"}) 

885def get_edge_attributes(G, name, default=None): 

886 """Get edge attributes from graph 

887 

888 Parameters 

889 ---------- 

890 G : NetworkX Graph 

891 

892 name : string 

893 Attribute name 

894 

895 default: object (default=None) 

896 Default value of the edge attribute if there is no value set for that 

897 edge in graph. If `None` then edges without this attribute are not 

898 included in the returned dict. 

899 

900 Returns 

901 ------- 

902 Dictionary of attributes keyed by edge. For (di)graphs, the keys are 

903 2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of 

904 the form: (u, v, key). 

905 

906 Examples 

907 -------- 

908 >>> G = nx.Graph() 

909 >>> nx.add_path(G, [1, 2, 3], color="red") 

910 >>> color = nx.get_edge_attributes(G, "color") 

911 >>> color[(1, 2)] 

912 'red' 

913 >>> G.add_edge(3, 4) 

914 >>> color = nx.get_edge_attributes(G, "color", default="yellow") 

915 >>> color[(3, 4)] 

916 'yellow' 

917 """ 

918 if G.is_multigraph(): 

919 edges = G.edges(keys=True, data=True) 

920 else: 

921 edges = G.edges(data=True) 

922 if default is not None: 

923 return {x[:-1]: x[-1].get(name, default) for x in edges} 

924 return {x[:-1]: x[-1][name] for x in edges if name in x[-1]} 

925 

926 

927@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True) 

928def remove_edge_attributes(G, *attr_names, ebunch=None): 

929 """Remove edge attributes from all edges in the graph. 

930 

931 Parameters 

932 ---------- 

933 G : NetworkX Graph 

934 

935 *attr_names : List of Strings 

936 The attribute names to remove from the graph. 

937 

938 Examples 

939 -------- 

940 >>> G = nx.path_graph(3) 

941 >>> nx.set_edge_attributes(G, {(u, v): u + v for u, v in G.edges()}, name="weight") 

942 >>> nx.get_edge_attributes(G, "weight") 

943 {(0, 1): 1, (1, 2): 3} 

944 >>> remove_edge_attributes(G, "weight") 

945 >>> nx.get_edge_attributes(G, "weight") 

946 {} 

947 """ 

948 if ebunch is None: 

949 ebunch = G.edges(keys=True) if G.is_multigraph() else G.edges() 

950 

951 for attr in attr_names: 

952 edges = ( 

953 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True) 

954 ) 

955 for *e, d in edges: 

956 if tuple(e) in ebunch: 

957 try: 

958 del d[attr] 

959 except KeyError: 

960 pass 

961 

962 

963def all_neighbors(graph, node): 

964 """Returns all of the neighbors of a node in the graph. 

965 

966 If the graph is directed returns predecessors as well as successors. 

967 

968 Parameters 

969 ---------- 

970 graph : NetworkX graph 

971 Graph to find neighbors. 

972 node : node 

973 The node whose neighbors will be returned. 

974 

975 Returns 

976 ------- 

977 neighbors : iterator 

978 Iterator of neighbors 

979 

980 Raises 

981 ------ 

982 NetworkXError 

983 If `node` is not in the graph. 

984 

985 Examples 

986 -------- 

987 For undirected graphs, this function is equivalent to ``G.neighbors(node)``. 

988 

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

990 >>> list(nx.all_neighbors(G, 1)) 

991 [0, 2] 

992 

993 For directed graphs, this function returns both predecessors and successors, 

994 which may include duplicates if a node is both a predecessor and successor 

995 (e.g., in bidirectional edges or self-loops). 

996 

997 >>> DG = nx.DiGraph([(0, 1), (1, 2), (2, 1)]) 

998 >>> list(nx.all_neighbors(DG, 1)) 

999 [0, 2, 2] 

1000 

1001 Notes 

1002 ----- 

1003 This function iterates over all neighbors (both predecessors and successors). 

1004 

1005 See Also 

1006 -------- 

1007 Graph.neighbors : Returns successors for both Graph and DiGraph 

1008 DiGraph.predecessors : Returns predecessors for directed graphs only 

1009 DiGraph.successors : Returns successors for directed graphs only 

1010 """ 

1011 if graph.is_directed(): 

1012 values = chain(graph.predecessors(node), graph.successors(node)) 

1013 else: 

1014 values = graph.neighbors(node) 

1015 return values 

1016 

1017 

1018def non_neighbors(graph, node): 

1019 """Returns the non-neighbors of the node in the graph. 

1020 

1021 Parameters 

1022 ---------- 

1023 graph : NetworkX graph 

1024 Graph to find neighbors. 

1025 

1026 node : node 

1027 The node whose neighbors will be returned. 

1028 

1029 Returns 

1030 ------- 

1031 non_neighbors : set 

1032 Set of nodes in the graph that are not neighbors of the node. 

1033 """ 

1034 return graph._adj.keys() - graph._adj[node].keys() - {node} 

1035 

1036 

1037def non_edges(graph): 

1038 """Returns the nonexistent edges in the graph. 

1039 

1040 Parameters 

1041 ---------- 

1042 graph : NetworkX graph. 

1043 Graph to find nonexistent edges. 

1044 

1045 Returns 

1046 ------- 

1047 non_edges : iterator 

1048 Iterator of edges that are not in the graph. 

1049 """ 

1050 if graph.is_directed(): 

1051 for u in graph: 

1052 for v in non_neighbors(graph, u): 

1053 yield (u, v) 

1054 else: 

1055 nodes = set(graph) 

1056 while nodes: 

1057 u = nodes.pop() 

1058 for v in nodes - set(graph[u]): 

1059 yield (u, v) 

1060 

1061 

1062@not_implemented_for("directed") 

1063def common_neighbors(G, u, v): 

1064 """Returns the common neighbors of two nodes in a graph. 

1065 

1066 Parameters 

1067 ---------- 

1068 G : graph 

1069 A NetworkX undirected graph. 

1070 

1071 u, v : nodes 

1072 Nodes in the graph. 

1073 

1074 Returns 

1075 ------- 

1076 cnbors : set 

1077 Set of common neighbors of u and v in the graph. 

1078 

1079 Raises 

1080 ------ 

1081 NetworkXError 

1082 If u or v is not a node in the graph. 

1083 

1084 Examples 

1085 -------- 

1086 >>> G = nx.complete_graph(5) 

1087 >>> sorted(nx.common_neighbors(G, 0, 1)) 

1088 [2, 3, 4] 

1089 """ 

1090 if u not in G: 

1091 raise nx.NetworkXError("u is not in the graph.") 

1092 if v not in G: 

1093 raise nx.NetworkXError("v is not in the graph.") 

1094 

1095 return G._adj[u].keys() & G._adj[v].keys() - {u, v} 

1096 

1097 

1098@nx._dispatchable(preserve_edge_attrs=True) 

1099def is_weighted(G, edge=None, weight="weight"):