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

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

2""" 

3 

4from collections import Counter 

5from itertools import chain 

6 

7import networkx as nx 

8from networkx.utils import not_implemented_for, pairwise 

9 

10__all__ = [ 

11 "nodes", 

12 "edges", 

13 "degree", 

14 "degree_histogram", 

15 "neighbors", 

16 "number_of_nodes", 

17 "number_of_edges", 

18 "density", 

19 "is_directed", 

20 "freeze", 

21 "is_frozen", 

22 "subgraph", 

23 "induced_subgraph", 

24 "edge_subgraph", 

25 "restricted_view", 

26 "to_directed", 

27 "to_undirected", 

28 "add_star", 

29 "add_path", 

30 "add_cycle", 

31 "create_empty_copy", 

32 "set_node_attributes", 

33 "get_node_attributes", 

34 "set_edge_attributes", 

35 "get_edge_attributes", 

36 "all_neighbors", 

37 "non_neighbors", 

38 "non_edges", 

39 "common_neighbors", 

40 "is_weighted", 

41 "is_negatively_weighted", 

42 "is_empty", 

43 "selfloop_edges", 

44 "nodes_with_selfloops", 

45 "number_of_selfloops", 

46 "path_weight", 

47 "is_path", 

48] 

49 

50 

51def nodes(G): 

52 """Returns an iterator over the graph nodes.""" 

53 return G.nodes() 

54 

55 

56def edges(G, nbunch=None): 

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

58 

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

60 

61 For digraphs, edges=out_edges 

62 """ 

63 return G.edges(nbunch) 

64 

65 

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

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

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

69 """ 

70 return G.degree(nbunch, weight) 

71 

72 

73def neighbors(G, n): 

74 """Returns a list of nodes connected to node n.""" 

75 return G.neighbors(n) 

76 

77 

78def number_of_nodes(G): 

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

80 return G.number_of_nodes() 

81 

82 

83def number_of_edges(G): 

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

85 return G.number_of_edges() 

86 

87 

88def density(G): 

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

90 

91 The density for undirected graphs is 

92 

93 .. math:: 

94 

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

96 

97 and for directed graphs is 

98 

99 .. math:: 

100 

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

102 

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

104 

105 Notes 

106 ----- 

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

108 The density of multigraphs can be higher than 1. 

109 

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

111 loops can have density higher than 1. 

112 """ 

113 n = number_of_nodes(G) 

114 m = number_of_edges(G) 

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

116 return 0 

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

118 if not G.is_directed(): 

119 d *= 2 

120 return d 

121 

122 

123def degree_histogram(G): 

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

125 

126 Parameters 

127 ---------- 

128 G : Networkx graph 

129 A graph 

130 

131 Returns 

132 ------- 

133 hist : list 

134 A list of frequencies of degrees. 

135 The degree values are the index in the list. 

136 

137 Notes 

138 ----- 

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

140 (Order(number_of_edges)) 

141 """ 

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

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

144 

145 

146def is_directed(G): 

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

148 return G.is_directed() 

149 

150 

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

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

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

154 

155 

156def freeze(G): 

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

158 nodes or edges. 

159 

160 Node and edge data can still be modified. 

161 

162 Parameters 

163 ---------- 

164 G : graph 

165 A NetworkX graph 

166 

167 Examples 

168 -------- 

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

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

171 >>> try: 

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

173 ... except nx.NetworkXError as err: 

174 ... print(str(err)) 

175 Frozen graph can't be modified 

176 

177 Notes 

178 ----- 

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

180 

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

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

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

184 >>> nx.is_frozen(unfrozen_graph) 

185 False 

186 

187 See Also 

188 -------- 

189 is_frozen 

190 """ 

191 G.add_node = frozen 

192 G.add_nodes_from = frozen 

193 G.remove_node = frozen 

194 G.remove_nodes_from = frozen 

195 G.add_edge = frozen 

196 G.add_edges_from = frozen 

197 G.add_weighted_edges_from = frozen 

198 G.remove_edge = frozen 

199 G.remove_edges_from = frozen 

200 G.clear = frozen 

201 G.clear_edges = frozen 

202 G.frozen = True 

203 return G 

204 

205 

206def is_frozen(G): 

207 """Returns True if graph is frozen. 

208 

209 Parameters 

210 ---------- 

211 G : graph 

212 A NetworkX graph 

213 

214 See Also 

215 -------- 

216 freeze 

217 """ 

