Find cyclic dependency without using graph in Map of array

Question

I have an object like following:

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

I have to find map of entities cyclic without converting it to graph.

Like output will be like following:

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']},
};

I tried with following:

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

Is there any other way to make it more performant. I think using JSON.stringify in itrative manner with try catch block might be also a way. but I'm not sure it will be more/less performant.

Hello, why are you putting a constraint on your problem? Why do you say "without converting it to graph"? Is there a reason you don't want to convert to a graph first? Do you already know how to do it from a graph and are looking for a different approach? — Ray Toal, May 16 '19 at 19:08
@Ray Toal, Thanks for asking. Yes, I have a little Idea to do it with Graph. I don't want to use Graph as it will introduce extra LOC(Definition of graph, node etc.) and in my code it is needed only once so want to finish it in low LOC to increase code readability. — Akhilesh Kumar, May 16 '19 at 19:13

score 4 · Accepted Answer · answered May 16 '19 at 19:56

You could take a function for checking the cyclic nature and store visited nodes to prevent to loop forever.

The result is an object with starting keys and their nodes which are cyclic. The wanted format is left as exercise to the reader.

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

Find cyclic dependency without using graph in Map of array

1 Answers1