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)]
451 """
452 nxf = nx.filters
453 edges = set(edges)
454 nodes = set()
455 for e in edges:
456 nodes.update(e[:2])
457 induced_nodes = nxf.show_nodes(nodes)
458 if G.is_multigraph():
459 if G.is_directed():
460 induced_edges = nxf.show_multidiedges(edges)
461 else:
462 induced_edges = nxf.show_multiedges(edges)
463 else:
464 if G.is_directed():
465 induced_edges = nxf.show_diedges(edges)
466 else:
467 induced_edges = nxf.show_edges(edges)
468 return nx.subgraph_view(G, filter_node=induced_nodes, filter_edge=induced_edges)
471def restricted_view(G, nodes, edges):
472 """Returns a view of `G` with hidden nodes and edges.
474 The resulting subgraph filters out node `nodes` and edges `edges`.
475 Filtered out nodes also filter out any of their edges.
477 Parameters
478 ----------
479 G : NetworkX Graph
480 nodes : iterable
481 An iterable of nodes. Nodes not present in `G` are ignored.
482 edges : iterable
483 An iterable of edges. Edges not present in `G` are ignored.
485 Returns
486 -------
487 subgraph : SubGraph View
488 A read-only restricted view of `G` filtering out nodes and edges.
489 Changes to `G` are reflected in the view.
491 Notes
492 -----
493 To create a mutable subgraph with its own copies of nodes
494 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
496 If you create a subgraph of a subgraph recursively you may end up
497 with a chain of subgraph views. Such chains can get quite slow
498 for lengths near 15. To avoid long chains, try to make your subgraph
499 based on the original graph. We do not rule out chains programmatically
500 so that odd cases like an `edge_subgraph` of a `restricted_view`
501 can be created.
503 Examples
504 --------
505 >>> G = nx.path_graph(5)
506 >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)])
507 >>> list(H.nodes)
508 [1, 2, 3, 4]
509 >>> list(H.edges)
510 [(2, 3)]
511 """
512 nxf = nx.filters
513 hide_nodes = nxf.hide_nodes(nodes)
514 if G.is_multigraph():
515 if G.is_directed():
516 hide_edges = nxf.hide_multidiedges(edges)
517 else:
518 hide_edges = nxf.hide_multiedges(edges)
519 else:
520 if G.is_directed():
521 hide_edges = nxf.hide_diedges(edges)
522 else:
523 hide_edges = nxf.hide_edges(edges)
524 return nx.subgraph_view(G, filter_node=hide_nodes, filter_edge=hide_edges)
527def to_directed(graph):
528 """Returns a directed view of the graph `graph`.
530 Identical to graph.to_directed(as_view=True)
531 Note that graph.to_directed defaults to `as_view=False`
532 while this function always provides a view.
533 """
534 return graph.to_directed(as_view=True)
537def to_undirected(graph):
538 """Returns an undirected view of the graph `graph`.
540 Identical to graph.to_undirected(as_view=True)
541 Note that graph.to_undirected defaults to `as_view=False`
542 while this function always provides a view.
543 """
544 return graph.to_undirected(as_view=True)
547def create_empty_copy(G, with_data=True):
548 """Returns a copy of the graph G with all of the edges removed.
550 Parameters
551 ----------
552 G : graph
553 A NetworkX graph
555 with_data : bool (default=True)
556 Propagate Graph and Nodes data to the new graph.
558 See Also
559 --------
560 empty_graph
562 """
563 H = G.__class__()
564 H.add_nodes_from(G.nodes(data=with_data))
565 if with_data:
566 H.graph.update(G.graph)
567 return H
570@nx._dispatchable(preserve_node_attrs=True, mutates_input=True)
571def set_node_attributes(G, values, name=None):
572 """Sets node attributes from a given value or dictionary of values.
574 .. Warning:: The call order of arguments `values` and `name`
575 switched between v1.x & v2.x.
577 Parameters
578 ----------
579 G : NetworkX Graph
581 values : scalar value, dict-like
582 What the node attribute should be set to. If `values` is
583 not a dictionary, then it is treated as a single attribute value
584 that is then applied to every node in `G`. This means that if
585 you provide a mutable object, like a list, updates to that object
586 will be reflected in the node attribute for every node.
587 The attribute name will be `name`.
589 If `values` is a dict or a dict of dict, it should be keyed
590 by node to either an attribute value or a dict of attribute key/value
591 pairs used to update the node's attributes.
593 name : string (optional, default=None)
594 Name of the node attribute to set if values is a scalar.
596 Examples
597 --------
598 After computing some property of the nodes of a graph, you may want
599 to assign a node attribute to store the value of that property for
600 each node::
602 >>> G = nx.path_graph(3)
603 >>> bb = nx.betweenness_centrality(G)
604 >>> isinstance(bb, dict)
605 True
606 >>> nx.set_node_attributes(G, bb, "betweenness")
607 >>> G.nodes[1]["betweenness"]
608 1.0
610 If you provide a list as the second argument, updates to the list
611 will be reflected in the node attribute for each node::
613 >>> G = nx.path_graph(3)
614 >>> labels = []
615 >>> nx.set_node_attributes(G, labels, "labels")
616 >>> labels.append("foo")
617 >>> G.nodes[0]["labels"]
618 ['foo']
619 >>> G.nodes[1]["labels"]
620 ['foo']
621 >>> G.nodes[2]["labels"]
622 ['foo']
624 If you provide a dictionary of dictionaries as the second argument,
625 the outer dictionary is assumed to be keyed by node to an inner
626 dictionary of node attributes for that node::
628 >>> G = nx.path_graph(3)
629 >>> attrs = {0: {"attr1": 20, "attr2": "nothing"}, 1: {"attr2": 3}}
630 >>> nx.set_node_attributes(G, attrs)
631 >>> G.nodes[0]["attr1"]
632 20
633 >>> G.nodes[0]["attr2"]
634 'nothing'
635 >>> G.nodes[1]["attr2"]
636 3
637 >>> G.nodes[2]
638 {}
640 Note that if the dictionary contains nodes that are not in `G`, the
641 values are silently ignored::
643 >>> G = nx.Graph()
644 >>> G.add_node(0)
645 >>> nx.set_node_attributes(G, {0: "red", 1: "blue"}, name="color")
646 >>> G.nodes[0]["color"]
647 'red'
648 >>> 1 in G.nodes
649 False
651 """
652 # Set node attributes based on type of `values`
653 if name is not None: # `values` must not be a dict of dict
654 try: # `values` is a dict
655 for n, v in values.items():
656 try:
657 G.nodes[n][name] = values[n]
658 except KeyError:
659 pass
660 except AttributeError: # `values` is a constant
661 for n in G:
662 G.nodes[n][name] = values
663 else: # `values` must be dict of dict
664 for n, d in values.items():
665 try:
666 G.nodes[n].update(d)
667 except KeyError:
668 pass
669 nx._clear_cache(G)
672@nx._dispatchable(node_attrs={"name": "default"})
673def get_node_attributes(G, name, default=None):
674 """Get node attributes from graph
676 Parameters
677 ----------
678 G : NetworkX Graph
680 name : string
681 Attribute name
683 default: object (default=None)
684 Default value of the node attribute if there is no value set for that
685 node in graph. If `None` then nodes without this attribute are not
686 included in the returned dict.
688 Returns
689 -------
690 Dictionary of attributes keyed by node.
692 Examples
693 --------
694 >>> G = nx.Graph()
695 >>> G.add_nodes_from([1, 2, 3], color="red")
696 >>> color = nx.get_node_attributes(G, "color")
697 >>> color[1]
698 'red'
699 >>> G.add_node(4)
700 >>> color = nx.get_node_attributes(G, "color", default="yellow")
701 >>> color[4]
702 'yellow'
703 """
704 if default is not None:
705 return {n: d.get(name, default) for n, d in G.nodes.items()}
706 return {n: d[name] for n, d in G.nodes.items() if name in d}
709@nx._dispatchable(preserve_node_attrs=True, mutates_input=True)
710def remove_node_attributes(G, *attr_names, nbunch=None):
711 """Remove node attributes from all nodes in the graph.
713 Parameters
714 ----------
715 G : NetworkX Graph
717 *attr_names : List of Strings
718 The attribute names to remove from the graph.
720 nbunch : List of Nodes
721 Remove the node attributes only from the nodes in this list.
723 Examples
724 --------
725 >>> G = nx.Graph()
726 >>> G.add_nodes_from([1, 2, 3], color="blue")
727 >>> nx.get_node_attributes(G, "color")
728 {1: 'blue', 2: 'blue', 3: 'blue'}
729 >>> nx.remove_node_attributes(G, "color")
730 >>> nx.get_node_attributes(G, "color")
731 {}
732 """
734 if nbunch is None:
735 nbunch = G.nodes()
737 for attr in attr_names:
738 for n, d in G.nodes(data=True):
739 if n in nbunch:
740 try:
741 del d[attr]
742 except KeyError:
743 pass
746@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True)
747def set_edge_attributes(G, values, name=None):
748 """Sets edge attributes from a given value or dictionary of values.
750 .. Warning:: The call order of arguments `values` and `name`
751 switched between v1.x & v2.x.
753 Parameters
754 ----------
755 G : NetworkX Graph
757 values : scalar value, dict-like
758 What the edge attribute should be set to. If `values` is
759 not a dictionary, then it is treated as a single attribute value
760 that is then applied to every edge in `G`. This means that if
761 you provide a mutable object, like a list, updates to that object
762 will be reflected in the edge attribute for each edge. The attribute
763 name will be `name`.
765 If `values` is a dict or a dict of dict, it should be keyed
766 by edge tuple to either an attribute value or a dict of attribute
767 key/value pairs used to update the edge's attributes.
768 For multigraphs, the edge tuples must be of the form ``(u, v, key)``,
769 where `u` and `v` are nodes and `key` is the edge key.
770 For non-multigraphs, the keys must be tuples of the form ``(u, v)``.
772 name : string (optional, default=None)
773 Name of the edge attribute to set if values is a scalar.
775 Examples
776 --------
777 After computing some property of the edges of a graph, you may want
778 to assign a edge attribute to store the value of that property for
779 each edge::
781 >>> G = nx.path_graph(3)
782 >>> bb = nx.edge_betweenness_centrality(G, normalized=False)
783 >>> nx.set_edge_attributes(G, bb, "betweenness")
784 >>> G.edges[1, 2]["betweenness"]
785 2.0
787 If you provide a list as the second argument, updates to the list
788 will be reflected in the edge attribute for each edge::
790 >>> labels = []
791 >>> nx.set_edge_attributes(G, labels, "labels")
792 >>> labels.append("foo")
793 >>> G.edges[0, 1]["labels"]
794 ['foo']
795 >>> G.edges[1, 2]["labels"]
796 ['foo']
798 If you provide a dictionary of dictionaries as the second argument,
799 the entire dictionary will be used to update edge attributes::
801 >>> G = nx.path_graph(3)
802 >>> attrs = {(0, 1): {"attr1": 20, "attr2": "nothing"}, (1, 2): {"attr2": 3}}
803 >>> nx.set_edge_attributes(G, attrs)
804 >>> G[0][1]["attr1"]
805 20
806 >>> G[0][1]["attr2"]
807 'nothing'
808 >>> G[1][2]["attr2"]
809 3
811 The attributes of one Graph can be used to set those of another.
813 >>> H = nx.path_graph(3)
814 >>> nx.set_edge_attributes(H, G.edges)
816 Note that if the dict contains edges that are not in `G`, they are
817 silently ignored::
819 >>> G = nx.Graph([(0, 1)])
820 >>> nx.set_edge_attributes(G, {(1, 2): {"weight": 2.0}})
821 >>> (1, 2) in G.edges()
822 False
824 For multigraphs, the `values` dict is expected to be keyed by 3-tuples
825 including the edge key::
827 >>> MG = nx.MultiGraph()
828 >>> edges = [(0, 1), (0, 1)]
829 >>> MG.add_edges_from(edges) # Returns list of edge keys
830 [0, 1]
831 >>> attributes = {(0, 1, 0): {"cost": 21}, (0, 1, 1): {"cost": 7}}
832 >>> nx.set_edge_attributes(MG, attributes)
833 >>> MG[0][1][0]["cost"]
834 21
835 >>> MG[0][1][1]["cost"]
836 7
838 If MultiGraph attributes are desired for a Graph, you must convert the 3-tuple
839 multiedge to a 2-tuple edge and the last multiedge's attribute value will
840 overwrite the previous values. Continuing from the previous case we get::
842 >>> H = nx.path_graph([0, 1, 2])
843 >>> nx.set_edge_attributes(H, {(u, v): ed for u, v, ed in MG.edges.data()})
844 >>> nx.get_edge_attributes(H, "cost")
845 {(0, 1): 7}
847 """
848 if name is not None:
849 # `values` does not contain attribute names
850 try:
851 # if `values` is a dict using `.items()` => {edge: value}
852 if G.is_multigraph():
853 for (u, v, key), value in values.items():
854 try:
855 G._adj[u][v][key][name] = value
856 except KeyError:
857 pass
858 else:
859 for (u, v), value in values.items():
860 try:
861 G._adj[u][v][name] = value
862 except KeyError:
863 pass
864 except AttributeError:
865 # treat `values` as a constant
866 for u, v, data in G.edges(data=True):
867 data[name] = values
868 else:
869 # `values` consists of doct-of-dict {edge: {attr: value}} shape
870 if G.is_multigraph():
871 for (u, v, key), d in values.items():
872 try:
873 G._adj[u][v][key].update(d)
874 except KeyError:
875 pass
876 else:
877 for (u, v), d in values.items():
878 try:
879 G._adj[u][v].update(d)
880 except KeyError:
881 pass
882 nx._clear_cache(G)
885@nx._dispatchable(edge_attrs={"name": "default"})
886def get_edge_attributes(G, name, default=None):
887 """Get edge attributes from graph
889 Parameters
890 ----------
891 G : NetworkX Graph
893 name : string
894 Attribute name
896 default: object (default=None)
897 Default value of the edge attribute if there is no value set for that
898 edge in graph. If `None` then edges without this attribute are not
899 included in the returned dict.
901 Returns
902 -------
903 Dictionary of attributes keyed by edge. For (di)graphs, the keys are
904 2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of
905 the form: (u, v, key).
907 Examples
908 --------
909 >>> G = nx.Graph()
910 >>> nx.add_path(G, [1, 2, 3], color="red")
911 >>> color = nx.get_edge_attributes(G, "color")
912 >>> color[(1, 2)]
913 'red'
914 >>> G.add_edge(3, 4)
915 >>> color = nx.get_edge_attributes(G, "color", default="yellow")
916 >>> color[(3, 4)]
917 'yellow'
918 """
919 if G.is_multigraph():
920 edges = G.edges(keys=True, data=True)
921 else:
922 edges = G.edges(data=True)
923 if default is not None:
924 return {x[:-1]: x[-1].get(name, default) for x in edges}
925 return {x[:-1]: x[-1][name] for x in edges if name in x[-1]}
928@nx._dispatchable(preserve_edge_attrs=True, mutates_input=True)
929def remove_edge_attributes(G, *attr_names, ebunch=None):
930 """Remove edge attributes from all edges in the graph.
932 Parameters
933 ----------
934 G : NetworkX Graph
936 *attr_names : List of Strings
937 The attribute names to remove from the graph.
939 Examples
940 --------
941 >>> G = nx.path_graph(3)
942 >>> nx.set_edge_attributes(G, {(u, v): u + v for u, v in G.edges()}, name="weight")
943 >>> nx.get_edge_attributes(G, "weight")
944 {(0, 1): 1, (1, 2): 3}
945 >>> remove_edge_attributes(G, "weight")
946 >>> nx.get_edge_attributes(G, "weight")
947 {}
948 """
949 if ebunch is None:
950 ebunch = G.edges(keys=True) if G.is_multigraph() else G.edges()
952 for attr in attr_names:
953 edges = (
954 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
955 )
956 for *e, d in edges:
957 if tuple(e) in ebunch:
958 try:
959 del d[attr]
960 except KeyError:
961 pass
964def all_neighbors(graph, node):
965 """Returns all of the neighbors of a node in the graph.
967 If the graph is directed returns predecessors as well as successors.
969 Parameters
970 ----------
971 graph : NetworkX graph
972 Graph to find neighbors.
973 node : node
974 The node whose neighbors will be returned.
976 Returns
977 -------
978 neighbors : iterator
979 Iterator of neighbors
981 Raises
982 ------
983 NetworkXError
984 If `node` is not in the graph.
986 Examples
987 --------
988 For undirected graphs, this function is equivalent to ``G.neighbors(node)``.
990 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
991 >>> list(nx.all_neighbors(G, 1))
992 [0, 2]
994 For directed graphs, this function returns both predecessors and successors,
995 which may include duplicates if a node is both a predecessor and successor
996 (e.g., in bidirectional edges or self-loops).
998 >>> DG = nx.DiGraph([(0, 1), (1, 2), (2, 1)])
999 >>> list(nx.all_neighbors(DG, 1))
1000 [0, 2, 2]
1002 Notes
1003 -----
1004 This function iterates over all neighbors (both predecessors and successors).
1006 See Also
1007 --------
1008 Graph.neighbors : Returns successors for both Graph and DiGraph
1009 DiGraph.predecessors : Returns predecessors for directed graphs only
1010 DiGraph.successors : Returns successors for directed graphs only
1011 """
1012 if graph.is_directed():
1013 values = chain(graph.predecessors(node), graph.successors(node))
1014 else:
1015 values = graph.neighbors(node)
1016 return values
1019def non_neighbors(graph, node):
1020 """Returns the non-neighbors of the node in the graph.
1022 Parameters
1023 ----------
1024 graph : NetworkX graph
1025 Graph to find neighbors.
1027 node : node
1028 The node whose neighbors will be returned.
1030 Returns
1031 -------
1032 non_neighbors : set
1033 Set of nodes in the graph that are not neighbors of the node.
1034 """
1035 return graph._adj.keys() - graph._adj[node].keys() - {node}
1038def non_edges(graph):
1039 """Returns the nonexistent edges in the graph.
1041 Parameters
1042 ----------
1043 graph : NetworkX graph.
1044 Graph to find nonexistent edges.
1046 Returns
1047 -------
1048 non_edges : iterator
1049 Iterator of edges that are not in the graph.
1050 """
1051 if graph.is_directed():
1052 for u in graph:
1053 for v in non_neighbors(graph, u):
1054 yield (u, v)
1055 else:
1056 nodes = set(graph)
1057 while nodes:
1058 u = nodes.pop()
1059 for v in nodes - set(graph[u]):
1060 yield (u, v)
1063@not_implemented_for("directed")
1064def common_neighbors(G, u, v):
1065 """Returns the common neighbors of two nodes in a graph.
1067 Parameters
1068 ----------
1069 G : graph
1070 A NetworkX undirected graph.
1072 u, v : nodes
1073 Nodes in the graph.
1075 Returns
1076 -------
1077 cnbors : set
1078 Set of common neighbors of u and v in the graph.
1080 Raises
1081 ------
1082 NetworkXError
1083 If u or v is not a node in the graph.
1085 Examples
1086 --------
1087 >>> G = nx.complete_graph(5)
1088 >>> sorted(nx.common_neighbors(G, 0, 1))
1089 [2, 3, 4]
1090 """
1091 if u not in G:
1092 raise nx.NetworkXError("u is not in the graph.")
1093 if v not in G:
1094 raise nx.NetworkXError("v is not in the graph.")
1096 return G._adj[u].keys() & G._adj[v].keys() - {u, v}
1099@nx._dispatchable(preserve_edge_attrs=True)
1100def is_weighted(G, edge=None, weight="weight"):
1101 """Returns True if `G` has weighted edges.
1103 Parameters
1104 ----------
1105 G : graph
1106 A NetworkX graph.
1108 edge : tuple, optional
1109 A 2-tuple specifying the only edge in `G` that will be tested. If
1110 None, then every edge in `G` is tested.
1112 weight: string, optional
1113 The attribute name used to query for edge weights.
1115 Returns
1116 -------
1117 bool
1118 A boolean signifying if `G`, or the specified edge, is weighted.
1120 Raises
1121 ------
1122 NetworkXError
1123 If the specified edge does not exist.
1125 Examples
1126 --------
1127 >>> G = nx.path_graph(4)
1128 >>> nx.is_weighted(G)
1129 False
1130 >>> nx.is_weighted(G, (2, 3))
1131 False
1133 >>> G = nx.DiGraph()
1134 >>> G.add_edge(1, 2, weight=1)
1135 >>> nx.is_weighted(G)
1136 True
1138 """
1139 if edge is not None:
1140 data = G.get_edge_data(*edge)
1141 if data is None:
1142 msg = f"Edge {edge!r} does not exist."
1143 raise nx.NetworkXError(msg)
1144 return weight in data
1146 if is_empty(G):
1147 # Special handling required since: all([]) == True
1148 return False
1150 return all(weight in data for u, v, data in G.edges(data=True))
1153@nx._dispatchable(edge_attrs="weight")
1154def is_negatively_weighted(G, edge=None, weight="weight"):
1155 """Returns True if `G` has negatively weighted edges.
1157 Parameters
1158 ----------
1159 G : graph
1160 A NetworkX graph.
1162 edge : tuple, optional
1163 A 2-tuple specifying the only edge in `G` that will be tested. If
1164 None, then every edge in `G` is tested.
1166 weight: string, optional
1167 The attribute name used to query for edge weights.
1169 Returns
1170 -------
1171 bool
1172 A boolean signifying if `G`, or the specified edge, is negatively
1173 weighted.
1175 Raises
1176 ------
1177 NetworkXError
1178 If the specified edge does not exist.
1180 Examples
1181 --------
1182 >>> G = nx.Graph()
1183 >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)])
1184 >>> G.add_edge(1, 2, weight=4)
1185 >>> nx.is_negatively_weighted(G, (1, 2))
1186 False
1187 >>> G[2][4]["weight"] = -2
1188 >>> nx.is_negatively_weighted(G)
1189 True
1190 >>> G = nx.DiGraph()
1191 >>> edges = [("0", "3", 3), ("0", "1", -5), ("1", "0", -2)]
1192 >>> G.add_weighted_edges_from(edges)
1193 >>> nx.is_negatively_weighted(G)
1194 True
1196 """
1197 if edge is not None:
1198 data = G.get_edge_data(*edge)
1199 if data is None:
1200 msg = f"Edge {edge!r} does not exist."
1201 raise nx.NetworkXError(msg)
1202 return weight in data and data[weight] < 0
1204 return any(weight in data and data[weight] < 0 for u, v, data in G.edges(data=True))
1207@nx._dispatchable
1208def is_empty(G):
1209 """Returns True if `G` has no edges.
1211 Parameters
1212 ----------
1213 G : graph
1214 A NetworkX graph.
1216 Returns
1217 -------
1218 bool
1219 True if `G` has no edges, and False otherwise.
1221 Notes
1222 -----
1223 An empty graph can have nodes but not edges. The empty graph with zero
1224 nodes is known as the null graph. This is an $O(n)$ operation where n
1225 is the number of nodes in the graph.
1227 """
1228 return not any(G._adj.values())
1231def nodes_with_selfloops(G):
1232 """Returns an iterator over nodes with self loops.
1234 A node with a self loop has an edge with both ends adjacent
1235 to that node.
1237 Returns
1238 -------
1239 nodelist : iterator
1240 A iterator over nodes with self loops.
1242 See Also
1243 --------
1244 selfloop_edges, number_of_selfloops
1246 Examples
1247 --------
1248 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1249 >>> G.add_edge(1, 1)
1250 >>> G.add_edge(1, 2)
1251 >>> list(nx.nodes_with_selfloops(G))
1252 [1]
1254 """
1255 return (n for n, nbrs in G._adj.items() if n in nbrs)
1258def selfloop_edges(G, data=False, keys=False, default=None):
1259 """Returns an iterator over selfloop edges.
1261 A selfloop edge has the same node at both ends.
1263 Parameters
1264 ----------
1265 G : graph
1266 A NetworkX graph.
1267 data : string or bool, optional (default=False)
1268 Return selfloop edges as two tuples (u, v) (data=False)
1269 or three-tuples (u, v, datadict) (data=True)
1270 or three-tuples (u, v, datavalue) (data='attrname')
1271 keys : bool, optional (default=False)
1272 If True, return edge keys with each edge.
1273 default : value, optional (default=None)
1274 Value used for edges that don't have the requested attribute.
1275 Only relevant if data is not True or False.
1277 Returns
1278 -------
1279 edgeiter : iterator over edge tuples
1280 An iterator over all selfloop edges.
1282 See Also
1283 --------
1284 nodes_with_selfloops, number_of_selfloops
1286 Examples
1287 --------
1288 >>> G = nx.MultiGraph() # or Graph, DiGraph, MultiDiGraph, etc
1289 >>> ekey = G.add_edge(1, 1)
1290 >>> ekey = G.add_edge(1, 2)
1291 >>> list(nx.selfloop_edges(G))
1292 [(1, 1)]
1293 >>> list(nx.selfloop_edges(G, data=True))
1294 [(1, 1, {})]
1295 >>> list(nx.selfloop_edges(G, keys=True))
1296 [(1, 1, 0)]
1297 >>> list(nx.selfloop_edges(G, keys=True, data=True))
1298 [(1, 1, 0, {})]
1299 """
1300 if data is True:
1301 if G.is_multigraph():
1302 if keys is True:
1303 return (
1304 (n, n, k, d)
1305 for n, nbrs in G._adj.items()
1306 if n in nbrs
1307 for k, d in nbrs[n].items()
1308 )
1309 else:
1310 return (
1311 (n, n, d)
1312 for n, nbrs in G._adj.items()
1313 if n in nbrs
1314 for d in nbrs[n].values()
1315 )
1316 else:
1317 return ((n, n, nbrs[n]) for n, nbrs in G._adj.items() if n in nbrs)
1318 elif data is not False:
1319 if G.is_multigraph():
1320 if keys is True:
1321 return (
1322 (n, n, k, d.get(data, default))
1323 for n, nbrs in G._adj.items()
1324 if n in nbrs
1325 for k, d in nbrs[n].items()
1326 )
1327 else:
1328 return (
1329 (n, n, d.get(data, default))
1330 for n, nbrs in G._adj.items()
1331 if n in nbrs
1332 for d in nbrs[n].values()
1333 )
1334 else:
1335 return (
1336 (n, n, nbrs[n].get(data, default))
1337 for n, nbrs in G._adj.items()
1338 if n in nbrs
1339 )
1340 else:
1341 if G.is_multigraph():
1342 if keys is True:
1343 return (
1344 (n, n, k)
1345 for n, nbrs in G._adj.items()
1346 if n in nbrs
1347 for k in nbrs[n]
1348 )
1349 else:
1350 return (
1351 (n, n)
1352 for n, nbrs in G._adj.items()
1353 if n in nbrs
1354 for i in range(len(nbrs[n])) # for easy edge removal (#4068)
1355 )
1356 else:
1357 return ((n, n) for n, nbrs in G._adj.items() if n in nbrs)
1360@nx._dispatchable
1361def number_of_selfloops(G):
1362 """Returns the number of selfloop edges.
1364 A selfloop edge has the same node at both ends.
1366 Returns
1367 -------
1368 nloops : int
1369 The number of selfloops.
1371 See Also
1372 --------
1373 nodes_with_selfloops, selfloop_edges
1375 Examples
1376 --------
1377 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1378 >>> G.add_edge(1, 1)
1379 >>> G.add_edge(1, 2)
1380 >>> nx.number_of_selfloops(G)
1381 1
1382 """
1383 return sum(1 for _ in nx.selfloop_edges(G))
1386def is_path(G, path):
1387 """Returns whether or not the specified path exists.
1389 For it to return True, every node on the path must exist and
1390 each consecutive pair must be connected via one or more edges.
1392 Parameters
1393 ----------
1394 G : graph
1395 A NetworkX graph.
1397 path : list
1398 A list of nodes which defines the path to traverse
1400 Returns
1401 -------
1402 bool
1403 True if `path` is a valid path in `G`
1405 """
1406 try:
1407 return all(nbr in G._adj[node] for node, nbr in nx.utils.pairwise(path))
1408 except (KeyError, TypeError):
1409 return False
1412def path_weight(G, path, weight):
1413 """Returns total cost associated with specified path and weight
1415 Parameters
1416 ----------
1417 G : graph
1418 A NetworkX graph.
1420 path: list
1421 A list of node labels which defines the path to traverse
1423 weight: string
1424 A string indicating which edge attribute to use for path cost
1426 Returns
1427 -------
1428 cost: int or float
1429 An integer or a float representing the total cost with respect to the
1430 specified weight of the specified path
1432 Raises
1433 ------
1434 NetworkXNoPath
1435 If the specified edge does not exist.
1436 """
1437 multigraph = G.is_multigraph()
1438 cost = 0
1440 if not nx.is_path(G, path):
1441 raise nx.NetworkXNoPath("path does not exist")
1442 for node, nbr in nx.utils.pairwise(path):
1443 if multigraph:
1444 cost += min(v[weight] for v in G._adj[node][nbr].values())
1445 else:
1446 cost += G._adj[node][nbr][weight]
1447 return cost
1450def describe(G, describe_hook=None):
1451 """Prints a description of the graph G.
1453 By default, the description includes some basic properties of the graph.
1454 You can also provide additional functions to compute and include
1455 more properties in the description.
1457 Parameters
1458 ----------
1459 G : graph
1460 A NetworkX graph.
1462 describe_hook: callable, optional (default=None)
1463 A function that takes a graph as input and returns a
1464 dictionary of additional properties to include in the description.
1465 The keys of the dictionary are the property names, and the values
1466 are the corresponding property values.
1468 Examples
1469 --------
1470 >>> G = nx.path_graph(5)
1471 >>> nx.describe(G)
1472 Number of nodes : 5
1473 Number of edges : 4
1474 Directed : False
1475 Multigraph : False
1476 Tree : True
1477 Bipartite : True
1478 Average degree (min, max) : 1.60 (1, 2)
1479 Number of connected components : 1
1481 >>> def augment_description(G):
1482 ... return {"Average Shortest Path Length": nx.average_shortest_path_length(G)}
1483 >>> nx.describe(G, describe_hook=augment_description)
1484 Number of nodes : 5
1485 Number of edges : 4
1486 Directed : False
1487 Multigraph : False
1488 Tree : True
1489 Bipartite : True
1490 Average degree (min, max) : 1.60 (1, 2)
1491 Number of connected components : 1
1492 Average Shortest Path Length : 2.0
1494 >>> G.name = "Path Graph of 5 nodes"
1495 >>> nx.describe(G)
1496 Name of Graph : Path Graph of 5 nodes
1497 Number of nodes : 5
1498 Number of edges : 4
1499 Directed : False
1500 Multigraph : False
1501 Tree : True
1502 Bipartite : True
1503 Average degree (min, max) : 1.60 (1, 2)
1504 Number of connected components : 1
1506 """
1507 info_dict = _create_describe_info_dict(G)
1509 if describe_hook is not None:
1510 additional_info = describe_hook(G)
1511 info_dict.update(additional_info)
1513 max_key_len = max(len(k) for k in info_dict)
1514 for key, val in info_dict.items():
1515 print(f"{key:<{max_key_len}} : {val}")
1518def _create_describe_info_dict(G):
1519 info = {}
1520 if G.name != "":
1521 info["Name of Graph"] = G.name
1522 info.update(
1523 {
1524 "Number of nodes": len(G),
1525 "Number of edges": G.number_of_edges(),
1526 "Directed": G.is_directed(),
1527 "Multigraph": G.is_multigraph(),
1528 "Tree": nx.is_tree(G),
1529 "Bipartite": nx.is_bipartite(G),
1530 }
1531 )
1532 if len(G) == 0:
1533 return info
1535 degree_values = dict(nx.degree(G)).values()
1536 avg_degree = sum(degree_values) / len(G)
1537 max_degree, min_degree = max(degree_values), min(degree_values)
1538 info["Average degree (min, max)"] = f"{avg_degree:.2f} ({min_degree}, {max_degree})"
1540 if G.is_directed():
1541 info["Number of strongly connected components"] = (
1542 nx.number_strongly_connected_components(G)
1543 )
1544 info["Number of weakly connected components"] = (
1545 nx.number_weakly_connected_components(G)
1546 )
1547 else:
1548 info["Number of connected components"] = nx.number_connected_components(G)
1549 return info