218 try: 

219 return G.frozen 

220 except AttributeError: 

221 return False 

222 

223 

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

225 """Add a star to Graph G_to_add_to. 

226 

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

228 It is connected to all other nodes. 

229 

230 Parameters 

231 ---------- 

232 G_to_add_to : graph 

233 A NetworkX graph 

234 nodes_for_star : iterable container 

235 A container of nodes. 

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

237 Attributes to add to every edge in star. 

238 

239 See Also 

240 -------- 

241 add_path, add_cycle 

242 

243 Examples 

244 -------- 

245 >>> G = nx.Graph() 

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

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

248 """ 

249 nlist = iter(nodes_for_star) 

250 try: 

251 v = next(nlist) 

252 except StopIteration: 

253 return 

254 G_to_add_to.add_node(v) 

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

256 G_to_add_to.add_edges_from(edges, **attr) 

257 

258 

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

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

261 

262 Parameters 

263 ---------- 

264 G_to_add_to : graph 

265 A NetworkX graph 

266 nodes_for_path : iterable container 

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

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

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

270 Attributes to add to every edge in path. 

271 

272 See Also 

273 -------- 

274 add_star, add_cycle 

275 

276 Examples 

277 -------- 

278 >>> G = nx.Graph() 

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

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

281 """ 

282 nlist = iter(nodes_for_path) 

283 try: 

284 first_node = next(nlist) 

285 except StopIteration: 

286 return 

287 G_to_add_to.add_node(first_node) 

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

289 

290 

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

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

293 

294 Parameters 

295 ---------- 

296 G_to_add_to : graph 

297 A NetworkX graph 

298 nodes_for_cycle: iterable container 

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

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

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

302 Attributes to add to every edge in cycle. 

303 

304 See Also 

305 -------- 

306 add_path, add_star 

307 

308 Examples 

309 -------- 

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

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

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

313 """ 

314 nlist = iter(nodes_for_cycle) 

315 try: 

316 first_node = next(nlist) 

317 except StopIteration: 

318 return 

319 G_to_add_to.add_node(first_node) 

320 G_to_add_to.add_edges_from( 

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

322 ) 

323 

324 

325def subgraph(G, nbunch): 

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

327 

328 Parameters 

329 ---------- 

330 G : graph 

331 A NetworkX graph 

332 

333 nbunch : list, iterable 

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

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

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

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

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

339 ignored. 

340 

341 Notes 

342 ----- 

343 subgraph(G) calls G.subgraph() 

344 """ 

345 return G.subgraph(nbunch) 

346 

347 

348def induced_subgraph(G, nbunch): 

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

350 

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

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

353 

354 Parameters 

355 ---------- 

356 G : NetworkX Graph 

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

358 

359 Returns 

360 ------- 

361 subgraph : SubGraph View 

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

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

364 

365 Notes 

366 ----- 

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

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

369 

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

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

372 

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

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

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

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

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

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

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

380 

381 Examples 

382 -------- 

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

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

385 >>> list(H.edges) 

386 [(0, 1)] 

387 >>> list(H.nodes) 

388 [0, 1, 3] 

389 """ 

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

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

392 

393 

394def edge_subgraph(G, edges): 

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

396 

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

398 node incident to any of those edges. 

399 

400 Parameters 

401 ---------- 

402 G : NetworkX Graph 

403 edges : iterable 

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

405 

406 Returns 

407 ------- 

408 subgraph : SubGraph View 

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

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

411 

412 Notes 

413 ----- 

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

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

416 

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

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

419 nested subgraph views. Luckily the edge_subgraph filter nests 

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

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

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

423 can be created. 

424 

425 Examples 

426 -------- 

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

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

429 >>> list(H.nodes) 

430 [0, 1, 3, 4] 

431 >>> list(H.edges) 

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

433 """ 

434 nxf = nx.filters 

435 edges = set(edges) 

436 nodes = set() 

437 for e in edges: 

438 nodes.update(e[:2]) 

439 induced_nodes = nxf.show_nodes(nodes) 

440 if G.is_multigraph(): 

441 if G.is_directed(): 

442 induced_edges = nxf.show_multidiedges(edges) 

443 else: 

444 induced_edges = nxf.show_multiedges(edges) 

445 else: 

446 if G.is_directed(): 

447 induced_edges = nxf.show_diedges(edges) 

448 else: 

449 induced_edges = nxf.show_edges(edges) 

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

451 

452 

453def restricted_view(G, nodes, edges): 

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

455 

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

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

458 

459 Parameters 

460 ---------- 

461 G : NetworkX Graph 

462 nodes : iterable 

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

464 edges : iterable 

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

466 

467 Returns 

468 ------- 

469 subgraph : SubGraph View 

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

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

472 

473 Notes 

474 ----- 

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

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

477 

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

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

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

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

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

483 can be created. 

484 

485 Examples 

486 -------- 

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

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

489 >>> list(H.nodes) 

490 [1, 2, 3, 4] 

491 >>> list(H.edges) 

492 [(2, 3)] 

493 """ 

