javascript - 如何检查节点是否相关？如果有两个邻居，我如何只选择一个邻居？

Question

我在 D3 中有一个强制布局。

我有许多节点，这些节点通过链接将它们连接起来。我的问题是，如果节点满足特定条件，我想删除链接。

假设我有节点 A、B、C。

说这个波浪字符 - “~”表示已连接。

If (A~B && A~C && B~C){

DELETE THE A~C link. //which would leave A~B~C
}

我已经尝试过每个链接:

link.forEach(function{d){ ....

但我似乎无法理解我将如何执行逻辑。

我会遍历每个节点 3 次，检查 A~B、A~C、B~C，但如果我有 100 个节点，那将非常慢。

任何帮助将不胜感激:)

这是我当前的边/链接数组的样子:

edges = [
{
    "source": "A",
    "target": "B",
    "other information" : "randomstring",
    "other information" : "randomstring"
},
{
    "source": "B",
    "target": "C",
    "other information" : "randomstring",
    "other information" : "randomstring"
} // and so on ....
]

Answer 1

这是一个图论问题，我假设您想打破一个循环，这就是我要做的

给定一个图g，大小为n，阶数为m

1) 从 links 构建一个哈希表，它用一个链接映射两个节点(O(m) 如果哈希是在恒定时间内完成的)，例如

// a reference to the link itself (which can be an object or a dom node)
var hash = {}
links.each(function (d) {
  var u = d.source
  var v = d.target
  hash[u] = hash[u] || {}
  // again replace this with the dom node if you want
  hash[u][v] = d
})

2) 运行 dfs 查找后缘(更多信息请参见 an article I wrote 或使用快速谷歌搜索)，每当您找到后缘时，您将获得有关源/目标节点和循环长度的信息 O(n + m)

3) 如果循环长度为 3 或您的标准是什么，则删除链接，从链接中删除将花费 O(km)，其中 k 是数字找到的周期数

现在使用 d3，您可以简单地重新绑定(bind)新数据(删除一些链接)并重新呈现图形