Discarding incoming nodes in a directed graph

Question

I'd like to discard incoming nodes in a directed graph.

tl;dr (jump to section 3)

I have a graph on which I perform a BFS to remove all unrelated nodes (relative to a candidate edge).

1. Sample graph data

Let this be a graph data structure:

Where: - id1 is the source, id2 is the target

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

Visualisation for above:

Graph visualisation for above structure

2. I successfully discard unrelated nodes/edges

I run a BFS (function below) to discard all unrelated nodes relative to edge=1 which yields this:

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

Visualisation for the above:

Graph visualisation for above structure

3. I now want to remove incoming nodes

Now I'd like to remove all incoming nodes as well and keep only nodes that reference "towards" a related node (for lack of a better word), starting from edge=1

For example:

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

Graph visualisation of desired result, showing severed link

How can I go about this?

Here's what I currently use to remove unrelated 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));
          


Show source
| javascript   | graph-algorithm   | graph-theory   2016-09-30 02:09 1 Answers

Answers ( 1 )

  1. 2016-09-30 05:09

    Assuming that your graph will never have branches (i.e. one node leading to two nodes), you can start at the source node and continue to look upwards for each child node.

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

    Alternatively, with branching nodes, you can keep track of each of the possible nodes in an array, and then use indexOf to search for them.

    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;
    }
    
◀ Go back