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"""Functions related to the Wiener Index of a graph.
3The Wiener Index is a topological measure of a graph
4related to the distance between nodes and their degree.
5The Schultz Index and Gutman Index are similar measures.
6They are used categorize molecules via the network of
7atoms connected by chemical bonds. The indices are
8correlated with functional aspects of the molecules.
10References
11----------
12.. [1] `Wikipedia: Wiener Index <https://en.wikipedia.org/wiki/Wiener_index>`_
13.. [2] M.V. Diudeaa and I. Gutman, Wiener-Type Topological Indices,
14 Croatica Chemica Acta, 71 (1998), 21-51.
15 https://hrcak.srce.hr/132323
16"""
18import itertools as it
20import networkx as nx
22__all__ = ["wiener_index", "schultz_index", "gutman_index", "hyper_wiener_index"]
25@nx._dispatchable(edge_attrs="weight")
26def wiener_index(G, weight=None):
27 """Returns the Wiener index of the given graph.
29 The *Wiener index* of a graph is the sum of the shortest-path
30 (weighted) distances between each pair of reachable nodes.
31 For pairs of nodes in undirected graphs, only one orientation
32 of the pair is counted.
34 Parameters
35 ----------
36 G : NetworkX graph
38 weight : string or None, optional (default: None)
39 If None, every edge has weight 1.
40 If a string, use this edge attribute as the edge weight.
41 Any edge attribute not present defaults to 1.
42 The edge weights are used to computing shortest-path distances.
44 Returns
45 -------
46 number
47 The Wiener index of the graph `G`.
49 Raises
50 ------
51 NetworkXError
52 If the graph `G` is not connected.
54 Notes
55 -----
56 If a pair of nodes is not reachable, the distance is assumed to be
57 infinity. This means that for graphs that are not
58 strongly-connected, this function returns ``inf``.
60 The Wiener index is not usually defined for directed graphs, however
61 this function uses the natural generalization of the Wiener index to
62 directed graphs.
64 Examples
65 --------
66 The Wiener index of the (unweighted) complete graph on *n* nodes
67 equals the number of pairs of the *n* nodes, since each pair of
68 nodes is at distance one::
70 >>> n = 10
71 >>> G = nx.complete_graph(n)
72 >>> nx.wiener_index(G) == n * (n - 1) / 2
73 True
75 Graphs that are not strongly-connected have infinite Wiener index::
77 >>> G = nx.empty_graph(2)
78 >>> nx.wiener_index(G)
79 inf
81 References
82 ----------
83 .. [1] `Wikipedia: Wiener Index <https://en.wikipedia.org/wiki/Wiener_index>`_
84 """
85 connected = nx.is_strongly_connected(G) if G.is_directed() else nx.is_connected(G)
86 if not connected:
87 return float("inf")
89 spl = nx.shortest_path_length(G, weight=weight)
90 total = sum(it.chain.from_iterable(nbrs.values() for node, nbrs in spl))
91 # Need to account for double counting pairs of nodes in undirected graphs.
92 return total if G.is_directed() else total / 2
95@nx.utils.not_implemented_for("directed")
96@nx.utils.not_implemented_for("multigraph")
97@nx._dispatchable(edge_attrs="weight")
98def schultz_index(G, weight=None):
99 r"""Returns the Schultz Index (of the first kind) of `G`
101 The *Schultz Index* [3]_ of a graph is the sum over all node pairs of
102 distances times the sum of degrees. Consider an undirected graph `G`.
103 For each node pair ``(u, v)`` compute ``dist(u, v) * (deg(u) + deg(v)``
104 where ``dist`` is the shortest path length between two nodes and ``deg``
105 is the degree of a node.
107 The Schultz Index is the sum of these quantities over all (unordered)
108 pairs of nodes.
110 Parameters
111 ----------
112 G : NetworkX graph
113 The undirected graph of interest.
114 weight : string or None, optional (default: None)
115 If None, every edge has weight 1.
116 If a string, use this edge attribute as the edge weight.
117 Any edge attribute not present defaults to 1.
118 The edge weights are used to computing shortest-path distances.
120 Returns
121 -------
122 number
123 The first kind of Schultz Index of the graph `G`.
125 Examples
126 --------
127 The Schultz Index of the (unweighted) complete graph on *n* nodes
128 equals the number of pairs of the *n* nodes times ``2 * (n - 1)``,
129 since each pair of nodes is at distance one and the sum of degree
130 of two nodes is ``2 * (n - 1)``.
132 >>> n = 10
133 >>> G = nx.complete_graph(n)
134 >>> nx.schultz_index(G) == (n * (n - 1) / 2) * (2 * (n - 1))
135 True
137 Graph that is disconnected
139 >>> nx.schultz_index(nx.empty_graph(2))
140 inf
142 References
143 ----------
144 .. [1] I. Gutman, Selected properties of the Schultz molecular topological index,
145 J. Chem. Inf. Comput. Sci. 34 (1994), 1087–1089.
146 https://doi.org/10.1021/ci00021a009
147 .. [2] M.V. Diudeaa and I. Gutman, Wiener-Type Topological Indices,
148 Croatica Chemica Acta, 71 (1998), 21-51.
149 https://hrcak.srce.hr/132323
150 .. [3] H. P. Schultz, Topological organic chemistry. 1.
151 Graph theory and topological indices of alkanes,i
152 J. Chem. Inf. Comput. Sci. 29 (1989), 239–257.
154 """
155 if not nx.is_connected(G):
156 return float("inf")
158 spl = nx.shortest_path_length(G, weight=weight)
159 d = dict(G.degree, weight=weight)
160 return sum(dist * (d[u] + d[v]) for u, info in spl for v, dist in info.items()) / 2
163@nx.utils.not_implemented_for("directed")
164@nx.utils.not_implemented_for("multigraph")
165@nx._dispatchable(edge_attrs="weight")
166def gutman_index(G, weight=None):
167 r"""Returns the Gutman Index for the graph `G`.
169 The *Gutman Index* measures the topology of networks, especially for molecule
170 networks of atoms connected by bonds [1]_. It is also called the Schultz Index
171 of the second kind [2]_.
173 Consider an undirected graph `G` with node set ``V``.
174 The Gutman Index of a graph is the sum over all (unordered) pairs of nodes
175 of nodes ``(u, v)``, with distance ``dist(u, v)`` and degrees ``deg(u)``
176 and ``deg(v)``, of ``dist(u, v) * deg(u) * deg(v)``
178 Parameters
179 ----------
180 G : NetworkX graph
182 weight : string or None, optional (default: None)
183 If None, every edge has weight 1.
184 If a string, use this edge attribute as the edge weight.
185 Any edge attribute not present defaults to 1.
186 The edge weights are used to computing shortest-path distances.
188 Returns
189 -------
190 number
191 The Gutman Index of the graph `G`.
193 Examples
194 --------
195 The Gutman Index of the (unweighted) complete graph on *n* nodes
196 equals the number of pairs of the *n* nodes times ``(n - 1) * (n - 1)``,
197 since each pair of nodes is at distance one and the product of degree of two
198 vertices is ``(n - 1) * (n - 1)``.
200 >>> n = 10
201 >>> G = nx.complete_graph(n)
202 >>> nx.gutman_index(G) == (n * (n - 1) / 2) * ((n - 1) * (n - 1))
203 True
205 Graphs that are disconnected
207 >>> G = nx.empty_graph(2)
208 >>> nx.gutman_index(G)
209 inf
211 References
212 ----------
213 .. [1] M.V. Diudeaa and I. Gutman, Wiener-Type Topological Indices,
214 Croatica Chemica Acta, 71 (1998), 21-51.
215 https://hrcak.srce.hr/132323
216 .. [2] I. Gutman, Selected properties of the Schultz molecular topological index,
217 J. Chem. Inf. Comput. Sci. 34 (1994), 1087–1089.
218 https://doi.org/10.1021/ci00021a009
220 """
221 if not nx.is_connected(G):
222 return float("inf")
224 spl = nx.shortest_path_length(G, weight=weight)
225 d = dict(G.degree, weight=weight)
226 return sum(dist * d[u] * d[v] for u, vinfo in spl for v, dist in vinfo.items()) / 2
229@nx.utils.not_implemented_for("directed")
230@nx.utils.not_implemented_for("multigraph")
231@nx._dispatchable(edge_attrs="weight")
232def hyper_wiener_index(G, weight=None):
233 r"""Returns the Hyper-Wiener index of the graph `G`.
235 The Hyper-Wiener index of a connected graph `G` is defined as
237 .. math::
238 WW(G) = \frac{1}{2} \sum_{u,v \in V(G)} (d(u,v) + d(u,v)^2)
240 where ``d(u, v)`` is the shortest-path distance between nodes ``u`` and ``v``.
242 Parameters
243 ----------
244 G : NetworkX graph
245 An undirected, connected graph.
247 weight : string or None, optional (default: None)
248 The edge attribute to use for calculating shortest-path distances.
249 If None, all edges are considered to have a weight of 1.
251 Returns
252 -------
253 float
254 The Hyper-Wiener index of the graph G.
255 Returns float("inf") if the graph is not connected.
257 References
258 ----------
259 .. [1] M. Randić, "Novel molecular descriptor for structure-property studies,"
260 Chemical Physics Letters, vol. 211, pp. 478-483, 1993.
261 .. [2] `Wikipedia: Hyper-Wiener Index <https://en.wikipedia.org/wiki/Hyper-Wiener_index>`_
263 Examples
264 --------
265 >>> G = nx.path_graph(4)
266 >>> nx.hyper_wiener_index(G)
267 30.0
269 >>> G = nx.cycle_graph(4)
270 >>> nx.hyper_wiener_index(G)
271 20.0
272 """
273 if not nx.is_connected(G):
274 return float("inf")
276 spl = nx.shortest_path_length(G, weight=weight)
277 total = sum(dist + dist**2 for _, lengths in spl for dist in lengths.values())
278 return total / 2