spanner

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

返回给定图具有给定拉伸度的 spanner。

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

参数：

GNetworkX 图

一个无向简单图。

stretchfloat

spanner 的拉伸度。

weightobject

用作距离的边属性。

seed整数、random_state 或 None（默认）

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

返回：

NetworkX 图

给定图具有给定拉伸度的 spanner。

引发：

ValueError

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

注解

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

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

参考文献

[1] S. Baswana, S. Sen. A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs. Random Struct. Algorithms 30(4): 532-563 (2007)。