extrema_bounding#
- extrema_bounding(G, compute='diameter')[source]#
Compute requested extreme distance metric of undirected graph G
Deprecated since version 2.8: extrema_bounding is deprecated and will be removed in NetworkX 3.0. Use the corresponding distance measure with the
usebounds=True
option instead.Computation is based on smart lower and upper bounds, and in practice linear in the number of nodes, rather than quadratic (except for some border cases such as complete graphs or circle shaped graphs).
- Parameters:
- GNetworkX graph
An undirected graph
- computestring denoting the requesting metric
“diameter” for the maximal eccentricity value, “radius” for the minimal eccentricity value, “periphery” for the set of nodes with eccentricity equal to the diameter, “center” for the set of nodes with eccentricity equal to the radius, “eccentricities” for the maximum distance from each node to all other nodes in G
- Returns:
- valuevalue of the requested metric
int for “diameter” and “radius” or list of nodes for “center” and “periphery” or dictionary of eccentricity values keyed by node for “eccentricities”
- Raises:
- NetworkXError
If the graph consists of multiple components
- ValueError
If
compute
is not one of “diameter”, “radius”, “periphery”, “center”, or “eccentricities”.
Notes
This algorithm was proposed in the following papers:
F.W. Takes and W.A. Kosters, Determining the Diameter of Small World Networks, in Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM 2011), pp. 1191-1196, 2011. doi: https://doi.org/10.1145/2063576.2063748
F.W. Takes and W.A. Kosters, Computing the Eccentricity Distribution of Large Graphs, Algorithms 6(1): 100-118, 2013. doi: https://doi.org/10.3390/a6010100
M. Borassi, P. Crescenzi, M. Habib, W.A. Kosters, A. Marino and F.W. Takes, Fast Graph Diameter and Radius BFS-Based Computation in (Weakly Connected) Real-World Graphs, Theoretical Computer Science 586: 59-80, 2015. doi: https://doi.org/10.1016/j.tcs.2015.02.033