JavaScript Detect is Cyclic in an array of objects

Issue

I have an array of Javascript objects as follows

a=[
  {id:1, parentId:2},
  {id:2, parentId:3},
  {id:3, parentId:4},
  {id:4, parentId:1},
  {id:5, parentId:5}
];

I would like to detect in this array
if any object refers to itself directly (5->5) or if refers to itself by other parents like 1->2->3->4->1

what is the best way to write it?

PS. There is another question like this one but it is not answered the question. the accepted answer is about a graph and it returns color coding,
How to detect a loop in a hierarchy of javascript elements but mine is parentId

my expected behaviour is:
false, 5->5 and 1->2->3->4->1
or simply false, neighter colour coding nor for graph 🙂

Solution

This one is non-recursive. Not most efficient, but checks items one by one – looking up the parent chain until found a match or no parent found. Then moving to next item.

Edit: Need of course to check against all items along the way of the chain (not just first) to prevent infinite loops in case of (1->2->2).

var a = [
  {id:1, parentId:2},
  {id:2, parentId:2},
  {id:3, parentId:4},
  {id:4, parentId:7},
  {id:5, parentId:6}
];

function search_id(arr, id) {
  return arr.find(item => item.id === id)
}

function is_array_cyclic(arr) {
  for (var i = 0; i < arr.length; i++) {
    var item = arr[i];
    var seen = [item.id]

    while (true) {
      var parent = search_id(arr, item.parentId);
      if (parent === undefined) {
        break;
      }
      if (seen.indexOf(parent.id)>-1) {
        // cyclical
        return true;
      }
      seen.push(parent.id);
      item = parent;
    }
  }
  return false;
}

console.log(is_array_cyclic(a))

Answered By – IT goldman

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply

(*) Required, Your email will not be published