javascript - 丢弃有向图中的传入节点

Question

我想丢弃有向图中的传入节点。

tl;dr(跳转到第 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。我现在想删除传入节点

现在我想删除所有 incoming 节点，只保留引用“朝向”相关节点的节点(因为缺少更好的词)，从 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));
          

Answer 1

假设您的图永远不会有分支(即一个节点导致两个节点)，您可以从源节点开始并继续向上查找每个子节点。

function removeIncoming(data, source){
    // keep track of the member we are looking for
    var target = source;
    // the resulting graph
    var result = [];
    // iterate through the data, looking for the target
    for(var i = 0; i < data.length; i++){
        // the object in the list
        var piece = data[i];
        // its properties id1 and id2
        var id1 = piece.id1;
        var id2 = piece.id2;

        // when we have found what we are looking for
        if(id1 === target){
            // look for its child
            target = id2;
            // start at the beginning
            i = -1;
            // and add the link to the resulting list
            result.push(piece);
        }
    }

    return result;
}

或者，对于分支节点，您可以跟踪数组中每个可能的节点，然后使用 indexOf 搜索它们。

function removeIncoming(data, source){
    // copy the data
    var dataCopy = Array.prototype.slice.call(data);
    // keep track of the members we are looking for
    var targets = [source];
    // the resulting graph
    var result = [];
    // iterate through the data, looking for the target
    for(var i = 0; i < dataCopy.length; i++){
        // the object in the list
        var piece = dataCopy[i];
        // its properties id1 and id2
        var id1 = piece.id1;
        var id2 = piece.id2;

        // when we have found what we are looking for
        if(targets.indexOf(id1) >= 0){
            // begin looking for its child
            targets.push(id2);
            // remove the node we just looked at
            dataCopy.splice(i, 1);
            // start at the beginning
            i = -1;
            // and add the link to the resulting list
            result.push(piece);
        }
    }

    return result;
}