494 nxf = nx.filters 

495 hide_nodes = nxf.hide_nodes(nodes) 

496 if G.is_multigraph(): 

497 if G.is_directed(): 

498 hide_edges = nxf.hide_multidiedges(edges) 

499 else: 

500 hide_edges = nxf.hide_multiedges(edges) 

501 else: 

502 if G.is_directed(): 

503 hide_edges = nxf.hide_diedges(edges) 

504 else: 

505 hide_edges = nxf.hide_edges(edges) 

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

507 

508 

509def to_directed(graph): 

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

511 

512 Identical to graph.to_directed(as_view=True) 

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

514 while this function always provides a view. 

515 """ 

516 return graph.to_directed(as_view=True) 

517 

518 

519def to_undirected(graph): 

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

521 

522 Identical to graph.to_undirected(as_view=True) 

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

524 while this function always provides a view. 

525 """ 

526 return graph.to_undirected(as_view=True) 

527 

528 

529def create_empty_copy(G, with_data=True): 

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

531 

532 Parameters 

533 ---------- 

534 G : graph 

535 A NetworkX graph 

536 

537 with_data : bool (default=True) 

538 Propagate Graph and Nodes data to the new graph. 

539 

540 See Also 

541 -------- 

542 empty_graph 

543 

544 """ 

545 H = G.__class__() 

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

547 if with_data: 

548 H.graph.update(G.graph) 

549 return H 

550 

551 

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

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

554 

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

556 switched between v1.x & v2.x. 

557 

558 Parameters 

559 ---------- 

560 G : NetworkX Graph 

561 

562 values : scalar value, dict-like 

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

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

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

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

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

568 The attribute name will be `name`. 

569 

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

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

572 pairs used to update the node's attributes. 

573 

574 name : string (optional, default=None) 

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

576 

577 Examples 

578 -------- 

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

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

581 each node:: 

582 

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

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

585 >>> isinstance(bb, dict) 

586 True 

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

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

589 1.0 

590 

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

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

593 

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

595 >>> labels = [] 

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

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

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

599 ['foo'] 

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

601 ['foo'] 

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

603 ['foo'] 

604 

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

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

607 dictionary of node attributes for that node:: 

608 

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

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

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

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

613 20 

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

615 'nothing' 

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

617 3 

618 >>> G.nodes[2] 

619 {} 

620 

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

622 values are silently ignored:: 

623 

624 >>> G = nx.Graph() 

625 >>> G.add_node(0) 

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

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

628 'red' 

629 >>> 1 in G.nodes 

630 False 

631 

632 """ 

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

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

635 try: # `values` is a dict 

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

637 try: 

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

639 except KeyError: 

640 pass 

641 except AttributeError: # `values` is a constant 

642 for n in G: 

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

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

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

646 try: 

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

648 except KeyError: 

649 pass 

650 

651 

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

653 """Get node attributes from graph 

654 

655 Parameters 

656 ---------- 

657 G : NetworkX Graph 

658 

659 name : string 

660 Attribute name 

661 

662 default: object (default=None) 

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

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

665 included in the returned dict. 

666 

667 Returns 

668 ------- 

669 Dictionary of attributes keyed by node. 

670 

671 Examples 

672 -------- 

673 >>> G = nx.Graph() 

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

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

676 >>> color[1] 

677 'red' 

678 >>> G.add_node(4) 

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

680 >>> color[4] 

681 'yellow' 

682 """ 

683 if default is not None: 

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

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

686 

687 

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

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

690 

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

692 switched between v1.x & v2.x. 

693 

694 Parameters 

695 ---------- 

696 G : NetworkX Graph 

697 

698 values : scalar value, dict-like 

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

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

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

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

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

704 name will be `name`. 

705 

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

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

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

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

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

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

712 

713 name : string (optional, default=None) 

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

