我希望能够在有向图中丢弃传入节点。
简短总结(跳转到第3部分)
我有一个图,在这个图上执行BFS以删除所有与候选边无关的节点。
1. 样本图数据
假设这是一个图数据结构:
其中:
- id1
是源,id2
是目标
var links = [
{id1: 1, id2: 2},
{id1: 2, id2: 3},
{id1: 9, id2: 3},
{id1: 6, id2: 8},
{id1: 3, id2: 4}
]
上述结构的可视化:
2. 我成功地丢弃了不相关的节点/边
我运行了一个BFS算法(如下所示的函数),以丢弃所有相对于edge = 1
无关的节点,结果如下:
var links = [
{id1: 1, id2: 2},
{id1: 2, id2: 3},
{id1: 9, id2: 3},
// {id1: 6, id2: 8}, Discarded (no connection with 1)
{id1: 3, id2: 4}
]
上述的可视化效果如下:
3. 我现在想要删除入节点
现在我想要删除所有的入节点,只保留从edge=1
开始“指向”相关节点的节点(用缺乏更好的词汇来描述)。
例如:
var links = [
{id1: 1, id2: 2},
{id1: 2, id2: 3},
{id1: 9, id2: 3}, // remove this
{id1: 3, id2: 4}
]
我该怎么做呢?
这是我目前用来删除不相关节点/边的方法:
var filterUnrelated = function(data, candidateId) {
var toTest = [candidateId];
var connected = [];
function addToTest(node) {
//If the node is not already set to be tested, and have not been tested
if (connected.indexOf(node) < 0 && toTest.indexOf(node) < 0) {
toTest.push(node);
}
}
function findAllConnectedNode(node) {
//We only test connected node, so this node should be connected
connected.push(node);
//Find every link with that node
data.filter(function(d) {
return (d.id1 === node) || (d.id2 === node);
//Add the linked node to test
}).map(function(d) {
if (d.id1 === node) {
addToTest(d.id2);
}
else { //d.id1 === node
addToTest(d.id1);
}
});
}
while (toTest.length > 0) {
findAllConnectedNode(toTest.shift());
}
return data.filter(function(d) {
return (connected.indexOf(d.id1) >= 0 ||
connected.indexOf(d.id2) >= 0);
})
}
var links = [
{id1: 1, id2: 2},
{id1: 2, id2: 3},
{id1: 9, id2: 3},
{id1: 6, id2: 8},
{id1: 3, id2: 4}
]
console.log(filterUnrelated(links, 1));
id1/id2
应该颠倒 - 即使用indexOf(id2)
和push(id1)
。 - nicholaswmin