networkx.algorithms.operators.product.power¶
-
power
(G, k)[source]¶ Returns the specified power of a graph.
The \(k\), denoted \(G^k\), is a graph on the same set of nodes in which two distinct nodes \(u\) and \(v\) are adjacent in \(G^k\) if and only if the shortest path distance between \(u\) and \(v\) in \(G\) is at most \(k\).
- Parameters
G (graph) – A NetworkX simple graph object.
k (positive integer) – The power to which to raise the graph
G
.
- Returns
G
to the powerk
.- Return type
NetworkX simple graph
- Raises
ValueError – If the exponent
k
is not positive.NetworkXNotImplemented – If
G
is not a simple graph.
Examples
The number of edges will never decrease when taking successive powers:
>>> G = nx.path_graph(4) >>> list(nx.power(G, 2).edges) [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] >>> list(nx.power(G, 3).edges) [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
The
k`th power of a cycle graph on *n* nodes is the complete graph on *n* nodes, if `k
is at leastn // 2
:>>> G = nx.cycle_graph(5) >>> H = nx.complete_graph(5) >>> nx.is_isomorphic(nx.power(G, 2), H) True >>> G = nx.cycle_graph(8) >>> H = nx.complete_graph(8) >>> nx.is_isomorphic(nx.power(G, 4), H) True
References
- 1
Bondy, U. S. R. Murty, Graph Theory. Springer, 2008.
Notes
This definition of “power graph” comes from Exercise 3.1.6 of Graph Theory by Bondy and Murty 1.