networkx.algorithms.sparsifiers.spanner

spanner(G, stretch, weight=None, seed=None)[源代码]

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

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

参数
  • GNETWorkX图 )--无向简单图。

  • 伸展浮动 )--扳手的伸长度。

  • 重量对象 )--要用作距离的边属性。

  • seedinteger, random_state, or None (default) )--随机数生成状态的指示器。见 Randomness .

返回

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

返回类型

NetworkX graph

引发

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