715 

716 Examples 

717 -------- 

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

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

720 each edge:: 

721 

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

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

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

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

726 2.0 

727 

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

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

730 

731 >>> labels = [] 

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

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

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

735 ['foo'] 

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

737 ['foo'] 

738 

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

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

741 

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

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

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

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

746 20 

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

748 'nothing' 

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

750 3 

751 

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

753 

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

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

756 

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

758 silently ignored:: 

759 

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

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

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

763 False 

764 

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

766 including the edge key:: 

767 

768 >>> MG = nx.MultiGraph() 

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

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

771 [0, 1] 

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

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

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

775 21 

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

777 7 

778 

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

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

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

782 

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

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

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

786 {(0, 1): 7} 

787 

788 """ 

789 if name is not None: 

790 # `values` does not contain attribute names 

791 try: 

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

793 if G.is_multigraph(): 

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

795 try: 

796 G[u][v][key][name] = value 

797 except KeyError: 

798 pass 

799 else: 

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

801 try: 

802 G[u][v][name] = value 

803 except KeyError: 

804 pass 

805 except AttributeError: 

806 # treat `values` as a constant 

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

808 data[name] = values 

809 else: 

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

811 if G.is_multigraph(): 

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

813 try: 

814 G[u][v][key].update(d) 

815 except KeyError: 

816 pass 

817 else: 

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

819 try: 

820 G[u][v].update(d) 

821 except KeyError: 

822 pass 

823 

824 

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

826 """Get edge attributes from graph 

827 

828 Parameters 

829 ---------- 

830 G : NetworkX Graph 

831 

832 name : string 

833 Attribute name 

834 

835 default: object (default=None) 

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

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

838 included in the returned dict. 

839 

840 Returns 

841 ------- 

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

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

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

845 

846 Examples 

847 -------- 

848 >>> G = nx.Graph() 

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

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

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

852 'red' 

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

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

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

856 'yellow' 

857 """ 

858 if G.is_multigraph(): 

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

860 else: 

861 edges = G.edges(data=True) 

862 if default is not None: 

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

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

865 

866 

867def all_neighbors(graph, node): 

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

869 

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

871 

872 Parameters 

873 ---------- 

874 graph : NetworkX graph 

875 Graph to find neighbors. 

876 

877 node : node 

878 The node whose neighbors will be returned. 

879 

880 Returns 

881 ------- 

882 neighbors : iterator 

883 Iterator of neighbors 

884 """ 

885 if graph.is_directed(): 

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

887 else: 

888 values = graph.neighbors(node) 

889 return values 

890 

891 

892def non_neighbors(graph, node): 

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

894 

895 Parameters 

896 ---------- 

897 graph : NetworkX graph 

898 Graph to find neighbors. 

899 

900 node : node 

901 The node whose neighbors will be returned. 

902 

903 Returns 

904 ------- 

905 non_neighbors : iterator 

906 Iterator of nodes in the graph that are not neighbors of the node. 

907 """ 

908 nbors = set(neighbors(graph, node)) | {node} 

909 return (nnode for nnode in graph if nnode not in nbors) 

910 

911 

912def non_edges(graph): 

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

914 

915 Parameters 

916 ---------- 

917 graph : NetworkX graph. 

918 Graph to find nonexistent edges. 

919 

920 Returns 

921 ------- 

922 non_edges : iterator 

923 Iterator of edges that are not in the graph. 

924 """ 

925 if graph.is_directed(): 

926 for u in graph: 

927 for v in non_neighbors(graph, u): 

928 yield (u, v) 

929 else: 

930 nodes = set(graph) 

931 while nodes: 

932 u = nodes.pop() 

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

934 yield (u, v) 

935 

936 

937@not_implemented_for("directed") 

938def common_neighbors(G, u, v): 

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

940 

941 Parameters 

942 ---------- 

943 G : graph 

944 A NetworkX undirected graph. 

945 

946 u, v : nodes 

947 Nodes in the graph. 

948 

949 Returns 

950 ------- 

951 cnbors : iterator 

952 Iterator of common neighbors of u and v in the graph. 

953 

954 Raises 

955 ------ 

956 NetworkXError 

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

958 

959 Examples 

960 -------- 

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

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

963 [2, 3, 4] 

964 """ 

965 if u not in G: 

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

967 if v not in G: 

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

969 

970 # Return a generator explicitly instead of yielding so that the above 

971 # checks are executed eagerly. 

972 return (w for w in G[u] if w in G[v] and w not in (u, v)) 

973 

974 

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

976 """Returns True if `G` has weighted edges. 

