Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functional interface to graph methods and assorted utilities."""
3from collections import Counter
4from itertools import chain
6import networkx as nx
7from networkx.utils import not_implemented_for, pairwise
9__all__ = [
10 "nodes",
11 "edges",
12 "degree",
13 "degree_histogram",
14 "neighbors",
15 "number_of_nodes",
16 "number_of_edges",
17 "density",
18 "is_directed",
19 "freeze",
20 "is_frozen",
21 "subgraph",
22 "induced_subgraph",
23 "edge_subgraph",
24 "restricted_view",
25 "to_directed",
26 "to_undirected",
27 "add_star",
28 "add_path",
29 "add_cycle",
30 "create_empty_copy",
31 "set_node_attributes",
32 "get_node_attributes",
33 "remove_node_attributes",
34 "set_edge_attributes",
35 "get_edge_attributes",
36 "remove_edge_attributes",
37 "all_neighbors",
38 "non_neighbors",
39 "non_edges",
40 "common_neighbors",
41 "is_weighted",
42 "is_negatively_weighted",
43 "is_empty",
44 "selfloop_edges",
45 "nodes_with_selfloops",
46 "number_of_selfloops",
47 "path_weight",
48 "is_path",
49 "describe",
50]
53def nodes(G):
54 """Returns a NodeView over the graph nodes.
56 This function wraps the :func:`G.nodes <networkx.Graph.nodes>` property.
57 """
58 return G.nodes()
61def edges(G, nbunch=None):
62 """Returns an edge view of edges incident to nodes in nbunch.
64 Return all edges if nbunch is unspecified or nbunch=None.
66 For digraphs, edges=out_edges
68 This function wraps the :func:`G.edges <networkx.Graph.edges>` property.
69 """
70 return G.edges(nbunch)
73def degree(G, nbunch=None, weight=None):
74 """Returns a degree view of single node or of nbunch of nodes.
75 If nbunch is omitted, then return degrees of *all* nodes.
77 This function wraps the :func:`G.degree <networkx.Graph.degree>` property.
78 """
79 return G.degree(nbunch, weight)
82def neighbors(G, n):
83 """Returns an iterator over all neighbors of node n.
85 This function wraps the :func:`G.neighbors <networkx.Graph.neighbors>` function.
86 """
87 return G.neighbors(n)
90def number_of_nodes(G):
91 """Returns the number of nodes in the graph.
93 This function wraps the :func:`G.number_of_nodes <networkx.Graph.number_of_nodes>` function.
94 """
95 return G.number_of_nodes()
98def number_of_edges(G):
99 """Returns the number of edges in the graph.
101 This function wraps the :func:`G.number_of_edges <networkx.Graph.number_of_edges>` function.
102 """
103 return G.number_of_edges()
106def density(G):
107 r"""Returns the density of a graph.
109 The density for undirected graphs is
111 .. math::
113 d = \frac{2m}{n(n-1)},
115 and for directed graphs is
117 .. math::
119 d = \frac{m}{n(n-1)},
121 where `n` is the number of nodes and `m` is the number of edges in `G`.
123 Notes
124 -----
125 The density is 0 for a graph without edges and 1 for a complete graph.
126 The density of multigraphs can be higher than 1.
128 Self loops are counted in the total number of edges so graphs with self
129 loops can have density higher than 1.
130 """
131 n = number_of_nodes(G)
132 m = number_of_edges(G)
133 if m == 0 or n <= 1:
134 return 0
135 d = m / (n * (n - 1))
136 if not G.is_directed():
137 d *= 2
138 return d
141def degree_histogram(G):
142 """Returns a list of the frequency of each degree value.
144 Parameters
145 ----------
146 G : Networkx graph
147 A graph
149 Returns
150 -------
151 hist : list
152 A list of frequencies of degrees.
153 The degree values are the index in the list.
155 Notes
156 -----
157 Note: the bins are width one, hence len(list) can be large
158 (Order(number_of_edges))
159 """
160 counts = Counter(d for n, d in G.degree())
161 return [counts.get(i, 0) for i in range(max(counts) + 1 if counts else 0)]
164def is_directed(G):
165 """Return True if graph is directed."""
166 return G.is_directed()
169def frozen(*args, **kwargs):
170 """Dummy method for raising errors when trying to modify frozen graphs"""
171 raise nx.NetworkXError("Frozen graph can't be modified")
174def freeze(G):
175 """Modify graph to prevent further change by adding or removing
176 nodes or edges.
178 Node and edge data can still be modified.
180 Parameters
181 ----------
182 G : graph
183 A NetworkX graph
185 Examples
186 --------
187 >>> G = nx.path_graph(4)
188 >>> G = nx.freeze(G)
189 >>> try:
190 ... G.add_edge(4, 5)
191 ... except nx.NetworkXError as err:
192 ... print(str(err))
193 Frozen graph can't be modified
195 Notes
196 -----
197 To "unfreeze" a graph you must make a copy by creating a new graph object:
199 >>> graph = nx.path_graph(4)
200 >>> frozen_graph = nx.freeze(graph)
201 >>> unfrozen_graph = nx.Graph(frozen_graph)
202 >>> nx.is_frozen(unfrozen_graph)
203 False
205 See Also
206 --------
207 is_frozen
208 """
209 G.add_node = frozen
210 G.add_nodes_from = frozen
211 G.remove_node = frozen
212 G.remove_nodes_from = frozen
213 G.add_edge = frozen
214 G.add_edges_from = frozen
215 G.add_weighted_edges_from = frozen
216 G.remove_edge = frozen
217 G.remove_edges_from = frozen
218 G.clear = frozen
219 G.clear_edges = frozen
220 G.frozen = True
221 return G
224def is_frozen(G):
225 """Returns True if graph is frozen.
227 Parameters
228 ----------
229 G : graph
230 A NetworkX graph
232 See Also
233 --------
234 freeze
235 """
236 try:
237 return G.frozen
238 except AttributeError:
239 return False
242def add_star(G_to_add_to, nodes_for_star, **attr):
243 """Add a star to Graph G_to_add_to.
245 The first node in `nodes_for_star` is the middle of the star.
246 It is connected to all other nodes.
248 Parameters
249 ----------
250 G_to_add_to : graph
251 A NetworkX graph
252 nodes_for_star : iterable container
253 A container of nodes.
254 attr : keyword arguments, optional (default= no attributes)
255 Attributes to add to every edge in star.
257 See Also
258 --------
259 add_path, add_cycle
261 Examples
262 --------
263 >>> G = nx.Graph()
264 >>> nx.add_star(G, [0, 1, 2, 3])
265 >>> nx.add_star(G, [10, 11, 12], weight=2)
266 """
267 nlist = iter(nodes_for_star)
268 try:
269 v = next(nlist)
270 except StopIteration:
271 return
272 G_to_add_to.add_node(v)
273 edges = ((v, n) for n in nlist)
274 G_to_add_to.add_edges_from(edges, **attr)
277def add_path(G_to_add_to, nodes_for_path, **attr):
278 """Add a path to the Graph G_to_add_to.
280 Parameters
281 ----------
282 G_to_add_to : graph
283 A NetworkX graph
284 nodes_for_path : iterable container
285 A container of nodes. A path will be constructed from
286 the nodes (in order) and added to the graph.
287 attr : keyword arguments, optional (default= no attributes)
288 Attributes to add to every edge in path.
290 See Also
291 --------
292 add_star, add_cycle
294 Examples
295 --------
296 >>> G = nx.Graph()
297 >>> nx.add_path(G, [0, 1, 2, 3])
298 >>> nx.add_path(G, [10, 11, 12], weight=7)
299 """
300 nlist = iter(nodes_for_path)
301 try:
302 first_node = next(nlist)
303 except StopIteration:
304 return
305 G_to_add_to.add_node(first_node)
306 G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist)), **attr)
309def add_cycle(G_to_add_to, nodes_for_cycle, **attr):
310 """Add a cycle to the Graph G_to_add_to.
312 Parameters
313 ----------
314 G_to_add_to : graph
315 A NetworkX graph
316 nodes_for_cycle: iterable container
317 A container of nodes. A cycle will be constructed from
318 the nodes (in order) and added to the graph.
319 attr : keyword arguments, optional (default= no attributes)
320 Attributes to add to every edge in cycle.
322 See Also
323 --------
324 add_path, add_star
326 Examples
327 --------
328 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
329 >>> nx.add_cycle(G, [0, 1, 2, 3])
330 >>> nx.add_cycle(G, [10, 11, 12], weight=7)
331 """
332 nlist = iter(nodes_for_cycle)
333 try:
334 first_node = next(nlist)
335 except StopIteration:
336 return
337 G_to_add_to.add_node(first_node)
338 G_to_add_to.add_edges_from(
339 pairwise(chain((first_node,), nlist), cyclic=True), **attr
340 )
343def subgraph(G, nbunch):
344 """Returns the subgraph induced on nodes in nbunch.
346 Parameters
347 ----------
348 G : graph
349 A NetworkX graph
351 nbunch : list, iterable
352 A container of nodes that will be iterated through once (thus
353 it should be an iterator or be iterable). Each element of the
354 container should be a valid node type: any hashable type except
355 None. If nbunch is None, return all edges data in the graph.
356 Nodes in nbunch that are not in the graph will be (quietly)
357 ignored.
359 Notes
360 -----
361 subgraph(G) calls G.subgraph()
362 """
363 return G.subgraph(nbunch)
366def induced_subgraph(G, nbunch):
367 """Returns a SubGraph view of `G` showing only nodes in nbunch.
369 The induced subgraph of a graph on a set of nodes N is the
370 graph with nodes N and edges from G which have both ends in N.
372 Parameters
373 ----------
374 G : NetworkX Graph
375 nbunch : node, container of nodes or None (for all nodes)
377 Returns
378 -------
379 subgraph : SubGraph View
380 A read-only view of the subgraph in `G` induced by the nodes.
381 Changes to the graph `G` will be reflected in the view.
383 Notes
384 -----
385 To create a mutable subgraph with its own copies of nodes
386 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
388 For an inplace reduction of a graph to a subgraph you can remove nodes:
389 `G.remove_nodes_from(n in G if n not in set(nbunch))`
391 If you are going to compute subgraphs of your subgraphs you could
392 end up with a chain of views that can be very slow once the chain
393 has about 15 views in it. If they are all induced subgraphs, you
394 can short-cut the chain by making them all subgraphs of the original
395 graph. The graph class method `G.subgraph` does this when `G` is
396 a subgraph. In contrast, this function allows you to choose to build
397 chains or not, as you wish. The returned subgraph is a view on `G`.
399 Examples
400 --------
401 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
402 >>> H = nx.induced_subgraph(G, [0, 1, 3])
403 >>> list(H.edges)
404 [(0, 1)]
405 >>> list(H.nodes)
406 [0, 1, 3]
407 """
408 induced_nodes = nx.filters.show_nodes(G.nbunch_iter(nbunch))
409 return nx.subgraph_view(G, filter_node=induced_nodes)
412def edge_subgraph(G, edges):
413 """Returns a view of the subgraph induced by the specified edges.
415 The induced subgraph contains each edge in `edges` and each
416 node incident to any of those edges.
418 Parameters
419 ----------
420 G : NetworkX Graph
421 edges : iterable
422 An iterable of edges. Edges not present in `G` are ignored.
424 Returns
425 -------
426 subgraph : SubGraph View
427 A read-only edge-induced subgraph of `G`.
428 Changes to `G` are reflected in the view.
430 Notes
431 -----
432 To create a mutable subgraph with its own copies of nodes
433 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
435 If you create a subgraph of a subgraph recursively you can end up
436 with a chain of subgraphs that becomes very slow with about 15
437 nested subgraph views. Luckily the edge_subgraph filter nests
438 nicely so you can use the original graph as G in this function
439 to avoid chains. We do not rule out chains programmatically so
440 that odd cases like an `edge_subgraph` of a `restricted_view`
441 can be created.
443 Examples
444 --------
445 >>> G = nx.path_graph(5)
446 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
447 >>> list(H.nodes)
448 [0, 1, 3, 4]
449 >>> list(H.edges)
450 [(0, 1), (3, 4)]
452 For multi graphs, `edges` must include the edge keys:
454 >>> G = nx.MultiGraph(G)
455 >>> H = nx.edge_subgraph(G, [(0, 1, 0), (3, 4, 0)])
456 >>> list(H.edges)
457 [(0, 1, 0), (3, 4, 0)]
459 Edge attributes can be used to filter multiedges:
461 >>> G.add_edge(0, 1, color="blue")
462 1
463 >>> G.add_edge(0, 1, color="green", weight=10)
464 2
465 >>> H = nx.edge_subgraph(
466 ... G,
467 ... (
468 ... (u, v, k)
469 ... for u, v, k, clr in G.edges(keys=True, data="color")
470 ... if clr == "green"
471 ... ),
472 ... )
473 >>> H.edges(keys=True, data=True)
474 MultiEdgeDataView([(0, 1, 2, {'color': 'green', 'weight': 10})])
477 """
478 nxf = nx.filters
479 edges = set(edges)
480 nodes = set()
481 for e in edges:
482 nodes.update(e[:2])
483 induced_nodes = nxf.show_nodes(nodes)
484 if G.is_multigraph():
485 if G.is_directed():
486 induced_edges = nxf.show_multidiedges(edges)
487 else:
488 induced_edges = nxf.show_multiedges(edges)
489 else:
490 if G.is_directed():
491 induced_edges = nxf.show_diedges(edges)
492 else:
493 induced_edges = nxf.show_edges(edges)
494 return nx.subgraph_view(G, filter_node=induced_nodes, filter_edge=induced_edges)
497def restricted_view(G, nodes, edges):
498 """Returns a view of `G` with hidden nodes and edges.
500 The resulting subgraph filters out node `nodes` and edges `edges`.
501 Filtered out nodes also filter out any of their edges.
503 Parameters
504 ----------
505 G : NetworkX Graph
506 nodes : iterable
507 An iterable of nodes. Nodes not present in `G` are ignored.
508 edges : iterable
509 An iterable of edges. Edges not present in `G` are ignored.
511 Returns
512 -------
513 subgraph : SubGraph View
514 A read-only restricted view of `G` filtering out nodes and edges.
515 Changes to `G` are reflected in the view.
517 Notes
518 -----
519 To create a mutable subgraph with its own copies of nodes
520 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
522 If you create a subgraph of a subgraph recursively you may end up
523 with a chain of subgraph views. Such chains can get quite slow
524 for lengths near 15. To avoid long chains, try to make your subgraph
525 based on the original graph. We do not rule out chains programmatically
526 so that odd cases like an `edge_subgraph` of a `restricted_view`
527 can be created.
529 Examples
530 --------
531 >>> G = nx.path_graph(5)
532 >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)])
533 >>> list(H.nodes)
534 [1, 2, 3, 4]
535 >>> list(H.edges)
536 [(2, 3)]
537 """
538 nxf = nx.filters
539 hide_nodes = nxf.hide_nodes(nodes)
540 if G.is_multigraph():
541 if G.is_directed():
542 hide_edges = nxf.hide_multidiedges(edges)
543 else:
544 hide_edges = nxf.hide_multiedges(edges)
545 else:
546 if G.is_directed():
547 hide_edges = nxf.hide_diedges(edges)
548 else:
549 hide_edges = nxf.hide_edges(edges)
550 return nx.subgraph_view(G, filter_node=hide_nodes, filter_edge=hide_edges)
553def to_directed(graph):
554 """Returns a directed view of the graph `graph`.
556 Identical to graph.to_directed(as_view=True)
557 Note that graph.to_directed defaults to `as_view=False`
558 while this function always provides a view.
559 """
560 return graph.to_directed(as_view=True)
563def to_undirected(graph):
564 """Returns an undirected view of the graph `graph`.
566 Identical to graph.to_undirected(as_view=True)
567 Note that graph.to_undirected defaults to `as_view=False`
568 while this function always provides a view.
569 """
570 return graph.to_undirected(as_view=True)
573def create_empty_copy(G, with_data=True):
574 """Returns a copy of the graph G with all of the edges removed.
576 Parameters
577 ----------
578 G : graph
579 A NetworkX graph
581 with_data : bool (default=True)
582 Propagate Graph and Nodes data to the new graph.
584 See Also
585 --------
586 empty_graph
588 """
589 H = G.__class__()
590 H.add_nodes_from(G.nodes(data=with_data))
591 if with_data:
592 H.graph.update(G.graph)
593 return H
596@nx._dispatchable(preserve_node_attrs=True, mutates_input=True)
597def set_node_attributes(G, values, name=None):
598 """Sets node attributes from a given value or dictionary of values.
600 .. Warning:: The call order of arguments `values` and `name`
601 switched between v1.x & v2.x.
603 Parameters
604 ----------
605 G : NetworkX Graph
607 values : scalar value, dict-like
608 What the node attribute should be set to. If `values` is
609 not a dictionary, then it is treated as a single attribute value
610 that is then applied to every node in `G`. This means that if
611 you provide a mutable object, like a list, updates to that object
612 will be reflected in the node attribute for every node.
613 The attribute name will be `name`.
615 If `values` is a dict or a dict of dict, it should be keyed
616 by node to either an attribute value or a dict of attribute key/value
617 pairs used to update the node's attributes.
619 name : string (optional, default=None)
620 Name of the node attribute to set if values is a scalar.
622 Examples
623 --------
624 After computing some property of the nodes of a graph, you may want
625 to assign a node attribute to store the value of that property for
626 each node::
628 >>> G = nx.path_graph(3)
629 >>> bb = nx.betweenness_centrality(G)
630 >>> isinstance(bb, dict)
631 True
632 >>> nx.set_node_attributes(G, bb, "betweenness")
633 >>> G.nodes[1]["betweenness"]
634 1.0
636 If you provide a list as the second argument, updates to the list
637 will be reflected in the node attribute for each node::
639 >>> G = nx.path_graph(3)
640 >>> labels = []
641 >>> nx.set_node_attributes(G, labels, "labels")
642 >>> labels.append("foo")
643 >>> G.nodes[0]["labels"]
644 ['foo']
645 >>> G.nodes[1]["labels"]
646 ['foo']
647 >>> G.nodes[2]["labels"]
648 ['foo']
650 If you provide a dictionary of dictionaries as the second argument,
651 the outer dictionary is assumed to be keyed by node to an inner
652 dictionary of node attributes for that node::
654 >>> G = nx.path_graph(3)
655 >>> attrs = {0: {"attr1": 20, "attr2": "nothing"}, 1: {"attr2": 3}}
656 >>> nx.set_node_attributes(G, attrs)
657 >>> G.nodes[0]["attr1"]
658 20
659 >>> G.nodes[0]["attr2"]
660 'nothing'
661 >>> G.nodes[1]["attr2"]
662 3
663 >>> G.nodes[2]
664 {}
666 Note that if the dictionary contains nodes that are not in `G`, the
667 values are silently ignored::
669 >>> G = nx.Graph()
670 >>> G.add_node(0)
671 >>> nx.set_node_attributes(G, {0: "red", 1: "blue"}, name="color")
672 >>> G.nodes[0]["color"]
673 'red'
674 >>> 1 in G.nodes
675 False
677 """
678 # Set node attributes based on type of `values`
679 if name is not None: # `values` must not be a dict of dict
680 try: # `values` is a dict
681 for n, v in values.items():
682 try:
683 G.nodes[n][name] = values[n]
684 except KeyError:
685 pass
686 except AttributeError: # `values` is a constant
687 for n in G:
688 G.nodes[n][name] = values
689 else: # `values` must be dict of dict
690 for n, d in values.items():
691 try:
692 G.nodes[n].update(d)
693 except KeyError:
694 pass
695 nx._clear_cache(G)
698@nx._dispatchable(node_attrs={"name": "default"})
699def get_node_attributes(G, name, default=None):
700 """Get node attributes from graph
702 Parameters
703 ----------
704 G : NetworkX Graph
706 name : string
707 Attribute name
709 default: object (default=None)
710 Default value of the node attribute if there is no value set for that
711 node in graph. If `None` then nodes without this attribute are not
712 included in the returned dict.
714 Returns
715 -------
716 Dictionary of attributes keyed by node.
718 Examples
719 --------
720 >>> G = nx.Graph()
721 >>> G.add_nodes_from([1, 2, 3], color="red")
722 >>> color = nx.get_node_attributes(G, "color")
723 >>> color[1]
724 'red'
725 >>> G.add_node(4)
726 >>> color = nx.get_node_attributes(G, "color", default="yellow")
727 >>> color[4]
728 'yellow'
729 """
730 if default is not None:
731 return {n: d.get(name, default) for n, d in G.nodes.items()}
732 return {n: d[name] for n, d in G.nodes.items() if name in d}
735@nx._dispatchable(preserve_node_attrs=True, mutates_input=True)
736def remove_node_attributes(G, *attr_names, nbunch=None):
737 """Remove node attributes from all nodes in the graph.
739 Parameters
740 ----------
741 G : NetworkX Graph
743 *attr_names : List of Strings
744 The attribute names to remove from the graph.
746 nbunch : List of Nodes
747 Remove the node attributes only from the nodes in this list.
749 Examples
750 --------
751 >>> G = nx.Graph()
752 >>> G.add_nodes_from([1, 2, 3], color="blue")
753 >>> nx.get_node_attributes(G, "color")
754 {1: 'blue', 2: 'blue', 3: 'blue'}
755 >>> nx.remove_node_attributes(G, "color")
756 >>> nx.get_node_attributes(G, "color")
757 {}
758 """
760 if nbunch is None:
761 nbunch = G.nodes()
763 for attr in attr_names:
764 for n, d in G.nodes(data=True):
765 if n in nbunch:
766 try:
767 del d[attr]
768 except KeyError:
769 pass
772@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True)
773def set_edge_attributes(G, values, name=None):
774 """Sets edge attributes from a given value or dictionary of values.
776 .. Warning:: The call order of arguments `values` and `name`
777 switched between v1.x & v2.x.
779 Parameters
780 ----------
781 G : NetworkX Graph
783 values : scalar value, dict-like
784 What the edge attribute should be set to. If `values` is
785 not a dictionary, then it is treated as a single attribute value
786 that is then applied to every edge in `G`. This means that if
787 you provide a mutable object, like a list, updates to that object
788 will be reflected in the edge attribute for each edge. The attribute
789 name will be `name`.
791 If `values` is a dict or a dict of dict, it should be keyed
792 by edge tuple to either an attribute value or a dict of attribute
793 key/value pairs used to update the edge's attributes.
794 For multigraphs, the edge tuples must be of the form ``(u, v, key)``,
795 where `u` and `v` are nodes and `key` is the edge key.
796 For non-multigraphs, the keys must be tuples of the form ``(u, v)``.
798 name : string (optional, default=None)
799 Name of the edge attribute to set if values is a scalar.
801 Examples
802 --------
803 After computing some property of the edges of a graph, you may want
804 to assign a edge attribute to store the value of that property for
805 each edge::
807 >>> G = nx.path_graph(3)
808 >>> bb = nx.edge_betweenness_centrality(G, normalized=False)
809 >>> nx.set_edge_attributes(G, bb, "betweenness")
810 >>> G.edges[1, 2]["betweenness"]
811 2.0
813 If you provide a list as the second argument, updates to the list
814 will be reflected in the edge attribute for each edge::
816 >>> labels = []
817 >>> nx.set_edge_attributes(G, labels, "labels")
818 >>> labels.append("foo")
819 >>> G.edges[0, 1]["labels"]
820 ['foo']
821 >>> G.edges[1, 2]["labels"]
822 ['foo']
824 If you provide a dictionary of dictionaries as the second argument,
825 the entire dictionary will be used to update edge attributes::
827 >>> G = nx.path_graph(3)
828 >>> attrs = {(0, 1): {"attr1": 20, "attr2": "nothing"}, (1, 2): {"attr2": 3}}
829 >>> nx.set_edge_attributes(G, attrs)
830 >>> G[0][1]["attr1"]
831 20
832 >>> G[0][1]["attr2"]
833 'nothing'
834 >>> G[1][2]["attr2"]
835 3
837 The attributes of one Graph can be used to set those of another.
839 >>> H = nx.path_graph(3)
840 >>> nx.set_edge_attributes(H, G.edges)
842 Note that if the dict contains edges that are not in `G`, they are
843 silently ignored::
845 >>> G = nx.Graph([(0, 1)])
846 >>> nx.set_edge_attributes(G, {(1, 2): {"weight": 2.0}})
847 >>> (1, 2) in G.edges()
848 False
850 For multigraphs, the `values` dict is expected to be keyed by 3-tuples
851 including the edge key::
853 >>> MG = nx.MultiGraph()
854 >>> edges = [(0, 1), (0, 1)]
855 >>> MG.add_edges_from(edges) # Returns list of edge keys
856 [0, 1]
857 >>> attributes = {(0, 1, 0): {"cost": 21}, (0, 1, 1): {"cost": 7}}
858 >>> nx.set_edge_attributes(MG, attributes)
859 >>> MG[0][1][0]["cost"]
860 21
861 >>> MG[0][1][1]["cost"]
862 7
864 If MultiGraph attributes are desired for a Graph, you must convert the 3-tuple
865 multiedge to a 2-tuple edge and the last multiedge's attribute value will
866 overwrite the previous values. Continuing from the previous case we get::
868 >>> H = nx.path_graph([0, 1, 2])
869 >>> nx.set_edge_attributes(H, {(u, v): ed for u, v, ed in MG.edges.data()})
870 >>> nx.get_edge_attributes(H, "cost")
871 {(0, 1): 7}
873 """
874 if name is not None:
875 # `values` does not contain attribute names
876 try:
877 # if `values` is a dict using `.items()` => {edge: value}
878 if G.is_multigraph():
879 for (u, v, key), value in values.items():
880 try:
881 G._adj[u][v][key][name] = value
882 except KeyError:
883 pass
884 else:
885 for (u, v), value in values.items():
886 try:
887 G._adj[u][v][name] = value
888 except KeyError:
889 pass
890 except AttributeError:
891 # treat `values` as a constant
892 for u, v, data in G.edges(data=True):
893 data[name] = values
894 else:
895 # `values` consists of doct-of-dict {edge: {attr: value}} shape
896 if G.is_multigraph():
897 for (u, v, key), d in values.items():
898 try:
899 G._adj[u][v][key].update(d)
900 except KeyError:
901 pass
902 else:
903 for (u, v), d in values.items():
904 try:
905 G._adj[u][v].update(d)
906 except KeyError:
907 pass
908 nx._clear_cache(G)
911@nx._dispatchable(edge_attrs={"name": "default"})
912def get_edge_attributes(G, name, default=None):
913 """Get edge attributes from graph
915 Parameters
916 ----------
917 G : NetworkX Graph
919 name : string
920 Attribute name
922 default: object (default=None)
923 Default value of the edge attribute if there is no value set for that
924 edge in graph. If `None` then edges without this attribute are not
925 included in the returned dict.
927 Returns
928 -------
929 Dictionary of attributes keyed by edge. For (di)graphs, the keys are
930 2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of
931 the form: (u, v, key).
933 Examples
934 --------
935 >>> G = nx.Graph()
936 >>> nx.add_path(G, [1, 2, 3], color="red")
937 >>> color = nx.get_edge_attributes(G, "color")
938 >>> color[(1, 2)]
939 'red'
940 >>> G.add_edge(3, 4)
941 >>> color = nx.get_edge_attributes(G, "color", default="yellow")
942 >>> color[(3, 4)]
943 'yellow'
944 """
945 if G.is_multigraph():
946 edges = G.edges(keys=True, data=True)
947 else:
948 edges = G.edges(data=True)
949 if default is not None:
950 return {x[:-1]: x[-1].get(name, default) for x in edges}
951 return {x[:-1]: x[-1][name] for x in edges if name in x[-1]}
954@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True)
955def remove_edge_attributes(G, *attr_names, ebunch=None):
956 """Remove edge attributes from all edges in the graph.
958 Parameters
959 ----------
960 G : NetworkX Graph
962 *attr_names : List of Strings
963 The attribute names to remove from the graph.
965 Examples
966 --------
967 >>> G = nx.path_graph(3)
968 >>> nx.set_edge_attributes(G, {(u, v): u + v for u, v in G.edges()}, name="weight")
969 >>> nx.get_edge_attributes(G, "weight")
970 {(0, 1): 1, (1, 2): 3}
971 >>> remove_edge_attributes(G, "weight")
972 >>> nx.get_edge_attributes(G, "weight")
973 {}
974 """
975 if ebunch is None:
976 ebunch = G.edges(keys=True) if G.is_multigraph() else G.edges()
978 for attr in attr_names:
979 edges = (
980 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
981 )
982 for *e, d in edges:
983 if tuple(e) in ebunch:
984 try:
985 del d[attr]
986 except KeyError:
987 pass
990def all_neighbors(graph, node):
991 """Returns all of the neighbors of a node in the graph.
993 If the graph is directed returns predecessors as well as successors.
995 Parameters
996 ----------
997 graph : NetworkX graph
998 Graph to find neighbors.
999 node : node
1000 The node whose neighbors will be returned.
1002 Returns
1003 -------
1004 neighbors : iterator
1005 Iterator of neighbors
1007 Raises
1008 ------
1009 NetworkXError
1010 If `node` is not in the graph.
1012 Examples
1013 --------
1014 For undirected graphs, this function is equivalent to ``G.neighbors(node)``.
1016 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1017 >>> list(nx.all_neighbors(G, 1))
1018 [0, 2]
1020 For directed graphs, this function returns both predecessors and successors,
1021 which may include duplicates if a node is both a predecessor and successor
1022 (e.g., in bidirectional edges or self-loops).
1024 >>> DG = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
1025 >>> list(nx.all_neighbors(DG, 1))
1026 [0, 2, 2]
1028 Notes
1029 -----
1030 This function iterates over all neighbors (both predecessors and successors).
1032 See Also
1033 --------
1034 Graph.neighbors : Returns successors for both Graph and DiGraph
1035 DiGraph.predecessors : Returns predecessors for directed graphs only
1036 DiGraph.successors : Returns successors for directed graphs only
1037 """
1038 if graph.is_directed():
1039 values = chain(graph.predecessors(node), graph.successors(node))
1040 else:
1041 values = graph.neighbors(node)
1042 return values
1045def non_neighbors(graph, node):
1046 """Returns the non-neighbors of the node in the graph.
1048 Parameters
1049 ----------
1050 graph : NetworkX graph
1051 Graph to find neighbors.
1053 node : node
1054 The node whose neighbors will be returned.
1056 Returns
1057 -------
1058 non_neighbors : set
1059 Set of nodes in the graph that are not neighbors of the node.
1060 """
1061 return graph._adj.keys() - graph._adj[node].keys() - {node}
1064def non_edges(graph):
1065 """Returns the nonexistent edges in the graph.
1067 Parameters
1068 ----------
1069 graph : NetworkX graph.
1070 Graph to find nonexistent edges.
1072 Returns
1073 -------
1074 non_edges : iterator
1075 Iterator of edges that are not in the graph.
1076 """
1077 if graph.is_directed():
1078 for u in graph:
1079 for v in non_neighbors(graph, u):
1080 yield (u, v)
1081 else:
1082 nodes = set(graph)
1083 while nodes:
1084 u = nodes.pop()
1085 for v in nodes - set(graph[u]):
1086 yield (u, v)
1089@not_implemented_for("directed")
1090def common_neighbors(G, u, v):
1091 """Returns the common neighbors of two nodes in a graph.
1093 Parameters
1094 ----------
1095 G : graph
1096 A NetworkX undirected graph.
1098 u, v : nodes
1099 Nodes in the graph.
1101 Returns
1102 -------
1103 cnbors : set
1104 Set of common neighbors of u and v in the graph.
1106 Raises
1107 ------
1108 NetworkXError
1109 If u or v is not a node in the graph.
1111 Examples
1112 --------
1113 >>> G = nx.complete_graph(5)
1114 >>> sorted(nx.common_neighbors(G, 0, 1))
1115 [2, 3, 4]
1116 """
1117 if u not in G:
1118 raise nx.NetworkXError("u is not in the graph.")
1119 if v not in G:
1120 raise nx.NetworkXError("v is not in the graph.")
1122 return G._adj[u].keys() & G._adj[v].keys() - {u, v}
1125@nx._dispatchable(preserve_edge_attrs=True)
1126def is_weighted(G, edge=None, weight="weight"):
1127 """Returns True if `G` has weighted edges.
1129 Parameters
1130 ----------
1131 G : graph
1132 A NetworkX graph.
1134 edge : tuple, optional
1135 A 2-tuple specifying the only edge in `G` that will be tested. If
1136 None, then every edge in `G` is tested.
1138 weight: string, optional
1139 The attribute name used to query for edge weights.
1141 Returns
1142 -------
1143 bool
1144 A boolean signifying if `G`, or the specified edge, is weighted.
1146 Raises
1147 ------
1148 NetworkXError
1149 If the specified edge does not exist.
1151 Examples
1152 --------
1153 >>> G = nx.path_graph(4)
1154 >>> nx.is_weighted(G)
1155 False
1156 >>> nx.is_weighted(G, (2, 3))
1157 False
1159 >>> G = nx.DiGraph()
1160 >>> G.add_edge(1, 2, weight=1)
1161 >>> nx.is_weighted(G)
1162 True
1164 """
1165 if edge is not None:
1166 data = G.get_edge_data(*edge)
1167 if data is None:
1168 msg = f"Edge {edge!r} does not exist."
1169 raise nx.NetworkXError(msg)
1170 return weight in data
1172 if is_empty(G):
1173 # Special handling required since: all([]) == True
1174 return False
1176 return all(weight in data for u, v, data in G.edges(data=True))
1179@nx._dispatchable(edge_attrs="weight")
1180def is_negatively_weighted(G, edge=None, weight="weight"):
1181 """Returns True if `G` has negatively weighted edges.
1183 Parameters
1184 ----------
1185 G : graph
1186 A NetworkX graph.
1188 edge : tuple, optional
1189 A 2-tuple specifying the only edge in `G` that will be tested. If
1190 None, then every edge in `G` is tested.
1192 weight: string, optional
1193 The attribute name used to query for edge weights.
1195 Returns
1196 -------
1197 bool
1198 A boolean signifying if `G`, or the specified edge, is negatively
1199 weighted.
1201 Raises
1202 ------
1203 NetworkXError
1204 If the specified edge does not exist.
1206 Examples
1207 --------
1208 >>> G = nx.Graph()
1209 >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)])
1210 >>> G.add_edge(1, 2, weight=4)
1211 >>> nx.is_negatively_weighted(G, (1, 2))
1212 False
1213 >>> G[2][4]["weight"] = -2
1214 >>> nx.is_negatively_weighted(G)
1215 True
1216 >>> G = nx.DiGraph()
1217 >>> edges = [("0", "3", 3), ("0", "1", -5), ("1", "0", -2)]
1218 >>> G.add_weighted_edges_from(edges)
1219 >>> nx.is_negatively_weighted(G)
1220 True
1222 """
1223 if edge is not None:
1224 data = G.get_edge_data(*edge)
1225 if data is None:
1226 msg = f"Edge {edge!r} does not exist."
1227 raise nx.NetworkXError(msg)
1228 return weight in data and data[weight] < 0
1230 return any(weight in data and data[weight] < 0 for u, v, data in G.edges(data=True))
1233@nx._dispatchable
1234def is_empty(G):
1235 """Returns True if `G` has no edges.
1237 Parameters
1238 ----------
1239 G : graph
1240 A NetworkX graph.
1242 Returns
1243 -------
1244 bool
1245 True if `G` has no edges, and False otherwise.
1247 Notes
1248 -----
1249 An empty graph can have nodes but not edges. The empty graph with zero
1250 nodes is known as the null graph. This is an $O(n)$ operation where n
1251 is the number of nodes in the graph.
1253 """
1254 return not any(G._adj.values())
1257def nodes_with_selfloops(G):
1258 """Returns an iterator over nodes with self loops.
1260 A node with a self loop has an edge with both ends adjacent
1261 to that node.
1263 Returns
1264 -------
1265 nodelist : iterator
1266 A iterator over nodes with self loops.
1268 See Also
1269 --------
1270 selfloop_edges, number_of_selfloops
1272 Examples
1273 --------
1274 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1275 >>> G.add_edge(1, 1)
1276 >>> G.add_edge(1, 2)
1277 >>> list(nx.nodes_with_selfloops(G))
1278 [1]
1280 """
1281 return (n for n, nbrs in G._adj.items() if n in nbrs)
1284def selfloop_edges(G, data=False, keys=False, default=None):
1285 """Returns an iterator over selfloop edges.
1287 A selfloop edge has the same node at both ends.
1289 Parameters
1290 ----------
1291 G : graph
1292 A NetworkX graph.
1293 data : string or bool, optional (default=False)
1294 Return selfloop edges as two tuples (u, v) (data=False)
1295 or three-tuples (u, v, datadict) (data=True)
1296 or three-tuples (u, v, datavalue) (data='attrname')
1297 keys : bool, optional (default=False)
1298 If True, return edge keys with each edge.
1299 default : value, optional (default=None)
1300 Value used for edges that don't have the requested attribute.
1301 Only relevant if data is not True or False.
1303 Returns
1304 -------
1305 edgeiter : iterator over edge tuples
1306 An iterator over all selfloop edges.
1308 See Also
1309 --------
1310 nodes_with_selfloops, number_of_selfloops
1312 Examples
1313 --------
1314 >>> G = nx.MultiGraph() # or Graph, DiGraph, MultiDiGraph, etc
1315 >>> ekey = G.add_edge(1, 1)
1316 >>> ekey = G.add_edge(1, 2)
1317 >>> list(nx.selfloop_edges(G))
1318 [(1, 1)]
1319 >>> list(nx.selfloop_edges(G, data=True))
1320 [(1, 1, {})]
1321 >>> list(nx.selfloop_edges(G, keys=True))
1322 [(1, 1, 0)]
1323 >>> list(nx.selfloop_edges(G, keys=True, data=True))
1324 [(1, 1, 0, {})]
1325 """
1326 if data is True:
1327 if G.is_multigraph():
1328 if keys is True:
1329 return (
1330 (n, n, k, d)
1331 for n, nbrs in G._adj.items()
1332 if n in nbrs
1333 for k, d in nbrs[n].items()
1334 )
1335 else:
1336 return (
1337 (n, n, d)
1338 for n, nbrs in G._adj.items()
1339 if n in nbrs
1340 for d in nbrs[n].values()
1341 )
1342 else:
1343 return ((n, n, nbrs[n]) for n, nbrs in G._adj.items() if n in nbrs)
1344 elif data is not False:
1345 if G.is_multigraph():
1346 if keys is True:
1347 return (
1348 (n, n, k, d.get(data, default))
1349 for n, nbrs in G._adj.items()
1350 if n in nbrs
1351 for k, d in nbrs[n].items()
1352 )
1353 else:
1354 return (
1355 (n, n, d.get(data, default))
1356 for n, nbrs in G._adj.items()
1357 if n in nbrs
1358 for d in nbrs[n].values()
1359 )
1360 else:
1361 return (
1362 (n, n, nbrs[n].get(data, default))
1363 for n, nbrs in G._adj.items()
1364 if n in nbrs
1365 )
1366 else:
1367 if G.is_multigraph():
1368 if keys is True:
1369 return (
1370 (n, n, k)
1371 for n, nbrs in G._adj.items()
1372 if n in nbrs
1373 for k in nbrs[n]
1374 )
1375 else:
1376 return (
1377 (n, n)
1378 for n, nbrs in G._adj.items()
1379 if n in nbrs
1380 for i in range(len(nbrs[n])) # for easy edge removal (#4068)
1381 )
1382 else:
1383 return ((n, n) for n, nbrs in G._adj.items() if n in nbrs)
1386@nx._dispatchable
1387def number_of_selfloops(G):
1388 """Returns the number of selfloop edges.
1390 A selfloop edge has the same node at both ends.
1392 Returns
1393 -------
1394 nloops : int
1395 The number of selfloops.
1397 See Also
1398 --------
1399 nodes_with_selfloops, selfloop_edges
1401 Examples
1402 --------
1403 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1404 >>> G.add_edge(1, 1)
1405 >>> G.add_edge(1, 2)
1406 >>> nx.number_of_selfloops(G)
1407 1
1408 """
1409 return sum(1 for _ in nx.selfloop_edges(G))
1412def is_path(G, path):
1413 """Returns whether or not the specified path exists.
1415 For it to return True, every node on the path must exist and
1416 each consecutive pair must be connected via one or more edges.
1418 Parameters
1419 ----------
1420 G : graph
1421 A NetworkX graph.
1423 path : list
1424 A list of nodes which defines the path to traverse
1426 Returns
1427 -------
1428 bool
1429 True if `path` is a valid path in `G`
1431 """
1432 try:
1433 return all(nbr in G._adj[node] for node, nbr in nx.utils.pairwise(path))
1434 except (KeyError, TypeError):
1435 return False
1438def path_weight(G, path, weight):
1439 """Returns total cost associated with specified path and weight
1441 Parameters
1442 ----------
1443 G : graph
1444 A NetworkX graph.
1446 path: list
1447 A list of node labels which defines the path to traverse
1449 weight: string
1450 A string indicating which edge attribute to use for path cost
1452 Returns
1453 -------
1454 cost: int or float
1455 An integer or a float representing the total cost with respect to the
1456 specified weight of the specified path
1458 Raises
1459 ------
1460 NetworkXNoPath
1461 If the specified edge does not exist.
1462 """
1463 multigraph = G.is_multigraph()
1464 cost = 0
1466 if not nx.is_path(G, path):
1467 raise nx.NetworkXNoPath("path does not exist")
1468 for node, nbr in nx.utils.pairwise(path):
1469 if multigraph:
1470 cost += min(v[weight] for v in G._adj[node][nbr].values())
1471 else:
1472 cost += G._adj[node][nbr][weight]
1473 return cost
1476def describe(G, describe_hook=None):
1477 """Prints a description of the graph G.
1479 By default, the description includes some basic properties of the graph.
1480 You can also provide additional functions to compute and include
1481 more properties in the description.
1483 Parameters
1484 ----------
1485 G : graph
1486 A NetworkX graph.
1488 describe_hook: callable, optional (default=None)
1489 A function that takes a graph as input and returns a
1490 dictionary of additional properties to include in the description.
1491 The keys of the dictionary are the property names, and the values
1492 are the corresponding property values.
1494 Examples
1495 --------
1496 >>> G = nx.path_graph(5)
1497 >>> nx.describe(G)
1498 Number of nodes : 5
1499 Number of edges : 4
1500 Directed : False
1501 Multigraph : False
1502 Tree : True
1503 Bipartite : True
1504 Average degree (min, max) : 1.60 (1, 2)
1505 Number of connected components : 1
1507 >>> def augment_description(G):
1508 ... return {"Average Shortest Path Length": nx.average_shortest_path_length(G)}
1509 >>> nx.describe(G, describe_hook=augment_description)
1510 Number of nodes : 5
1511 Number of edges : 4
1512 Directed : False
1513 Multigraph : False
1514 Tree : True
1515 Bipartite : True
1516 Average degree (min, max) : 1.60 (1, 2)
1517 Number of connected components : 1
1518 Average Shortest Path Length : 2.0
1520 >>> G.name = "Path Graph of 5 nodes"
1521 >>> nx.describe(G)
1522 Name of Graph : Path Graph of 5 nodes
1523 Number of nodes : 5
1524 Number of edges : 4
1525 Directed : False
1526 Multigraph : False
1527 Tree : True
1528 Bipartite : True
1529 Average degree (min, max) : 1.60 (1, 2)
1530 Number of connected components : 1
1532 """
1533 info_dict = _create_describe_info_dict(G)
1535 if describe_hook is not None:
1536 additional_info = describe_hook(G)
1537 info_dict.update(additional_info)
1539 max_key_len = max(len(k) for k in info_dict)
1540 for key, val in info_dict.items():
1541 print(f"{key:<{max_key_len}} : {val}")
1544def _create_describe_info_dict(G):
1545 info = {}
1546 if G.name != "":
1547 info["Name of Graph"] = G.name
1548 info.update(
1549 {
1550 "Number of nodes": len(G),
1551 "Number of edges": G.number_of_edges(),
1552 "Directed": G.is_directed(),
1553 "Multigraph": G.is_multigraph(),
1554 "Tree": nx.is_tree(G),
1555 "Bipartite": nx.is_bipartite(G),
1556 }
1557 )
1558 if len(G) == 0:
1559 return info
1561 degree_values = dict(nx.degree(G)).values()
1562 avg_degree = sum(degree_values) / len(G)
1563 max_degree, min_degree = max(degree_values), min(degree_values)
1564 info["Average degree (min, max)"] = f"{avg_degree:.2f} ({min_degree}, {max_degree})"
1566 if G.is_directed():
1567 info["Number of strongly connected components"] = (
1568 nx.number_strongly_connected_components(G)
1569 )
1570 info["Number of weakly connected components"] = (
1571 nx.number_weakly_connected_components(G)
1572 )
1573 else:
1574 info["Number of connected components"] = nx.number_connected_components(G)
1575 return info