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).
id1
id2
var links = [
{id1: 1, id2: 2},
{id1: 2, id2: 3},
{id1: 9, id2: 3},
{id1: 6, id2: 8},
{id1: 3, id2: 4}
]
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}
]
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));
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;
}