Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/wiener.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
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
11 from itertools import chain
12
13 from .components import is_connected
14 from .components import is_strongly_connected
15 from .shortest_paths import shortest_path_length as spl
16
17 __all__ = ['wiener_index']
18
19 #: Rename the :func:`chain.from_iterable` function for the sake of
20 #: brevity.
21 chaini = chain.from_iterable
22
23
24 def wiener_index(G, weight=None):
25 """Returns the Wiener index of the given graph.
26
27 The *Wiener index* of a graph is the sum of the shortest-path
28 distances between each pair of reachable nodes. For pairs of nodes
29 in undirected graphs, only one orientation of the pair is counted.
30
31 Parameters
32 ----------
33 G : NetworkX graph
34
35 weight : object
36 The edge attribute to use as distance when computing
37 shortest-path distances. This is passed directly to the
38 :func:`networkx.shortest_path_length` function.
39
40 Returns
41 -------
42 float
43 The Wiener index of the graph `G`.
44
45 Raises
46 ------
47 NetworkXError
48 If the graph `G` is not connected.
49
50 Notes
51 -----
52 If a pair of nodes is not reachable, the distance is assumed to be
53 infinity. This means that for graphs that are not
54 strongly-connected, this function returns ``inf``.
55
56 The Wiener index is not usually defined for directed graphs, however
57 this function uses the natural generalization of the Wiener index to
58 directed graphs.
59
60 Examples
61 --------
62 The Wiener index of the (unweighted) complete graph on *n* nodes
63 equals the number of pairs of the *n* nodes, since each pair of
64 nodes is at distance one::
65
66 >>> import networkx as nx
67 >>> n = 10
68 >>> G = nx.complete_graph(n)
69 >>> nx.wiener_index(G) == n * (n - 1) / 2
70 True
71
72 Graphs that are not strongly-connected have infinite Wiener index::
73
74 >>> G = nx.empty_graph(2)
75 >>> nx.wiener_index(G)
76 inf
77
78 """
79 is_directed = G.is_directed()
80 if (is_directed and not is_strongly_connected(G)) or \
81 (not is_directed and not is_connected(G)):
82 return float('inf')
83 total = sum(chaini(p.values() for v, p in spl(G, weight=weight)))
84 # Need to account for double counting pairs of nodes in undirected graphs.
85 return total if is_directed else total / 2