# wiener.py - functions related to the Wiener index of a graph
# Copyright 2015 NetworkX developers.
# This file is part of NetworkX.
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
"""Functions related to the Wiener index of a graph."""
from __future__ import division
from itertools import chain
from .components import is_connected
from .components import is_strongly_connected
from .shortest_paths import shortest_path_length as spl
__all__ = ['wiener_index']
#: Rename the :func:`chain.from_iterable` function for the sake of
chaini = chain.from_iterable
[docs]def wiener_index(G, weight=None):
"""Returns the Wiener index of the given graph.
The *Wiener index* of a graph is the sum of the shortest-path
distances between each pair of reachable nodes. For pairs of nodes
in undirected graphs, only one orientation of the pair is counted.
G : NetworkX graph
weight : object
The edge attribute to use as distance when computing
shortest-path distances. This is passed directly to the
The Wiener index of the graph `G`.
If the graph `G` is not connected.
If a pair of nodes is not reachable, the distance is assumed to be
infinity. This means that for graphs that are not
strongly-connected, this function returns ``inf``.
The Wiener index is not usually defined for directed graphs, however
this function uses the natural generalization of the Wiener index to
The Wiener index of the (unweighted) complete graph on *n* nodes
equals the number of pairs of the *n* nodes, since each pair of
nodes is at distance one::
>>> import networkx as nx
>>> n = 10
>>> G = nx.complete_graph(n)
>>> nx.wiener_index(G) == n * (n - 1) / 2
Graphs that are not strongly-connected have infinite Wiener index::
>>> G = nx.empty_graph(2)
is_directed = G.is_directed()
if (is_directed and not is_strongly_connected(G)) or
(not is_directed and not is_connected(G)):
total = sum(chaini(p.values() for v, p in spl(G, weight=weight)))
# Need to account for double counting pairs of nodes in undirected graphs.
return total if is_directed else total / 2