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

Question

我在D3中有一个力布局.

我有很多节点,链接连接起来.我的问题是,如果节点符合某个标准,我想删除链接.

假设我有节点A,B,C.

说这个tilda字符 - '〜'表示已连接.

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个节点会非常慢.

任何帮助,将不胜感激 :)

以下是我当前的edge/links数组的外观:

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 查找后缘（更多信息请参见我写的文章或通过快速谷歌搜索），每当您找到后缘时，您都会获得有关源/目标节点和周期长度的信息O(n + m)

3) 如果循环长度为 3 或无论您的标准是什么，则删除链接，从链接中删除将需要O(km)找到k的循环数

现在使用 d3，您可以简单地重新绑定新数据（删除一些链接）并重新渲染图形