扳手

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

返回具有给定拉伸的给定图形的扳手。

图G=（v，e）的一个带拉伸t的扳手是子图H=（v，e_s），这样e_s是e的一个子集，h中任意一对节点之间的距离最多是g中节点之间距离的t倍。

参数

G网络X图表

一个无向的简单图。

stretch浮动

扳手的伸展。

weight对象

要用作距离的边属性。

seed整数、随机状态或无（默认）

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

返回

网络X图表

具有给定拉伸的给定图形的扳手。

加薪

ValueError

如果给定的拉伸小于1。

笔记

此函数通过baswana和sen实现扳手算法，请参见 [1] .

该算法是一种随机拉斯维加斯算法：预期运行时间为o（k m），其中k=（Stretch+1）//2，m是g中的边数。返回的图始终是给定图中具有指定拉伸的扳手。对于加权图，扳手中的边数为o（k*n^（1+1/k）），其中k定义如上，n是g中的节点数。对于未加权图，边数为o（n^（1+1/k）+k n）。

工具书类

[1] S.Baswana，S.Sen.一种简单的线性时间随机算法，用于计算加权图中的稀疏扳手。随机结构。算法30（4）：532-563（2007）。