在不创建孤儿的情况下断开网络链接？

Question

我有一个 10x10 节点的网格，其中所有相邻节点都被 linked 以创建 180 links 的图形 - 即：

我希望做的是创建一个程序来破坏这些 link 中的 x%，但重要的是在不创建任何孤立子图的情况下这样做——也就是说，100 个节点中的任何一个都保留可从所有其他 99 个节点访问 - 即

我最初（天真地）认为我可以做如下事情：

ask n-of 45 nodes with [count my-links > 1] 
[
    ask one-of my-links [die]
]

但是，这不会阻止 sub-graphs 从主图中孤立 - 即

另一种选择可能是重复要求单个 link 死亡，然后检查图形总数不超过 1 - 如果超过 1，则重新创建 link 并选择另一个来破坏.但是，（1）这看起来不是特别优雅； (2) 我一直无法找到一种方法来使用内置 link 或 nw 程序来计算不同图形的数量。

我确实认为我的部分问题是不知道这些 subgraphs/isolates/cliques 等的正确术语...

如果有人对如何做到这一点有任何想法（或者可以纠正我对图论术语的严重不足的理解），我们将不胜感激。

Answer 1

对于您想到的解决方案，您可以使用 nw 扩展来检查您刚刚断开连接的节点之间是否仍然存在路径，方法是检查 nw:distance-to returns false 或一个数字。

或者，您可以计算 connected components 的数量。

我认为删除 link 并测试连通性是一个非常合理的方法。您实施的任何算法都必须笨拙地假装 link 无论如何都不存在，因此可能比仅删除该东西更复杂。

编辑：为远程版本添加代码以澄清：

to break-link
  let break-candidate one-of links
  let end-one [end1] of break-candidate
  let end-two [end2] of break-candidate
  ask break-candidate [die]
  if [nw:distance-to end-two] of end-one = false [
    ask end-one [ create-link-with end-two ]
    break-link
  ]
end

不确定这个版本或 nw:weak-component-cluster 版本是否会更快。这可能取决于网络的规模。

Answer 2

非常感谢您对 nw:weak-component-clusters 的提示 - 我不知道这一点。

我现在已经实现了以下简单的递归过程，它将杀死一个 link，如果 link 拆分了图形，则重新创建它并调用该过程。这对我想做的事情很有效。但是请注意，如果您运行的次数足够多，您最终将陷入递归循环，因为在不拆分图形的情况下将没有更多的 link 可以中断，并且该过程将继续调用自身。

to breakLink
  let breakCandidate one-of links  
  let end1Candidate [end1] of breakCandidate 
  let end2Candidate [end2] of breakCandidate 

  ask breakCandidate [die]
  if (length nw:weak-component-clusters > 1) 
  [ 
    ask end1Candidate 
    [
      create-link-with end2Candidate 
      breakLink
    ] 
  ]
end

干杯

在不创建孤儿的情况下断开网络链接？

Breaking network links without creating orphans?

netlogo