U 9v f@sFdZddlmZddlmZmZddlmZdgZ ej Z d ddZ dS) z1Functions related to the Wiener index of a graph.)chain) is_connectedis_strongly_connected)shortest_path_length wiener_indexNcCsV|}|rt|r |s(t|s(tdSttddt||dD}|rN|S|dS)aReturns 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. Parameters ---------- G : NetworkX graph weight : object The edge attribute to use as distance when computing shortest-path distances. This is passed directly to the :func:`networkx.shortest_path_length` function. Returns ------- float The Wiener index of the graph `G`. Raises ------ NetworkXError If the graph `G` is not connected. Notes ----- 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 directed graphs. Examples -------- 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:: >>> n = 10 >>> G = nx.complete_graph(n) >>> nx.wiener_index(G) == n * (n - 1) / 2 True Graphs that are not strongly-connected have infinite Wiener index:: >>> G = nx.empty_graph(2) >>> nx.wiener_index(G) inf infcss|]\}}|VqdS)N)values).0vpr >/tmp/pip-unpacked-wheel-_lngutwb/networkx/algorithms/wiener.py Jszwiener_index..)weight) is_directedrrfloatsumchainispl)Grrtotalr r rrs6 )N) __doc__ itertoolsr componentsrrZshortest_pathsrr__all__ from_iterablerrr r r rs