丢弃有向图中的传入节点

Question

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

tl;dr（跳转到第 3 部分）

我有一个图，我在该图上执行 BFS 以删除所有不相关的节点（相对于候选边）。

1。样本图表数据

假设这是一个图形数据结构：

其中： - id1 是 source，id2 是 target

      var links = [
        {id1: 1, id2: 2},
        {id1: 2, id2: 3},
        {id1: 9, id2: 3},
        {id1: 6, id2: 8},
        {id1: 3, id2: 4}
      ]

以上可视化：

2。我成功丢弃了不相关的 nodes/edges

我运行一个 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 节点，只保留引用 "towards" 相关节点的节点（因为缺少更好的词），从 edge=1

开始

例如：

      var links = [
        {id1: 1, id2: 2},
        {id1: 2, id2: 3},
        {id1: 9, id2: 3}, // remove this
        {id1: 3, id2: 4}
      ]

我该怎么做？

这是我目前用来删除不相关的 nodes/edges:

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;
}

丢弃有向图中的传入节点

Discarding incoming nodes in a directed graph

javascript

graph-theory

graph-algorithm

1。样本图表数据

2。我成功丢弃了不相关的 nodes/edges

3。我现在想删除传入节点