Sefi Ninio February 2016

Find head of link chain

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?

Answers


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.

Post Status

Asked in February 2016
Viewed 1,606 times
Voted 14
Answered 1 times

Search




Leave an answer