How To Detect A Loop In A Hierarchy Of Javascript Elements

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 = [ {

Solution 1:

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 = {}


functionvisit(vertex) {
    if (colors[vertex] === 'black') {
        // black = okreturn; 
    }

    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/

Solution 2:

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.

functionisCircular(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; }