## 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:

### 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:

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

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

## Answers to Discarding incoming nodes in a directed graph ( 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.

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.