How to detect a loop in a hierarchy of javascript elements

Question

I have a list of elements, each has an ID and a parent ID. What I want to do is detect when there is a loop in this 'hierarchy', and show which ID starts the loop.

list = [
  {
    id: '1',
    parent: '2'
  },
  {
    id: '2',
    parent: '3'
  },
  {
    id: '3',
    parent: '4'
  },
    {
    //This id is causing the loop
    id: '4',
    parent: '1'
  }
]

I have tried this to build the tree, which works when there's no loop, but does not work with a loop:

function treeify(list, idAttr, parentAttr, childrenAttr) {
    if (!idAttr) idAttr = 'id';
    if (!parentAttr) parentAttr = 'parent';
    if (!childrenAttr) childrenAttr = 'children';
    var treeList = [];
    var lookup = {};
    list.forEach(function(obj) {
        lookup[obj[idAttr]] = obj;
        obj[childrenAttr] = [];
    });
    list.forEach(function(obj) {
        if (obj[parentAttr] != null) {
            lookup[obj[parentAttr]][childrenAttr].push(obj);
        } else {
            treeList.push(obj);
        }
    });
    return treeList;
};

I also cannot detect when there is a loop.

I'd like to return the ID of the element that caused the loop to allow me to fix the data behind it.

so you have a structure describing 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1 and you want to find the first element that closes the circular loop, right? — VLAZ
– VLAZ, Commented Mar 25, 2019 at 13:33
The element that causes the loop as you've defined it is dependent on where you start in the loop. Also, that if there are multiple loops, or elements that loop to themselves? — ControlAltDel
– ControlAltDel, Commented Mar 25, 2019 at 13:37
If cycle detection is what you need, why not go with an algorithm like Floyd Cycle Detection — Ahmed Bajra
– Ahmed Bajra, Commented Mar 25, 2019 at 13:50

georg · Accepted Answer · 2019-03-25 16:37:59Z

2

You can apply white-grey-black coloring to detect nodes that are (re)visited while visiting their descendants (I've simplified your graph to a list of parent-child pairs):

graph = [
    [2, 1],
    [3, 2],
    [1300023, 3],
    [1, 1300023],
];


colors = {}


function visit(vertex) {
    if (colors[vertex] === 'black') {
        // black = ok
        return; 
    }

    if (colors[vertex] === 'grey') {
        // grey = visited while its children are being visited
        // cycle!
        console.log('cycle', colors); 
        return; 
    }

    // mark as being visited
    colors[vertex] = 'grey';

    // visit children
    graph.forEach(edge => {
        if (edge[0] === vertex)
            visit(edge[1]);
    });

    // mark as visited and ok
    colors[vertex] = 'black'

}

visit(1)

A nice illustration of this approach: https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/

edited Mar 25, 2019 at 16:37

answered Mar 25, 2019 at 14:05

georg

216k57 gold badges324 silver badges401 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user1320453 Over a year ago

Thanks - however this does not appear to work for larger ids such as 1300023.

georg Over a year ago

@user1320453: I see no problem with "1300023" specifically, but if your ids are larger than javascript number range, just use strings.

georg Over a year ago

@user1320453: visit('123')

georg Over a year ago

@user1320453: no prob ;)

user1320453 Over a year ago

Having implemented this, I can't see that it would return the id of the 'issue' element. After running this with a much larger list of ids, it does return an object in the console, but all elements in the object are tagged as 'black'

|

Nina Scholz · Accepted Answer · 2019-03-25 14:08:52Z

0

You could collect all nodes and the childrens in object and filter all nodes by taking an array of visited nodes.

The infinite array contains all nodes which causes a circular reference.

function isCircular(id, visited = []) {
    return visited.includes(id)
        || Object.keys(links[id]).some(k => isCircular(k, visited.concat(id)));
}
var list = [{ id: '1', parent: '2' }, { id: '2', parent: '3' }, { id: '3', parent: '4' }, { id: '4', parent: '1' }],
    links = {},
    infinite = [];
    
list.forEach(({ id, parent }) => {
    links[parent] = links[parent] || {};
    links[parent][id] = true;
});


infinite = list.filter(({ id }) => isCircular(id));

console.log(links);
console.log(infinite);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Mar 25, 2019 at 14:08

answered Mar 25, 2019 at 13:57

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

1 Comment

user1320453 Over a year ago

Thanks very much for your answer - although this works, it doesn't appear to be able to handle where a parent id is not defined, or if parent id is used twice - both of which are legitimate here.

Collectives™ on Stack Overflow

How to detect a loop in a hierarchy of javascript elements

2 Answers 2

6 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related