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

Question

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

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

Есть ли другой способ сделать его более производительным. Я думаю, что использование JSON.stringify итеративно с блоком try catch также может быть подходящим способом. но я не уверен, что он будет более / менее производительным.

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