Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/wiener.py: 62%

1"""Functions related to the Wiener index of a graph.""" 

2 

3from itertools import chain 

4 

5import networkx as nx 

6 

7from .components import is_connected, is_strongly_connected 

8from .shortest_paths import shortest_path_length as spl 

9 

10__all__ = ["wiener_index"] 

11 

12#: Rename the :func:`chain.from_iterable` function for the sake of 

13#: brevity. 

14chaini = chain.from_iterable 

15 

16 

17@nx._dispatch(edge_attrs="weight") 

18def wiener_index(G, weight=None): 

19 """Returns the Wiener index of the given graph. 

20 

21 The *Wiener index* of a graph is the sum of the shortest-path 

22 distances between each pair of reachable nodes. For pairs of nodes 

23 in undirected graphs, only one orientation of the pair is counted. 

24 

25 Parameters 

26 ---------- 

27 G : NetworkX graph 

28 

29 weight : object 

30 The edge attribute to use as distance when computing 

31 shortest-path distances. This is passed directly to the 

32 :func:`networkx.shortest_path_length` function. 

33 

34 Returns 

35 ------- 

36 float 

37 The Wiener index of the graph `G`. 

38 

39 Raises 

40 ------ 

41 NetworkXError 

42 If the graph `G` is not connected. 

43 

44 Notes 

45 ----- 

46 If a pair of nodes is not reachable, the distance is assumed to be 

47 infinity. This means that for graphs that are not 

48 strongly-connected, this function returns ``inf``. 

49 

50 The Wiener index is not usually defined for directed graphs, however 

51 this function uses the natural generalization of the Wiener index to 

52 directed graphs. 

53 

54 Examples 

55 -------- 

56 The Wiener index of the (unweighted) complete graph on *n* nodes 

57 equals the number of pairs of the *n* nodes, since each pair of 

58 nodes is at distance one:: 

59 

60 >>> n = 10 

61 >>> G = nx.complete_graph(n) 

62 >>> nx.wiener_index(G) == n * (n - 1) / 2 

63 True 

64 

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

66 

67 >>> G = nx.empty_graph(2) 

68 >>> nx.wiener_index(G) 

69 inf 

70 

71 """ 

72 is_directed = G.is_directed() 

73 if (is_directed and not is_strongly_connected(G)) or ( 

74 not is_directed and not is_connected(G) 

75 ): 

76 return float("inf") 

77 total = sum(chaini(p.values() for v, p in spl(G, weight=weight))) 

78 # Need to account for double counting pairs of nodes in undirected graphs. 

79 return total if is_directed else total / 2