networkx 2.8.2 Pypi GitHub Homepage
Other Docs
NotesParametersRaisesReturns
spanner(G, stretch, weight=None, seed=None)

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.

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).

Parameters

G : NetworkX graph

An undirected simple graph.

stretch : float

The stretch of the spanner.

weight : object

The edge attribute to use as distance.

seed : integer, random_state, or None (default)

Indicator of random number generation state. See Randomness<randomness> .

Raises

ValueError

If a stretch less than 1 is given.

Returns

NetworkX graph

A spanner of the given graph with the given stretch.

Returns a spanner of the given graph with the given stretch.

Examples

See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them


GitHub : /networkx/algorithms/sparsifiers.py#9
type: <class 'function'>
Commit: