Как обнаружить петлю в иерархии элементов JavaScript - PullRequest
Новая
       12

Как обнаружить петлю в иерархии элементов JavaScript

0 голосов
/ 25 марта 2019

У меня есть список элементов, у каждого есть идентификатор и родительский идентификатор.Я хочу определить, когда в этой «иерархии» есть цикл, и показать, какой идентификатор запускает цикл. 

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

Я пытался построить дерево, которое работает, когда цикла нет., но не работает с циклом: 

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

Я также не могу определить, когда есть цикл.

Я хотел бы вернуть идентификатор элемента, который вызвал цикл кпозвольте мне исправить данные за ним.

Ответы [ 2 ]

1 голос
/ 25 марта 2019

Вы можете применить бело-серо-черную раскраску, чтобы обнаружить узлы, которые (повторно) посещались при посещении их потомков (я упростил ваш график до списка пар родитель-потомок): 

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)

Хорошая иллюстрация этого подхода: https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/

0 голосов
/ 25 марта 2019

Вы можете собрать все узлы и дочерние объекты в объекте и отфильтровать все узлы, взяв массив посещенных узлов.

Бесконечный массив содержит все узлы, которые вызывают циклическую ссылку. 

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; }
...