Nicholas Kyriakides Nicholas Kyriakides - 2 months ago 9
Javascript Question

Discarding incoming nodes in a directed graph

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




Answer

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