spanner

spanner(G, stretch, weight=None, seed=None)

返回具有给定伸展度的给定图的稀疏图。

图 G = (V, E) 的伸展度为 t 的稀疏图是一个子图 H = (V, E_S)，其中 E_S 是 E 的子集，并且 H 中任意一对节点之间的距离最多是 G 中节点之间距离的 t 倍。

Parameters:

GNetworkX 图

一个无向简单图。

stretchfloat

稀疏图的伸展度。

weight对象

用作距离的边属性。

seed整数，random_state，或 None（默认）

随机数生成状态的指示器。 参见 Randomness 。

Returns:

NetworkX 图

具有给定伸展度的给定图的稀疏图。

Raises:

ValueError

如果给定的伸展度小于 1。

Notes

此函数实现了 Baswana 和 Sen 的稀疏图算法， 参见 [1]。

该算法是一个随机化的拉斯维加斯算法：期望的运行时间是 O(km)，其中 k = (stretch + 1) // 2，m 是 G 中的边数。返回的图始终是具有指定伸展度的给定图的稀疏图。对于加权图，稀疏图中的边数是 O(k * n^(1 + 1 / k))，其中 k 如上定义，n 是 G 中的节点数。对于无权图，边数是 O(n^(1 + 1 / k) + kn)。

References

[1] S. Baswana, S. Sen. 一种简单且线性时间随机化算法，用于在加权图中计算稀疏图。 Random Struct. Algorithms 30(4): 532-563 (2007).