Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/classes/function.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functional interface to graph methods and assorted utilities. | |
2 """ | |
3 | |
4 from collections import Counter | |
5 from itertools import chain | |
6 | |
7 import networkx as nx | |
8 from networkx.utils import pairwise, not_implemented_for | |
9 from networkx.classes.graphviews import subgraph_view, reverse_view | |
10 | |
11 | |
12 __all__ = [ | |
13 "nodes", | |
14 "edges", | |
15 "degree", | |
16 "degree_histogram", | |
17 "neighbors", | |
18 "number_of_nodes", | |
19 "number_of_edges", | |
20 "density", | |
21 "is_directed", | |
22 "info", | |
23 "freeze", | |
24 "is_frozen", | |
25 "subgraph", | |
26 "subgraph_view", | |
27 "induced_subgraph", | |
28 "reverse_view", | |
29 "edge_subgraph", | |
30 "restricted_view", | |
31 "to_directed", | |
32 "to_undirected", | |
33 "add_star", | |
34 "add_path", | |
35 "add_cycle", | |
36 "create_empty_copy", | |
37 "set_node_attributes", | |
38 "get_node_attributes", | |
39 "set_edge_attributes", | |
40 "get_edge_attributes", | |
41 "all_neighbors", | |
42 "non_neighbors", | |
43 "non_edges", | |
44 "common_neighbors", | |
45 "is_weighted", | |
46 "is_negatively_weighted", | |
47 "is_empty", | |
48 "selfloop_edges", | |
49 "nodes_with_selfloops", | |
50 "number_of_selfloops", | |
51 "path_weight", | |
52 "is_path", | |
53 ] | |
54 | |
55 | |
56 def nodes(G): | |
57 """Returns an iterator over the graph nodes.""" | |
58 return G.nodes() | |
59 | |
60 | |
61 def edges(G, nbunch=None): | |
62 """Returns an edge view of edges incident to nodes in nbunch. | |
63 | |
64 Return all edges if nbunch is unspecified or nbunch=None. | |
65 | |
66 For digraphs, edges=out_edges | |
67 """ | |
68 return G.edges(nbunch) | |
69 | |
70 | |
71 def degree(G, nbunch=None, weight=None): | |
72 """Returns a degree view of single node or of nbunch of nodes. | |
73 If nbunch is omitted, then return degrees of *all* nodes. | |
74 """ | |
75 return G.degree(nbunch, weight) | |
76 | |
77 | |
78 def neighbors(G, n): | |
79 """Returns a list of nodes connected to node n. """ | |
80 return G.neighbors(n) | |
81 | |
82 | |
83 def number_of_nodes(G): | |
84 """Returns the number of nodes in the graph.""" | |
85 return G.number_of_nodes() | |
86 | |
87 | |
88 def number_of_edges(G): | |
89 """Returns the number of edges in the graph. """ | |
90 return G.number_of_edges() | |
91 | |
92 | |
93 def density(G): | |
94 r"""Returns the density of a graph. | |
95 | |
96 The density for undirected graphs is | |
97 | |
98 .. math:: | |
99 | |
100 d = \frac{2m}{n(n-1)}, | |
101 | |
102 and for directed graphs is | |
103 | |
104 .. math:: | |
105 | |
106 d = \frac{m}{n(n-1)}, | |
107 | |
108 where `n` is the number of nodes and `m` is the number of edges in `G`. | |
109 | |
110 Notes | |
111 ----- | |
112 The density is 0 for a graph without edges and 1 for a complete graph. | |
113 The density of multigraphs can be higher than 1. | |
114 | |
115 Self loops are counted in the total number of edges so graphs with self | |
116 loops can have density higher than 1. | |
117 """ | |
118 n = number_of_nodes(G) | |
119 m = number_of_edges(G) | |
120 if m == 0 or n <= 1: | |
121 return 0 | |
122 d = m / (n * (n - 1)) | |
123 if not G.is_directed(): | |
124 d *= 2 | |
125 return d | |
126 | |
127 | |
128 def degree_histogram(G): | |
129 """Returns a list of the frequency of each degree value. | |
130 | |
131 Parameters | |
132 ---------- | |
133 G : Networkx graph | |
134 A graph | |
135 | |
136 Returns | |
137 ------- | |
138 hist : list | |
139 A list of frequencies of degrees. | |
140 The degree values are the index in the list. | |
141 | |
142 Notes | |
143 ----- | |
144 Note: the bins are width one, hence len(list) can be large | |
145 (Order(number_of_edges)) | |
146 """ | |
147 counts = Counter(d for n, d in G.degree()) | |
148 return [counts.get(i, 0) for i in range(max(counts) + 1)] | |
149 | |
150 | |
151 def is_directed(G): | |
152 """ Return True if graph is directed.""" | |
153 return G.is_directed() | |
154 | |
155 | |
156 def frozen(*args, **kwargs): | |
157 """Dummy method for raising errors when trying to modify frozen graphs""" | |
158 raise nx.NetworkXError("Frozen graph can't be modified") | |
159 | |
160 | |
161 def freeze(G): | |
162 """Modify graph to prevent further change by adding or removing | |
163 nodes or edges. | |
164 | |
165 Node and edge data can still be modified. | |
166 | |
167 Parameters | |
168 ---------- | |
169 G : graph | |
170 A NetworkX graph | |
171 | |
172 Examples | |
173 -------- | |
174 >>> G = nx.path_graph(4) | |
175 >>> G = nx.freeze(G) | |
176 >>> try: | |
177 ... G.add_edge(4, 5) | |
178 ... except nx.NetworkXError as e: | |
179 ... print(str(e)) | |
180 Frozen graph can't be modified | |
181 | |
182 Notes | |
183 ----- | |
184 To "unfreeze" a graph you must make a copy by creating a new graph object: | |
185 | |
186 >>> graph = nx.path_graph(4) | |
187 >>> frozen_graph = nx.freeze(graph) | |
188 >>> unfrozen_graph = nx.Graph(frozen_graph) | |
189 >>> nx.is_frozen(unfrozen_graph) | |
190 False | |
191 | |
192 See Also | |
193 -------- | |
194 is_frozen | |
195 """ | |
196 G.add_node = frozen | |
197 G.add_nodes_from = frozen | |
198 G.remove_node = frozen | |
199 G.remove_nodes_from = frozen | |
200 G.add_edge = frozen | |
201 G.add_edges_from = frozen | |
202 G.add_weighted_edges_from = frozen | |
203 G.remove_edge = frozen | |
204 G.remove_edges_from = frozen | |
205 G.clear = frozen | |
206 G.frozen = True | |
207 return G | |
208 | |
209 | |
210 def is_frozen(G): | |
211 """Returns True if graph is frozen. | |
212 | |
213 Parameters | |
214 ---------- | |
215 G : graph | |
216 A NetworkX graph | |
217 | |
218 See Also | |
219 -------- | |
220 freeze | |
221 """ | |
222 try: | |
223 return G.frozen | |
224 except AttributeError: | |
225 return False | |
226 | |
227 | |
228 def add_star(G_to_add_to, nodes_for_star, **attr): | |
229 """Add a star to Graph G_to_add_to. | |
230 | |
231 The first node in `nodes_for_star` is the middle of the star. | |
232 It is connected to all other nodes. | |
233 | |
234 Parameters | |
235 ---------- | |
236 G_to_add_to : graph | |
237 A NetworkX graph | |
238 nodes_for_star : iterable container | |
239 A container of nodes. | |
240 attr : keyword arguments, optional (default= no attributes) | |
241 Attributes to add to every edge in star. | |
242 | |
243 See Also | |
244 -------- | |
245 add_path, add_cycle | |
246 | |
247 Examples | |
248 -------- | |
249 >>> G = nx.Graph() | |
250 >>> nx.add_star(G, [0, 1, 2, 3]) | |
251 >>> nx.add_star(G, [10, 11, 12], weight=2) | |
252 """ | |
253 nlist = iter(nodes_for_star) | |
254 try: | |
255 v = next(nlist) | |
256 except StopIteration: | |
257 return | |
258 G_to_add_to.add_node(v) | |
259 edges = ((v, n) for n in nlist) | |
260 G_to_add_to.add_edges_from(edges, **attr) | |
261 | |
262 | |
263 def add_path(G_to_add_to, nodes_for_path, **attr): | |
264 """Add a path to the Graph G_to_add_to. | |
265 | |
266 Parameters | |
267 ---------- | |
268 G_to_add_to : graph | |
269 A NetworkX graph | |
270 nodes_for_path : iterable container | |
271 A container of nodes. A path will be constructed from | |
272 the nodes (in order) and added to the graph. | |
273 attr : keyword arguments, optional (default= no attributes) | |
274 Attributes to add to every edge in path. | |
275 | |
276 See Also | |
277 -------- | |
278 add_star, add_cycle | |
279 | |
280 Examples | |
281 -------- | |
282 >>> G = nx.Graph() | |
283 >>> nx.add_path(G, [0, 1, 2, 3]) | |
284 >>> nx.add_path(G, [10, 11, 12], weight=7) | |
285 """ | |
286 nlist = iter(nodes_for_path) | |
287 try: | |
288 first_node = next(nlist) | |
289 except StopIteration: | |
290 return | |
291 G_to_add_to.add_node(first_node) | |
292 G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist)), **attr) | |
293 | |
294 | |
295 def add_cycle(G_to_add_to, nodes_for_cycle, **attr): | |
296 """Add a cycle to the Graph G_to_add_to. | |
297 | |
298 Parameters | |
299 ---------- | |
300 G_to_add_to : graph | |
301 A NetworkX graph | |
302 nodes_for_cycle: iterable container | |
303 A container of nodes. A cycle will be constructed from | |
304 the nodes (in order) and added to the graph. | |
305 attr : keyword arguments, optional (default= no attributes) | |
306 Attributes to add to every edge in cycle. | |
307 | |
308 See Also | |
309 -------- | |
310 add_path, add_star | |
311 | |
312 Examples | |
313 -------- | |
314 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc | |
315 >>> nx.add_cycle(G, [0, 1, 2, 3]) | |
316 >>> nx.add_cycle(G, [10, 11, 12], weight=7) | |
317 """ | |
318 nlist = iter(nodes_for_cycle) | |
319 try: | |
320 first_node = next(nlist) | |
321 except StopIteration: | |
322 return | |
323 G_to_add_to.add_node(first_node) | |
324 G_to_add_to.add_edges_from( | |
325 pairwise(chain((first_node,), nlist), cyclic=True), **attr | |
326 ) | |
327 | |
328 | |
329 def subgraph(G, nbunch): | |
330 """Returns the subgraph induced on nodes in nbunch. | |
331 | |
332 Parameters | |
333 ---------- | |
334 G : graph | |
335 A NetworkX graph | |
336 | |
337 nbunch : list, iterable | |
338 A container of nodes that will be iterated through once (thus | |
339 it should be an iterator or be iterable). Each element of the | |
340 container should be a valid node type: any hashable type except | |
341 None. If nbunch is None, return all edges data in the graph. | |
342 Nodes in nbunch that are not in the graph will be (quietly) | |
343 ignored. | |
344 | |
345 Notes | |
346 ----- | |
347 subgraph(G) calls G.subgraph() | |
348 """ | |
349 return G.subgraph(nbunch) | |
350 | |
351 | |
352 def induced_subgraph(G, nbunch): | |
353 """Returns a SubGraph view of `G` showing only nodes in nbunch. | |
354 | |
355 The induced subgraph of a graph on a set of nodes N is the | |
356 graph with nodes N and edges from G which have both ends in N. | |
357 | |
358 Parameters | |
359 ---------- | |
360 G : NetworkX Graph | |
361 nbunch : node, container of nodes or None (for all nodes) | |
362 | |
363 Returns | |
364 ------- | |
365 subgraph : SubGraph View | |
366 A read-only view of the subgraph in `G` induced by the nodes. | |
367 Changes to the graph `G` will be reflected in the view. | |
368 | |
369 Notes | |
370 ----- | |
371 To create a mutable subgraph with its own copies of nodes | |
372 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` | |
373 | |
374 For an inplace reduction of a graph to a subgraph you can remove nodes: | |
375 `G.remove_nodes_from(n in G if n not in set(nbunch))` | |
376 | |
377 If you are going to compute subgraphs of your subgraphs you could | |
378 end up with a chain of views that can be very slow once the chain | |
379 has about 15 views in it. If they are all induced subgraphs, you | |
380 can short-cut the chain by making them all subgraphs of the original | |
381 graph. The graph class method `G.subgraph` does this when `G` is | |
382 a subgraph. In contrast, this function allows you to choose to build | |
383 chains or not, as you wish. The returned subgraph is a view on `G`. | |
384 | |
385 Examples | |
386 -------- | |
387 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc | |
388 >>> H = G.subgraph([0, 1, 2]) | |
389 >>> list(H.edges) | |
390 [(0, 1), (1, 2)] | |
391 """ | |
392 induced_nodes = nx.filters.show_nodes(G.nbunch_iter(nbunch)) | |
393 return nx.graphviews.subgraph_view(G, induced_nodes) | |
394 | |
395 | |
396 def edge_subgraph(G, edges): | |
397 """Returns a view of the subgraph induced by the specified edges. | |
398 | |
399 The induced subgraph contains each edge in `edges` and each | |
400 node incident to any of those edges. | |
401 | |
402 Parameters | |
403 ---------- | |
404 G : NetworkX Graph | |
405 edges : iterable | |
406 An iterable of edges. Edges not present in `G` are ignored. | |
407 | |
408 Returns | |
409 ------- | |
410 subgraph : SubGraph View | |
411 A read-only edge-induced subgraph of `G`. | |
412 Changes to `G` are reflected in the view. | |
413 | |
414 Notes | |
415 ----- | |
416 To create a mutable subgraph with its own copies of nodes | |
417 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` | |
418 | |
419 If you create a subgraph of a subgraph recursively you can end up | |
420 with a chain of subgraphs that becomes very slow with about 15 | |
421 nested subgraph views. Luckily the edge_subgraph filter nests | |
422 nicely so you can use the original graph as G in this function | |
423 to avoid chains. We do not rule out chains programmatically so | |
424 that odd cases like an `edge_subgraph` of a `restricted_view` | |
425 can be created. | |
426 | |
427 Examples | |
428 -------- | |
429 >>> G = nx.path_graph(5) | |
430 >>> H = G.edge_subgraph([(0, 1), (3, 4)]) | |
431 >>> list(H.nodes) | |
432 [0, 1, 3, 4] | |
433 >>> list(H.edges) | |
434 [(0, 1), (3, 4)] | |
435 """ | |
436 nxf = nx.filters | |
437 edges = set(edges) | |
438 nodes = set() | |
439 for e in edges: | |
440 nodes.update(e[:2]) | |
441 induced_nodes = nxf.show_nodes(nodes) | |
442 if G.is_multigraph(): | |
443 if G.is_directed(): | |
444 induced_edges = nxf.show_multidiedges(edges) | |
445 else: | |
446 induced_edges = nxf.show_multiedges(edges) | |
447 else: | |
448 if G.is_directed(): | |
449 induced_edges = nxf.show_diedges(edges) | |
450 else: | |
451 induced_edges = nxf.show_edges(edges) | |
452 return nx.graphviews.subgraph_view(G, induced_nodes, induced_edges) | |
453 | |
454 | |
455 def restricted_view(G, nodes, edges): | |
456 """Returns a view of `G` with hidden nodes and edges. | |
457 | |
458 The resulting subgraph filters out node `nodes` and edges `edges`. | |
459 Filtered out nodes also filter out any of their edges. | |
460 | |
461 Parameters | |
462 ---------- | |
463 G : NetworkX Graph | |
464 nodes : iterable | |
465 An iterable of nodes. Nodes not present in `G` are ignored. | |
466 edges : iterable | |
467 An iterable of edges. Edges not present in `G` are ignored. | |
468 | |
469 Returns | |
470 ------- | |
471 subgraph : SubGraph View | |
472 A read-only restricted view of `G` filtering out nodes and edges. | |
473 Changes to `G` are reflected in the view. | |
474 | |
475 Notes | |
476 ----- | |
477 To create a mutable subgraph with its own copies of nodes | |
478 edges and attributes use `subgraph.copy()` or `Graph(subgraph)` | |
479 | |
480 If you create a subgraph of a subgraph recursively you may end up | |
481 with a chain of subgraph views. Such chains can get quite slow | |
482 for lengths near 15. To avoid long chains, try to make your subgraph | |
483 based on the original graph. We do not rule out chains programmatically | |
484 so that odd cases like an `edge_subgraph` of a `restricted_view` | |
485 can be created. | |
486 | |
487 Examples | |
488 -------- | |
489 >>> G = nx.path_graph(5) | |
490 >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)]) | |
491 >>> list(H.nodes) | |
492 [1, 2, 3, 4] | |
493 >>> list(H.edges) | |
494 [(2, 3)] | |
495 """ | |
496 nxf = nx.filters | |
497 hide_nodes = nxf.hide_nodes(nodes) | |
498 if G.is_multigraph(): | |
499 if G.is_directed(): | |
500 hide_edges = nxf.hide_multidiedges(edges) | |
501 else: | |
502 hide_edges = nxf.hide_multiedges(edges) | |
503 else: | |
504 if G.is_directed(): | |
505 hide_edges = nxf.hide_diedges(edges) | |
506 else: | |
507 hide_edges = nxf.hide_edges(edges) | |
508 return nx.graphviews.subgraph_view(G, hide_nodes, hide_edges) | |
509 | |
510 | |
511 def to_directed(graph): | |
512 """Returns a directed view of the graph `graph`. | |
513 | |
514 Identical to graph.to_directed(as_view=True) | |
515 Note that graph.to_directed defaults to `as_view=False` | |
516 while this function always provides a view. | |
517 """ | |
518 return graph.to_directed(as_view=True) | |
519 | |
520 | |
521 def to_undirected(graph): | |
522 """Returns an undirected view of the graph `graph`. | |
523 | |
524 Identical to graph.to_undirected(as_view=True) | |
525 Note that graph.to_undirected defaults to `as_view=False` | |
526 while this function always provides a view. | |
527 """ | |
528 return graph.to_undirected(as_view=True) | |
529 | |
530 | |
531 def create_empty_copy(G, with_data=True): | |
532 """Returns a copy of the graph G with all of the edges removed. | |
533 | |
534 Parameters | |
535 ---------- | |
536 G : graph | |
537 A NetworkX graph | |
538 | |
539 with_data : bool (default=True) | |
540 Propagate Graph and Nodes data to the new graph. | |
541 | |
542 See Also | |
543 ----- | |
544 empty_graph | |
545 | |
546 """ | |
547 H = G.__class__() | |
548 H.add_nodes_from(G.nodes(data=with_data)) | |
549 if with_data: | |
550 H.graph.update(G.graph) | |
551 return H | |
552 | |
553 | |
554 def info(G, n=None): | |
555 """Return a summary of information for the graph G or a single node n. | |
556 | |
557 The summary includes the number of nodes and edges (or neighbours for a single | |
558 node), and their average degree. | |
559 | |
560 Parameters | |
561 ---------- | |
562 G : Networkx graph | |
563 A graph | |
564 n : node (any hashable) | |
565 A node in the graph G | |
566 | |
567 Returns | |
568 ------- | |
569 info : str | |
570 A string containing the short summary | |
571 | |
572 Raises | |
573 ------ | |
574 NetworkXError | |
575 If n is not in the graph G | |
576 | |
577 """ | |
578 info = "" # append this all to a string | |
579 if n is None: | |
580 info += f"Name: {G.name}\n" | |
581 type_name = [type(G).__name__] | |
582 info += f"Type: {','.join(type_name)}\n" | |
583 info += f"Number of nodes: {G.number_of_nodes()}\n" | |
584 info += f"Number of edges: {G.number_of_edges()}\n" | |
585 nnodes = G.number_of_nodes() | |
586 if len(G) > 0: | |
587 if G.is_directed(): | |
588 deg = sum(d for n, d in G.in_degree()) / float(nnodes) | |
589 info += f"Average in degree: {deg:8.4f}\n" | |
590 deg = sum(d for n, d in G.out_degree()) / float(nnodes) | |
591 info += f"Average out degree: {deg:8.4f}" | |
592 else: | |
593 s = sum(dict(G.degree()).values()) | |
594 info += f"Average degree: {(float(s) / float(nnodes)):8.4f}" | |
595 else: | |
596 if n not in G: | |
597 raise nx.NetworkXError(f"node {n} not in graph") | |
598 info += f"Node {n} has the following properties:\n" | |
599 info += f"Degree: {G.degree(n)}\n" | |
600 info += "Neighbors: " | |
601 info += " ".join(str(nbr) for nbr in G.neighbors(n)) | |
602 return info | |
603 | |
604 | |
605 def set_node_attributes(G, values, name=None): | |
606 """Sets node attributes from a given value or dictionary of values. | |
607 | |
608 .. Warning:: The call order of arguments `values` and `name` | |
609 switched between v1.x & v2.x. | |
610 | |
611 Parameters | |
612 ---------- | |
613 G : NetworkX Graph | |
614 | |
615 values : scalar value, dict-like | |
616 What the node attribute should be set to. If `values` is | |
617 not a dictionary, then it is treated as a single attribute value | |
618 that is then applied to every node in `G`. This means that if | |
619 you provide a mutable object, like a list, updates to that object | |
620 will be reflected in the node attribute for every node. | |
621 The attribute name will be `name`. | |
622 | |
623 If `values` is a dict or a dict of dict, it should be keyed | |
624 by node to either an attribute value or a dict of attribute key/value | |
625 pairs used to update the node's attributes. | |
626 | |
627 name : string (optional, default=None) | |
628 Name of the node attribute to set if values is a scalar. | |
629 | |
630 Examples | |
631 -------- | |
632 After computing some property of the nodes of a graph, you may want | |
633 to assign a node attribute to store the value of that property for | |
634 each node:: | |
635 | |
636 >>> G = nx.path_graph(3) | |
637 >>> bb = nx.betweenness_centrality(G) | |
638 >>> isinstance(bb, dict) | |
639 True | |
640 >>> nx.set_node_attributes(G, bb, "betweenness") | |
641 >>> G.nodes[1]["betweenness"] | |
642 1.0 | |
643 | |
644 If you provide a list as the second argument, updates to the list | |
645 will be reflected in the node attribute for each node:: | |
646 | |
647 >>> G = nx.path_graph(3) | |
648 >>> labels = [] | |
649 >>> nx.set_node_attributes(G, labels, "labels") | |
650 >>> labels.append("foo") | |
651 >>> G.nodes[0]["labels"] | |
652 ['foo'] | |
653 >>> G.nodes[1]["labels"] | |
654 ['foo'] | |
655 >>> G.nodes[2]["labels"] | |
656 ['foo'] | |
657 | |
658 If you provide a dictionary of dictionaries as the second argument, | |
659 the outer dictionary is assumed to be keyed by node to an inner | |
660 dictionary of node attributes for that node:: | |
661 | |
662 >>> G = nx.path_graph(3) | |
663 >>> attrs = {0: {"attr1": 20, "attr2": "nothing"}, 1: {"attr2": 3}} | |
664 >>> nx.set_node_attributes(G, attrs) | |
665 >>> G.nodes[0]["attr1"] | |
666 20 | |
667 >>> G.nodes[0]["attr2"] | |
668 'nothing' | |
669 >>> G.nodes[1]["attr2"] | |
670 3 | |
671 >>> G.nodes[2] | |
672 {} | |
673 | |
674 """ | |
675 # Set node attributes based on type of `values` | |
676 if name is not None: # `values` must not be a dict of dict | |
677 try: # `values` is a dict | |
678 for n, v in values.items(): | |
679 try: | |
680 G.nodes[n][name] = values[n] | |
681 except KeyError: | |
682 pass | |
683 except AttributeError: # `values` is a constant | |
684 for n in G: | |
685 G.nodes[n][name] = values | |
686 else: # `values` must be dict of dict | |
687 for n, d in values.items(): | |
688 try: | |
689 G.nodes[n].update(d) | |
690 except KeyError: | |
691 pass | |
692 | |
693 | |
694 def get_node_attributes(G, name): | |
695 """Get node attributes from graph | |
696 | |
697 Parameters | |
698 ---------- | |
699 G : NetworkX Graph | |
700 | |
701 name : string | |
702 Attribute name | |
703 | |
704 Returns | |
705 ------- | |
706 Dictionary of attributes keyed by node. | |
707 | |
708 Examples | |
709 -------- | |
710 >>> G = nx.Graph() | |
711 >>> G.add_nodes_from([1, 2, 3], color="red") | |
712 >>> color = nx.get_node_attributes(G, "color") | |
713 >>> color[1] | |
714 'red' | |
715 """ | |
716 return {n: d[name] for n, d in G.nodes.items() if name in d} | |
717 | |
718 | |
719 def set_edge_attributes(G, values, name=None): | |
720 """Sets edge attributes from a given value or dictionary of values. | |
721 | |
722 .. Warning:: The call order of arguments `values` and `name` | |
723 switched between v1.x & v2.x. | |
724 | |
725 Parameters | |
726 ---------- | |
727 G : NetworkX Graph | |
728 | |
729 values : scalar value, dict-like | |
730 What the edge attribute should be set to. If `values` is | |
731 not a dictionary, then it is treated as a single attribute value | |
732 that is then applied to every edge in `G`. This means that if | |
733 you provide a mutable object, like a list, updates to that object | |
734 will be reflected in the edge attribute for each edge. The attribute | |
735 name will be `name`. | |
736 | |
737 If `values` is a dict or a dict of dict, it should be keyed | |
738 by edge tuple to either an attribute value or a dict of attribute | |
739 key/value pairs used to update the edge's attributes. | |
740 For multigraphs, the edge tuples must be of the form ``(u, v, key)``, | |
741 where `u` and `v` are nodes and `key` is the edge key. | |
742 For non-multigraphs, the keys must be tuples of the form ``(u, v)``. | |
743 | |
744 name : string (optional, default=None) | |
745 Name of the edge attribute to set if values is a scalar. | |
746 | |
747 Examples | |
748 -------- | |
749 After computing some property of the edges of a graph, you may want | |
750 to assign a edge attribute to store the value of that property for | |
751 each edge:: | |
752 | |
753 >>> G = nx.path_graph(3) | |
754 >>> bb = nx.edge_betweenness_centrality(G, normalized=False) | |
755 >>> nx.set_edge_attributes(G, bb, "betweenness") | |
756 >>> G.edges[1, 2]["betweenness"] | |
757 2.0 | |
758 | |
759 If you provide a list as the second argument, updates to the list | |
760 will be reflected in the edge attribute for each edge:: | |
761 | |
762 >>> labels = [] | |
763 >>> nx.set_edge_attributes(G, labels, "labels") | |
764 >>> labels.append("foo") | |
765 >>> G.edges[0, 1]["labels"] | |
766 ['foo'] | |
767 >>> G.edges[1, 2]["labels"] | |
768 ['foo'] | |
769 | |
770 If you provide a dictionary of dictionaries as the second argument, | |
771 the entire dictionary will be used to update edge attributes:: | |
772 | |
773 >>> G = nx.path_graph(3) | |
774 >>> attrs = {(0, 1): {"attr1": 20, "attr2": "nothing"}, (1, 2): {"attr2": 3}} | |
775 >>> nx.set_edge_attributes(G, attrs) | |
776 >>> G[0][1]["attr1"] | |
777 20 | |
778 >>> G[0][1]["attr2"] | |
779 'nothing' | |
780 >>> G[1][2]["attr2"] | |
781 3 | |
782 | |
783 """ | |
784 if name is not None: | |
785 # `values` does not contain attribute names | |
786 try: | |
787 # if `values` is a dict using `.items()` => {edge: value} | |
788 if G.is_multigraph(): | |
789 for (u, v, key), value in values.items(): | |
790 try: | |
791 G[u][v][key][name] = value | |
792 except KeyError: | |
793 pass | |
794 else: | |
795 for (u, v), value in values.items(): | |
796 try: | |
797 G[u][v][name] = value | |
798 except KeyError: | |
799 pass | |
800 except AttributeError: | |
801 # treat `values` as a constant | |
802 for u, v, data in G.edges(data=True): | |
803 data[name] = values | |
804 else: | |
805 # `values` consists of doct-of-dict {edge: {attr: value}} shape | |
806 if G.is_multigraph(): | |
807 for (u, v, key), d in values.items(): | |
808 try: | |
809 G[u][v][key].update(d) | |
810 except KeyError: | |
811 pass | |
812 else: | |
813 for (u, v), d in values.items(): | |
814 try: | |
815 G[u][v].update(d) | |
816 except KeyError: | |
817 pass | |
818 | |
819 | |
820 def get_edge_attributes(G, name): | |
821 """Get edge attributes from graph | |
822 | |
823 Parameters | |
824 ---------- | |
825 G : NetworkX Graph | |
826 | |
827 name : string | |
828 Attribute name | |
829 | |
830 Returns | |
831 ------- | |
832 Dictionary of attributes keyed by edge. For (di)graphs, the keys are | |
833 2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of | |
834 the form: (u, v, key). | |
835 | |
836 Examples | |
837 -------- | |
838 >>> G = nx.Graph() | |
839 >>> nx.add_path(G, [1, 2, 3], color="red") | |
840 >>> color = nx.get_edge_attributes(G, "color") | |
841 >>> color[(1, 2)] | |
842 'red' | |
843 """ | |
844 if G.is_multigraph(): | |
845 edges = G.edges(keys=True, data=True) | |
846 else: | |
847 edges = G.edges(data=True) | |
848 return {x[:-1]: x[-1][name] for x in edges if name in x[-1]} | |
849 | |
850 | |
851 def all_neighbors(graph, node): | |
852 """Returns all of the neighbors of a node in the graph. | |
853 | |
854 If the graph is directed returns predecessors as well as successors. | |
855 | |
856 Parameters | |
857 ---------- | |
858 graph : NetworkX graph | |
859 Graph to find neighbors. | |
860 | |
861 node : node | |
862 The node whose neighbors will be returned. | |
863 | |
864 Returns | |
865 ------- | |
866 neighbors : iterator | |
867 Iterator of neighbors | |
868 """ | |
869 if graph.is_directed(): | |
870 values = chain(graph.predecessors(node), graph.successors(node)) | |
871 else: | |
872 values = graph.neighbors(node) | |
873 return values | |
874 | |
875 | |
876 def non_neighbors(graph, node): | |
877 """Returns the non-neighbors of the node in the graph. | |
878 | |
879 Parameters | |
880 ---------- | |
881 graph : NetworkX graph | |
882 Graph to find neighbors. | |
883 | |
884 node : node | |
885 The node whose neighbors will be returned. | |
886 | |
887 Returns | |
888 ------- | |
889 non_neighbors : iterator | |
890 Iterator of nodes in the graph that are not neighbors of the node. | |
891 """ | |
892 nbors = set(neighbors(graph, node)) | {node} | |
893 return (nnode for nnode in graph if nnode not in nbors) | |
894 | |
895 | |
896 def non_edges(graph): | |
897 """Returns the non-existent edges in the graph. | |
898 | |
899 Parameters | |
900 ---------- | |
901 graph : NetworkX graph. | |
902 Graph to find non-existent edges. | |
903 | |
904 Returns | |
905 ------- | |
906 non_edges : iterator | |
907 Iterator of edges that are not in the graph. | |
908 """ | |
909 if graph.is_directed(): | |
910 for u in graph: | |
911 for v in non_neighbors(graph, u): | |
912 yield (u, v) | |
913 else: | |
914 nodes = set(graph) | |
915 while nodes: | |
916 u = nodes.pop() | |
917 for v in nodes - set(graph[u]): | |
918 yield (u, v) | |
919 | |
920 | |
921 @not_implemented_for("directed") | |
922 def common_neighbors(G, u, v): | |
923 """Returns the common neighbors of two nodes in a graph. | |
924 | |
925 Parameters | |
926 ---------- | |
927 G : graph | |
928 A NetworkX undirected graph. | |
929 | |
930 u, v : nodes | |
931 Nodes in the graph. | |
932 | |
933 Returns | |
934 ------- | |
935 cnbors : iterator | |
936 Iterator of common neighbors of u and v in the graph. | |
937 | |
938 Raises | |
939 ------ | |
940 NetworkXError | |
941 If u or v is not a node in the graph. | |
942 | |
943 Examples | |
944 -------- | |
945 >>> G = nx.complete_graph(5) | |
946 >>> sorted(nx.common_neighbors(G, 0, 1)) | |
947 [2, 3, 4] | |
948 """ | |
949 if u not in G: | |
950 raise nx.NetworkXError("u is not in the graph.") | |
951 if v not in G: | |
952 raise nx.NetworkXError("v is not in the graph.") | |
953 | |
954 # Return a generator explicitly instead of yielding so that the above | |
955 # checks are executed eagerly. | |
956 return (w for w in G[u] if w in G[v] and w not in (u, v)) | |
957 | |
958 | |
959 def is_weighted(G, edge=None, weight="weight"): | |
960 """Returns True if `G` has weighted edges. | |
961 | |
962 Parameters | |
963 ---------- | |
964 G : graph | |
965 A NetworkX graph. | |
966 | |
967 edge : tuple, optional | |
968 A 2-tuple specifying the only edge in `G` that will be tested. If | |
969 None, then every edge in `G` is tested. | |
970 | |
971 weight: string, optional | |
972 The attribute name used to query for edge weights. | |
973 | |
974 Returns | |
975 ------- | |
976 bool | |
977 A boolean signifying if `G`, or the specified edge, is weighted. | |
978 | |
979 Raises | |
980 ------ | |
981 NetworkXError | |
982 If the specified edge does not exist. | |
983 | |
984 Examples | |
985 -------- | |
986 >>> G = nx.path_graph(4) | |
987 >>> nx.is_weighted(G) | |
988 False | |
989 >>> nx.is_weighted(G, (2, 3)) | |
990 False | |
991 | |
992 >>> G = nx.DiGraph() | |
993 >>> G.add_edge(1, 2, weight=1) | |
994 >>> nx.is_weighted(G) | |
995 True | |
996 | |
997 """ | |
998 if edge is not None: | |
999 data = G.get_edge_data(*edge) | |
1000 if data is None: | |
1001 msg = f"Edge {edge!r} does not exist." | |
1002 raise nx.NetworkXError(msg) | |
1003 return weight in data | |
1004 | |
1005 if is_empty(G): | |
1006 # Special handling required since: all([]) == True | |
1007 return False | |
1008 | |
1009 return all(weight in data for u, v, data in G.edges(data=True)) | |
1010 | |
1011 | |
1012 def is_negatively_weighted(G, edge=None, weight="weight"): | |
1013 """Returns True if `G` has negatively weighted edges. | |
1014 | |
1015 Parameters | |
1016 ---------- | |
1017 G : graph | |
1018 A NetworkX graph. | |
1019 | |
1020 edge : tuple, optional | |
1021 A 2-tuple specifying the only edge in `G` that will be tested. If | |
1022 None, then every edge in `G` is tested. | |
1023 | |
1024 weight: string, optional | |
1025 The attribute name used to query for edge weights. | |
1026 | |
1027 Returns | |
1028 ------- | |
1029 bool | |
1030 A boolean signifying if `G`, or the specified edge, is negatively | |
1031 weighted. | |
1032 | |
1033 Raises | |
1034 ------ | |
1035 NetworkXError | |
1036 If the specified edge does not exist. | |
1037 | |
1038 Examples | |
1039 -------- | |
1040 >>> G = nx.Graph() | |
1041 >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)]) | |
1042 >>> G.add_edge(1, 2, weight=4) | |
1043 >>> nx.is_negatively_weighted(G, (1, 2)) | |
1044 False | |
1045 >>> G[2][4]["weight"] = -2 | |
1046 >>> nx.is_negatively_weighted(G) | |
1047 True | |
1048 >>> G = nx.DiGraph() | |
1049 >>> edges = [("0", "3", 3), ("0", "1", -5), ("1", "0", -2)] | |
1050 >>> G.add_weighted_edges_from(edges) | |
1051 >>> nx.is_negatively_weighted(G) | |
1052 True | |
1053 | |
1054 """ | |
1055 if edge is not None: | |
1056 data = G.get_edge_data(*edge) | |
1057 if data is None: | |
1058 msg = f"Edge {edge!r} does not exist." | |
1059 raise nx.NetworkXError(msg) | |
1060 return weight in data and data[weight] < 0 | |
1061 | |
1062 return any(weight in data and data[weight] < 0 for u, v, data in G.edges(data=True)) | |
1063 | |
1064 | |
1065 def is_empty(G): | |
1066 """Returns True if `G` has no edges. | |
1067 | |
1068 Parameters | |
1069 ---------- | |
1070 G : graph | |
1071 A NetworkX graph. | |
1072 | |
1073 Returns | |
1074 ------- | |
1075 bool | |
1076 True if `G` has no edges, and False otherwise. | |
1077 | |
1078 Notes | |
1079 ----- | |
1080 An empty graph can have nodes but not edges. The empty graph with zero | |
1081 nodes is known as the null graph. This is an $O(n)$ operation where n | |
1082 is the number of nodes in the graph. | |
1083 | |
1084 """ | |
1085 return not any(G.adj.values()) | |
1086 | |
1087 | |
1088 def nodes_with_selfloops(G): | |
1089 """Returns an iterator over nodes with self loops. | |
1090 | |
1091 A node with a self loop has an edge with both ends adjacent | |
1092 to that node. | |
1093 | |
1094 Returns | |
1095 ------- | |
1096 nodelist : iterator | |
1097 A iterator over nodes with self loops. | |
1098 | |
1099 See Also | |
1100 -------- | |
1101 selfloop_edges, number_of_selfloops | |
1102 | |
1103 Examples | |
1104 -------- | |
1105 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc | |
1106 >>> G.add_edge(1, 1) | |
1107 >>> G.add_edge(1, 2) | |
1108 >>> list(nx.nodes_with_selfloops(G)) | |
1109 [1] | |
1110 | |
1111 """ | |
1112 return (n for n, nbrs in G.adj.items() if n in nbrs) | |
1113 | |
1114 | |
1115 def selfloop_edges(G, data=False, keys=False, default=None): | |
1116 """Returns an iterator over selfloop edges. | |
1117 | |
1118 A selfloop edge has the same node at both ends. | |
1119 | |
1120 Parameters | |
1121 ---------- | |
1122 data : string or bool, optional (default=False) | |
1123 Return selfloop edges as two tuples (u, v) (data=False) | |
1124 or three-tuples (u, v, datadict) (data=True) | |
1125 or three-tuples (u, v, datavalue) (data='attrname') | |
1126 keys : bool, optional (default=False) | |
1127 If True, return edge keys with each edge. | |
1128 default : value, optional (default=None) | |
1129 Value used for edges that don't have the requested attribute. | |
1130 Only relevant if data is not True or False. | |
1131 | |
1132 Returns | |
1133 ------- | |
1134 edgeiter : iterator over edge tuples | |
1135 An iterator over all selfloop edges. | |
1136 | |
1137 See Also | |
1138 -------- | |
1139 nodes_with_selfloops, number_of_selfloops | |
1140 | |
1141 Examples | |
1142 -------- | |
1143 >>> G = nx.MultiGraph() # or Graph, DiGraph, MultiDiGraph, etc | |
1144 >>> ekey = G.add_edge(1, 1) | |
1145 >>> ekey = G.add_edge(1, 2) | |
1146 >>> list(nx.selfloop_edges(G)) | |
1147 [(1, 1)] | |
1148 >>> list(nx.selfloop_edges(G, data=True)) | |
1149 [(1, 1, {})] | |
1150 >>> list(nx.selfloop_edges(G, keys=True)) | |
1151 [(1, 1, 0)] | |
1152 >>> list(nx.selfloop_edges(G, keys=True, data=True)) | |
1153 [(1, 1, 0, {})] | |
1154 """ | |
1155 if data is True: | |
1156 if G.is_multigraph(): | |
1157 if keys is True: | |
1158 return ( | |
1159 (n, n, k, d) | |
1160 for n, nbrs in G.adj.items() | |
1161 if n in nbrs | |
1162 for k, d in nbrs[n].items() | |
1163 ) | |
1164 else: | |
1165 return ( | |
1166 (n, n, d) | |
1167 for n, nbrs in G.adj.items() | |
1168 if n in nbrs | |
1169 for d in nbrs[n].values() | |
1170 ) | |
1171 else: | |
1172 return ((n, n, nbrs[n]) for n, nbrs in G.adj.items() if n in nbrs) | |
1173 elif data is not False: | |
1174 if G.is_multigraph(): | |
1175 if keys is True: | |
1176 return ( | |
1177 (n, n, k, d.get(data, default)) | |
1178 for n, nbrs in G.adj.items() | |
1179 if n in nbrs | |
1180 for k, d in nbrs[n].items() | |
1181 ) | |
1182 else: | |
1183 return ( | |
1184 (n, n, d.get(data, default)) | |
1185 for n, nbrs in G.adj.items() | |
1186 if n in nbrs | |
1187 for d in nbrs[n].values() | |
1188 ) | |
1189 else: | |
1190 return ( | |
1191 (n, n, nbrs[n].get(data, default)) | |
1192 for n, nbrs in G.adj.items() | |
1193 if n in nbrs | |
1194 ) | |
1195 else: | |
1196 if G.is_multigraph(): | |
1197 if keys is True: | |
1198 return ( | |
1199 (n, n, k) for n, nbrs in G.adj.items() if n in nbrs for k in nbrs[n] | |
1200 ) | |
1201 else: | |
1202 return ( | |
1203 (n, n) | |
1204 for n, nbrs in G.adj.items() | |
1205 if n in nbrs | |
1206 for i in range(len(nbrs[n])) # for easy edge removal (#4068) | |
1207 ) | |
1208 else: | |
1209 return ((n, n) for n, nbrs in G.adj.items() if n in nbrs) | |
1210 | |
1211 | |
1212 def number_of_selfloops(G): | |
1213 """Returns the number of selfloop edges. | |
1214 | |
1215 A selfloop edge has the same node at both ends. | |
1216 | |
1217 Returns | |
1218 ------- | |
1219 nloops : int | |
1220 The number of selfloops. | |
1221 | |
1222 See Also | |
1223 -------- | |
1224 nodes_with_selfloops, selfloop_edges | |
1225 | |
1226 Examples | |
1227 -------- | |
1228 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc | |
1229 >>> G.add_edge(1, 1) | |
1230 >>> G.add_edge(1, 2) | |
1231 >>> nx.number_of_selfloops(G) | |
1232 1 | |
1233 """ | |
1234 return sum(1 for _ in nx.selfloop_edges(G)) | |
1235 | |
1236 | |
1237 def is_path(G, path): | |
1238 """Returns whether or not the specified path exists | |
1239 | |
1240 Parameters | |
1241 ---------- | |
1242 G : graph | |
1243 A NetworkX graph. | |
1244 | |
1245 path: list | |
1246 A list of node labels which defines the path to traverse | |
1247 | |
1248 Returns | |
1249 ------- | |
1250 isPath: bool | |
1251 A boolean representing whether or not the path exists | |
1252 | |
1253 """ | |
1254 for node, nbr in nx.utils.pairwise(path): | |
1255 if nbr not in G[node]: | |
1256 return False | |
1257 return True | |
1258 | |
1259 | |
1260 def path_weight(G, path, weight): | |
1261 """Returns total cost associated with specified path and weight | |
1262 | |
1263 Parameters | |
1264 ---------- | |
1265 G : graph | |
1266 A NetworkX graph. | |
1267 | |
1268 path: list | |
1269 A list of node labels which defines the path to traverse | |
1270 | |
1271 weight: string | |
1272 A string indicating which edge attribute to use for path cost | |
1273 | |
1274 Returns | |
1275 ------- | |
1276 cost: int | |
1277 A integer representing the total cost with respect to the | |
1278 specified weight of the specified path | |
1279 | |
1280 Raises | |
1281 ------ | |
1282 NetworkXNoPath | |
1283 If the specified edge does not exist. | |
1284 """ | |
1285 multigraph = G.is_multigraph() | |
1286 cost = 0 | |
1287 | |
1288 if not nx.is_path(G, path): | |
1289 raise nx.NetworkXNoPath("path does not exist") | |
1290 for node, nbr in nx.utils.pairwise(path): | |
1291 if multigraph: | |
1292 cost += min([v[weight] for v in G[node][nbr].values()]) | |
1293 else: | |
1294 cost += G[node][nbr][weight] | |
1295 return cost |