How to check if a graph is cyclic in JavaScript

user_1900131 0
Viewed 676

I would like to check if a graph is cyclic in JavaScript. I have two arrays and each item in first array has a relation with (same index) item of second array.

Let's give an example: first = [4, 2, 3, 1] second = [2, 3, 1, 4]

So there are relations between 4=>2, 2=>3, 3=>1 and 1=4. When you look at the graph, you can see that it is cyclic. enter image description here

I wrote this code but it is returning false although it should return true for the following input;

first = [2, 1, 3, 4] second = [3, 2, 1, 3]

How can I achieve this? Do I need to use graph algorithm?

function ifGraphCyclic(first, second) {
    let nodes = new Map();
    let unique = [];
    for (let i = 0; i < first.length; i++) {
        nodes.set(first[i], second[i]);
    }

    for (let value of nodes.values()) {
        unique.push(nodes.get(value));
    }

    if (first.length === new Set(unique).size) {
        return true;
    }

    return false;
}

console.log(ifGraphCyclic([4, 2, 3, 1], [2, 3, 1, 4])) // return true
console.log(ifGraphCyclic([2, 1, 3, 4], [3, 2, 1, 3])) // *return false but should return true*
console.log(ifGraphCyclic([1, 2, 2, 4, 4, 5, 6], [2, 3, 4, 5, 6, 6, 3])) // return false
console.log(ifGraphCyclic([1, 2, 2, 4, 5, 6, 6], [2, 3, 4, 5, 6, 3, 4])) // *return false but should return true*
graph data-structures arrays algorithm javascript
2 Answers

You could collect all relations of the nodes in an object with arrays and check if a node is seen.

function ifGraphCyclic(first, second) {
    const nodes = first.reduce((r, v, i) => ((r[v] = r[v] || []).push(second[i]), r), {});

    for (let n of first) {
        const queue = [[n, []]];

        while (queue.length) {
            const [node, seen] = queue.shift();
            if (!(node in nodes)) continue;
            if (seen.includes(node)) {
                console.log(...seen, n);
                return true;
            }
            seen.push(node);
            queue.push(...nodes[node].map(a => [a, [...seen]]));
        }
    }

    return false;
}

console.log(ifGraphCyclic([4, 2, 3, 1], [2, 3, 1, 4])); // 4 2 3 1 4
console.log(ifGraphCyclic([2, 1, 3, 4], [3, 2, 1, 3])); // 2 3 1 2
console.log(ifGraphCyclic([3, 4, 2, 1], [1, 3, 4, 2])); // 3 1 2 4 3
console.log(ifGraphCyclic([3, 4, 2, 1], [1, 3, 4, 5])); // 2 4 3 1 5
console.log(ifGraphCyclic([1, 2, 2, 4, 4, 5, 6], [2, 3, 4, 5, 6, 6, 3]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_14476750

Another idea to look of those two arrays as a permutation of the numbers 1,..,n: (which means that f(first[i]) = second[i]))

Hence, in the example of: first = [3, 4, 2, 1] second = [1, 3, 4, 2] we have the following function:

f(3)=1, f(4)=3, f(2)=4, f(1)=2

Then, if a cycle for you is a loop that its length is smaller than n, then a straight forward way to check this is:

(0) define a function F as above
(1) Initialize array of n numbers, named A
(2) for i in A: 
(2.1) count = 0, tmp = i
(2.2) while (count < n):
(2.2.1) tmp = F(tmp)
(2.2.2) if tmp == i: set A[i] to 1 (break..)
(3) if your arrays is only zeros, then there is no cycle of length under than n
user_97151850
Related