Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
networkx.algorithms.sparsifiers.spanner¶

spanner
(G, stretch, weight=None, seed=None)[source]¶ Returns a spanner of the given graph with the given stretch.
A spanner of a graph G = (V, E) with stretch t is a subgraph H = (V, E_S) such that E_S is a subset of E and the distance between any pair of nodes in H is at most t times the distance between the nodes in G.
 Parameters
 GNetworkX graph
An undirected simple graph.
 stretchfloat
The stretch of the spanner.
 weightobject
The edge attribute to use as distance.
 seedinteger, random_state, or None (default)
Indicator of random number generation state. See Randomness.
 Returns
 NetworkX graph
A spanner of the given graph with the given stretch.
 Raises
 ValueError
If a stretch less than 1 is given.
Notes
This function implements the spanner algorithm by Baswana and Sen, see [1].
This algorithm is a randomized las vegas algorithm: The expected running time is O(km) where k = (stretch + 1) // 2 and m is the number of edges in G. The returned graph is always a spanner of the given graph with the specified stretch. For weighted graphs the number of edges in the spanner is O(k * n^(1 + 1 / k)) where k is defined as above and n is the number of nodes in G. For unweighted graphs the number of edges is O(n^(1 + 1 / k) + kn).
References
[1] S. Baswana, S. Sen. A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs. Random Struct. Algorithms 30(4): 532563 (2007).