Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / wiener.py @ 5cef0f13

History | View | Annotate | Download (2.53 KB)

1
# wiener.py - functions related to the Wiener index of a graph
2
#
3
# Copyright 2015 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Functions related to the Wiener index of a graph."""
10
from __future__ import division
11

    
12
from itertools import chain
13

    
14
from .components import is_connected
15
from .components import is_strongly_connected
16
from .shortest_paths import shortest_path_length as spl
17

    
18
__all__ = ['wiener_index']
19

    
20
#: Rename the :func:`chain.from_iterable` function for the sake of
21
#: brevity.
22
chaini = chain.from_iterable
23

    
24

    
25
def wiener_index(G, weight=None):
26
    """Returns the Wiener index of the given graph.
27

28
    The *Wiener index* of a graph is the sum of the shortest-path
29
    distances between each pair of reachable nodes. For pairs of nodes
30
    in undirected graphs, only one orientation of the pair is counted.
31

32
    Parameters
33
    ----------
34
    G : NetworkX graph
35

36
    weight : object
37
        The edge attribute to use as distance when computing
38
        shortest-path distances. This is passed directly to the
39
        :func:`networkx.shortest_path_length` function.
40

41
    Returns
42
    -------
43
    float
44
        The Wiener index of the graph `G`.
45

46
    Raises
47
    ------
48
    NetworkXError
49
        If the graph `G` is not connected.
50

51
    Notes
52
    -----
53
    If a pair of nodes is not reachable, the distance is assumed to be
54
    infinity. This means that for graphs that are not
55
    strongly-connected, this function returns ``inf``.
56

57
    The Wiener index is not usually defined for directed graphs, however
58
    this function uses the natural generalization of the Wiener index to
59
    directed graphs.
60

61
    Examples
62
    --------
63
    The Wiener index of the (unweighted) complete graph on *n* nodes
64
    equals the number of pairs of the *n* nodes, since each pair of
65
    nodes is at distance one::
66

67
        >>> import networkx as nx
68
        >>> n = 10
69
        >>> G = nx.complete_graph(n)
70
        >>> nx.wiener_index(G) == n * (n - 1) / 2
71
        True
72

73
    Graphs that are not strongly-connected have infinite Wiener index::
74

75
        >>> G = nx.empty_graph(2)
76
        >>> nx.wiener_index(G)
77
        inf
78

79
    """
80
    is_directed = G.is_directed()
81
    if (is_directed and not is_strongly_connected(G)) or \
82
            (not is_directed and not is_connected(G)):
83
        return float('inf')
84
    total = sum(chaini(p.values() for v, p in spl(G, weight=weight)))
85
    # Need to account for double counting pairs of nodes in undirected graphs.
86
    return total if is_directed else total / 2