Convert entity relation array to object in Javascript

Given an array with two entries, parent and child relation, convert the array to a relation tree object (parent -> child -> grandchild) in JavaScript.

The input array will contain relations for many ancestries in random order, We must return the array of strings representing different relationships.

For example, in the below case, the topmost ancestor is an animal.

Example

Input:
[
  ["lion", "cat"],
  ["cat", "mammal"],
  ["dog", "mammal"],
  ["mammal", "animal"],
  ["fish", "animal"],
  ["shark", "fish"],
];

Output:
[
  "animal -> mammal -> cat -> lion",
  "animal -> mammal -> cat",
  "animal -> mammal -> dog",
  "animal -> mammal",
  "animal -> fish",
  "animal -> fish -> shark"
]

Convert relation array to object tree in JavaScript.

The first thing we have to do is to convert the array to an object of the parent-child relationship for better processing.

// aggregate parent / child relation
const aggregate = (arr) => {
  
  // aggregate the values for easier processing
  return arr.reduce((a, b) => {
    const [child, parent] = b;
    
    // aggregating on child
    a[child] = parent;
    
    return a;
  }, {});
}

const arr = [
  ["lion", "cat"],
  ["cat", "mammal"],
  ["dog", "mammal"],
  ["mammal", "animal"],
  ["fish", "animal"],
  ["shark", "fish"],
];

console.log(aggregate(arr));

/*
{
  "lion": "cat",
  "cat": "mammal",
  "dog": "mammal",
  "mammal": "animal",
  "fish": "animal",
  "shark": "fish"
}
*/

We have aggregated the values on the child as one child will have only one parent, this way a single key-value pair is formed which is faster in forming relationships.

Now, all we have to do is recursively keep on traversing this map and form the relation string. For this, we will get the value of the current key and recursively call the same function with this value and the map to get its ancestry and so on.

// for a relationship from the aggregated value
const convert = (obj) => {
  return Object.keys(obj).reduce((a, b) => {
    a.push(getKey(obj, b));
    return a;
  }, []);
}

// helper function to form the string
// till the last hierarchy
const getKey = (obj, key) => {
  // access the
  const val = obj[key];
  
  // the formation can be reversed by chaning the order of the keys
  // child -> parent | parent -> child
  if(val in obj){
    return getKey(obj, val) + " -> " + key;
  }else{
    return val + " -> " + key;
  }
}

Input:
// map after aggregation
const map = {
  "lion": "cat",
  "cat": "mammal",
  "dog": "mammal",
  "mammal": "animal",
  "fish": "animal",
  "shark": "fish"
};

console.log(convert(map));

Output:
[
  "animal -> mammal -> cat -> lion",
  "animal -> mammal -> cat",
  "animal -> mammal -> dog",
  "animal -> mammal",
  "animal -> fish",
  "animal -> fish -> shark"
]

Complete code

const ancestry = (arr) => {

  // aggregate parent / child relation
  const aggregate = (arr) => {

    // aggregate the values for easier processing
    return arr.reduce((a, b) => {
      const [child, parent] = b;

      // aggregating on child
      a[child] = parent;

      return a;
    }, {});
  };
  
  // for a relationship from the aggregated value
  const convert = (obj) => {
    return Object.keys(obj).reduce((a, b) => {
      a.push(getKey(obj, b));
      return a;
    }, []);
  };

  // helper function to form the string
  // till the last hierarchy
  const getKey = (obj, key) => {
    // access the
    const val = obj[key];

    // the formation can be reversed by chaning the order of the keys
    // child -> parent | parent -> child
    if(val in obj){
      return getKey(obj, val) + " -> " + key;
    }else{
      return val + " -> " + key;
    }
  };
  
  // get the aggregated map
  const aggregatedMap = aggregate(arr);
  
  // return the ancestory 
  return convert(aggregatedMap);

};

Input:
const arr = [
  ["lion", "cat"],
  ["cat", "mammal"],
  ["dog", "mammal"],
  ["mammal", "animal"],
  ["fish", "animal"],
  ["shark", "fish"],
];

console.log(ancestry(arr));

Output:
[
  "animal -> mammal -> cat -> lion",
  "animal -> mammal -> cat",
  "animal -> mammal -> dog",
  "animal -> mammal",
  "animal -> fish",
  "animal -> fish -> shark"
]