977 

978 Parameters 

979 ---------- 

980 G : graph 

981 A NetworkX graph. 

982 

983 edge : tuple, optional 

984 A 2-tuple specifying the only edge in `G` that will be tested. If 

985 None, then every edge in `G` is tested. 

986 

987 weight: string, optional 

988 The attribute name used to query for edge weights. 

989 

990 Returns 

991 ------- 

992 bool 

993 A boolean signifying if `G`, or the specified edge, is weighted. 

994 

995 Raises 

996 ------ 

997 NetworkXError 

998 If the specified edge does not exist. 

999 

1000 Examples 

1001 -------- 

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

1003 >>> nx.is_weighted(G) 

1004 False 

1005 >>> nx.is_weighted(G, (2, 3)) 

1006 False 

1007 

1008 >>> G = nx.DiGraph() 

1009 >>> G.add_edge(1, 2, weight=1) 

1010 >>> nx.is_weighted(G) 

1011 True 

1012 

1013 """ 

1014 if edge is not None: 

1015 data = G.get_edge_data(*edge) 

1016 if data is None: 

1017 msg = f"Edge {edge!r} does not exist." 

1018 raise nx.NetworkXError(msg) 

1019 return weight in data 

1020 

1021 if is_empty(G): 

1022 # Special handling required since: all([]) == True 

1023 return False 

1024 

1025 return all(weight in data for u, v, data in G.edges(data=True)) 

1026 

1027 

1028def is_negatively_weighted(G, edge=None, weight="weight"): 

1029 """Returns True if `G` has negatively weighted edges. 

1030 

1031 Parameters 

1032 ---------- 

1033 G : graph 

1034 A NetworkX graph. 

1035 

1036 edge : tuple, optional 

1037 A 2-tuple specifying the only edge in `G` that will be tested. If 

1038 None, then every edge in `G` is tested. 

1039 

1040 weight: string, optional 

1041 The attribute name used to query for edge weights. 

1042 

1043 Returns 

1044 ------- 

1045 bool 

1046 A boolean signifying if `G`, or the specified edge, is negatively 

1047 weighted. 

1048 

1049 Raises 

1050 ------ 

1051 NetworkXError 

1052 If the specified edge does not exist. 

1053 

1054 Examples 

1055 -------- 

1056 >>> G = nx.Graph() 

1057 >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)]) 

1058 >>> G.add_edge(1, 2, weight=4) 

1059 >>> nx.is_negatively_weighted(G, (1, 2)) 

1060 False 

1061 >>> G[2][4]["weight"] = -2 

1062 >>> nx.is_negatively_weighted(G) 

1063 True 

1064 >>> G = nx.DiGraph() 

1065 >>> edges = [("0", "3", 3), ("0", "1", -5), ("1", "0", -2)] 

1066 >>> G.add_weighted_edges_from(edges) 

1067 >>> nx.is_negatively_weighted(G) 

1068 True 

1069 

1070 """ 

1071 if edge is not None: 

1072 data = G.get_edge_data(*edge) 

1073 if data is None: 

1074 msg = f"Edge {edge!r} does not exist." 

1075 raise nx.NetworkXError(msg) 

1076 return weight in data and data[weight] < 0 

1077 

1078 return any(weight in data and data[weight] < 0 for u, v, data in G.edges(data=True)) 

1079 

1080 

1081def is_empty(G): 

1082 """Returns True if `G` has no edges. 

1083 

1084 Parameters 

1085 ---------- 

1086 G : graph 

1087 A NetworkX graph. 

1088 

1089 Returns 

1090 ------- 

1091 bool 

1092 True if `G` has no edges, and False otherwise. 

1093 

1094 Notes 

1095 ----- 

1096 An empty graph can have nodes but not edges. The empty graph with zero 

1097 nodes is known as the null graph. This is an $O(n)$ operation where n 

1098 is the number of nodes in the graph. 

1099 

1100 """ 

1101 return not any(G.adj.values()) 

1102 

1103 

1104def nodes_with_selfloops(G): 

1105 """Returns an iterator over nodes with self loops. 

1106 

1107 A node with a self loop has an edge with both ends adjacent 

1108 to that node. 

1109 

1110 Returns 

1111 ------- 

1112 nodelist : iterator 

1113 A iterator over nodes with self loops.