5

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*
nanokozmos
  • 323
  • 1
  • 7
  • 14
  • 2
    The second example in the code: 2 -> 3 -> 1 -> 2. Isn't that a cycle? And the third example: 3 -> 1 -> 2 -> 4 -> 3. Isn't that a cycle? What is your definition of cycle? – trincot Feb 04 '21 at 16:51
  • Yes, second example has a cycle so it should return true instead of false but third example is not cycle. You can see the cyclic and acyclic graphs here: https://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acyclic/ – nanokozmos Feb 04 '21 at 17:06
  • 1
    the last is cyclic as well with `3 -> 1 -> 2 -> 4 -> 3` – Nina Scholz Feb 04 '21 at 17:10
  • 1
    @nanokozmos, if traveling from a node is visited again, the graph is cyclic. the third example visits 3 again. – Nina Scholz Feb 04 '21 at 17:26
  • Alright I have updated the examples – nanokozmos Feb 04 '21 at 17:59
  • The last one again has a cycle: `4 -> 5 -> 6 -> 4`. – trincot Feb 04 '21 at 18:17
  • @trincot Yes, that's why I commented this "return false but should return true" – nanokozmos Feb 04 '21 at 18:20
  • You might want to look at the algorithms at https://stackoverflow.com/q/583876/1243641. If possible, you also should consider a better data structure. `[[4,2], [2,3], [3,1], [1, 4]]`, an array containing all the (directed) edges would be much cleaner. – Scott Sauyet Feb 04 '21 at 19:20
  • "*I wrote this code*" - in your `Map`, the second edge 6->4 overwrite the first edge 6->3. A node must have multiple adjacencies, otherwise it's not a graph. "*Do I need to use graph algorithm?*" - yes. [There's plenty](https://en.wikipedia.org/wiki/Cycle_detection). – Bergi Feb 04 '21 at 19:21

2 Answers2

2

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; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

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
e.ad
  • 380
  • 2
  • 10