Найти циклическую зависимость без использования графика в Map of array

У меня есть объект, подобный следующему:

var myMap = {
    v1: ['v2', 'v4', 'v5'],
    v2: ['x', 'v4', 'y'],
    v3: ['v2', 'v4', 'v5'],
    v4: ['e', 'v1', 'v5'],
    v5: ['v2', 'v4', 'v3'],
};

Я должен найти карту объектов циклическим без преобразования его в граф.

Как вывод будет выглядеть следующим образом:

var myDep = {
    v1: {isCyclic: true, cyclicDependents: ['v4']},
    v2: {isCyclic: false, cyclicDependents: []},
    v3: {isCyclic: true, cyclicDependents: ['v5']},
    v4: {isCyclic: true, cyclicDependents: ['v1', 'v5']},
    v5: {isCyclic: true, cyclicDependents: ['v4', 'v3']},
};

Я пытался со следующим:

 var graph = { v1: ["v2", "v4", "v5"], v2: ["x", "v4", "y"], v3: ["v2", "v4", "v5"], v4: ["e", "v1", "v5"], v5: ["v2", "v4", "v3"] }; var myDep = { v1: { isCyclic: false, cyclicDependents: [] }, v2: { isCyclic: false, cyclicDependents: [] }, v3: { isCyclic: false, cyclicDependents: [] }, v4: { isCyclic: false, cyclicDependents: [] }, v5: { isCyclic: false, cyclicDependents: [] } }; myDep = Object.keys(graph).reduce((a, b) => { graph[b] && graph[b].forEach(d => { if (graph[d] && ~graph[d].indexOf(b)) { a[b].isCyclic = true; a[b].cyclicDependents.push(d); } }); return a; }, myDep); console.log(myDep); 

Всего 1 ответ


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

Результатом является объект со стартовыми ключами и их узлами, которые являются циклическими. Требуемый формат оставлен читателю в качестве упражнения.

 function isCyclic(node, target, [...visited] = []) { if (node === target) return true; if (visited.includes(node) || !myMap[node]) return false; visited.push(node); return myMap[node].some(n => isCyclic(n, target, visited)); } var myMap = { v1: ['v2', 'v4', 'v5'], v2: ['x', 'v4', 'y'], v3: ['v2', 'v4', 'v5'], v4: ['e', 'v1', 'v5'], v5: ['v2', 'v4', 'v3'] }, result = {}; Object.entries(myMap).forEach(([k, v]) => result[k] = v.filter(n => isCyclic(n, k))); console.log(result); 
 .as-console-wrapper { max-height: 100% !important; top: 0; } 


Есть идеи?

10000