Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/wiener.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions related to the Wiener index of a graph.""" | |
2 | |
3 from itertools import chain | |
4 | |
5 from .components import is_connected | |
6 from .components import is_strongly_connected | |
7 from .shortest_paths import shortest_path_length as spl | |
8 | |
9 __all__ = ["wiener_index"] | |
10 | |
11 #: Rename the :func:`chain.from_iterable` function for the sake of | |
12 #: brevity. | |
13 chaini = chain.from_iterable | |
14 | |
15 | |
16 def wiener_index(G, weight=None): | |
17 """Returns the Wiener index of the given graph. | |
18 | |
19 The *Wiener index* of a graph is the sum of the shortest-path | |
20 distances between each pair of reachable nodes. For pairs of nodes | |
21 in undirected graphs, only one orientation of the pair is counted. | |
22 | |
23 Parameters | |
24 ---------- | |
25 G : NetworkX graph | |
26 | |
27 weight : object | |
28 The edge attribute to use as distance when computing | |
29 shortest-path distances. This is passed directly to the | |
30 :func:`networkx.shortest_path_length` function. | |
31 | |
32 Returns | |
33 ------- | |
34 float | |
35 The Wiener index of the graph `G`. | |
36 | |
37 Raises | |
38 ------ | |
39 NetworkXError | |
40 If the graph `G` is not connected. | |
41 | |
42 Notes | |
43 ----- | |
44 If a pair of nodes is not reachable, the distance is assumed to be | |
45 infinity. This means that for graphs that are not | |
46 strongly-connected, this function returns ``inf``. | |
47 | |
48 The Wiener index is not usually defined for directed graphs, however | |
49 this function uses the natural generalization of the Wiener index to | |
50 directed graphs. | |
51 | |
52 Examples | |
53 -------- | |
54 The Wiener index of the (unweighted) complete graph on *n* nodes | |
55 equals the number of pairs of the *n* nodes, since each pair of | |
56 nodes is at distance one:: | |
57 | |
58 >>> n = 10 | |
59 >>> G = nx.complete_graph(n) | |
60 >>> nx.wiener_index(G) == n * (n - 1) / 2 | |
61 True | |
62 | |
63 Graphs that are not strongly-connected have infinite Wiener index:: | |
64 | |
65 >>> G = nx.empty_graph(2) | |
66 >>> nx.wiener_index(G) | |
67 inf | |
68 | |
69 """ | |
70 is_directed = G.is_directed() | |
71 if (is_directed and not is_strongly_connected(G)) or ( | |
72 not is_directed and not is_connected(G) | |
73 ): | |
74 return float("inf") | |
75 total = sum(chaini(p.values() for v, p in spl(G, weight=weight))) | |
76 # Need to account for double counting pairs of nodes in undirected graphs. | |
77 return total if is_directed else total / 2 |