### comparison env/lib/python3.9/site-packages/networkx/classes/function.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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",
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
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
219 --------
220 freeze
221 """
222 try:
223 return G.frozen
224 except AttributeError:
225 return False
226
227
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
244 --------
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
259 edges = ((v, n) for n in nlist)
261
262
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
277 --------
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
293
294
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
309 --------
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
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
543 -----
544 empty_graph
545
546 """
547 H = G.__class__()
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)]
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
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
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
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