# Developers Planet

Sefi Ninio February 2016

Using lodash, I have created an array of pairs, each representing source and destination of a link. So for a given path of links, I have:

``````[ [a, b], [a, c], [d, c] ]
``````

It is a given that the first element is the first link in the chain. I originally wanted to map the pairs into key/value map object and then go through the keys and/or values to find the head.

simplified algorithm:

``````keys.contains(a) || values.contains(a)
``````

if either returns true (excluding the pair itself, naturally), then it is not the head. So, starting with the first pair, keys.contains(a) || values.contains(a) returns true so it is not the head, and keys.contains(b) || values.contains(b) returns false - so it must be the head.

The problem: I can't map the pairs into an object, since there might be key/value duplicates that override each other.

i.e., for the examples above, the resulting object will be:

``````{
a: c,
d: c
}
``````

I know I can loop through them, however I am reluctant to do so many loops unless I have to...

Any ideas of a more efficient solution?

Ronald February 2016

I assume the source is the key and the destination is the value. The roots of your directed graph are those keys that do not occur as a value. (The leafs: vice versa).

`a` would be a root, as well as `d`. `b` and `c` are not. Your condition should be `keys.contains(a) && !values.contains(a)`.

You might not have a root at all though if the objects point to each other (`[ [a, b], [b, a] ]`) or if something points to itself (`[ [a, a] ]`).

Now if you eliminate the self references, you can collect the keys and the values. To get the roots you iterate over the keys and test if they aren't a value. To get the leafs, you iterate over the values and test if they aren't a key.

HTH, but I'm not sure I understood your question correctly.