How to detect circular references in JavaScript

Question

For example:

$ node
> var x = {}
undefined
> x.x = x
{ x: [Circular] }

Wondering the sort of structures are they using to accomplish this, because it's not encoded directly into what I just did. It seems like they would do something like:

var graph = new Graph(object)
graph.detectCircularReferences()

And then it would get them, but not sure how that works. Hoping to learn how to implement that.

Possible duplicate of [Best algorithm for detecting cycles in a directed graph](https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph) — Robby Cornelissen, Dec 21 '17 at 03:25
See [here](https://github.com/nodejs/node/blob/3fe165ace6723b1446994574a5197bb70d9a6c72/lib/util.js#L186) and [here](https://github.com/nodejs/node/blob/3fe165ace6723b1446994574a5197bb70d9a6c72/lib/util.js#L168). They basically bail out when trying to JSON.stringify a circular object and it raises an exception — Oluwafemi Sule, Dec 21 '17 at 03:27
You could have a recursive function that push references of objects it encounter into an array, and for each new object it checks if its reference already encountered (exist in the array) or not. — ibrahim mahrir, Dec 21 '17 at 04:00
@ibrahimmahrir It would be much better to use a `Set` (constant time membership lookup) instead of an array, but otherwise this is the way to go. — Diasiare, Dec 21 '17 at 15:03

score 2 · Accepted Answer · answered Dec 22 '17 at 11:53

Taking into an account the ideas from the comments I came to this function. It traverses the passed object (over arrays and object) and returns an array of paths that point to the circular references.

// This function is going to return an array of paths
// that point to the cycles in the object
const getCycles = object => {
    if (!object) {
        return;
    }

    // Save traversed references here
    const traversedProps = new Set();
    const cycles = [];

    // Recursive function to go over objects/arrays
    const traverse = function (currentObj, path) {
        // If we saw a node it's a cycle, no need to travers it's entries
        if (traversedProps.has(currentObj)) {
            cycles.push(path);
            return;
        }

        traversedProps.add(currentObj);

        // Traversing the entries
        for (let key in currentObj) {
            const value = currentObj[key];
            // We don't want to care about the falsy values
            // Only objects and arrays can produce the cycles and they are truthy
            if (currentObj.hasOwnProperty(key) && value) {
                if (value.constructor === Object) {
                    // We'd like to save path as parent[0] in case when parent obj is an array
                    // and parent.prop in case it's an object
                    let parentIsArray = currentObj.constructor === Array;
                    traverse(value, parentIsArray ? `${path}[${key}]` : `${path}.${key}`);

                } else if (value.constructor === Array) {
                    for (let i = 0; i < value.length; i += 1) {
                        traverse(value[i], `${path}.${key}[${i}]`);
                    }
                }

                // We don't care of any other values except Arrays and objects.
            }
        }
    }

    traverse(object, 'root');
    return cycles;
};

Then you can test it like this:

// Making some cycles.
const x = {};
x.cycle = x;
const objWithCycles = {
    prop: {},
    prop2: [1, 2, [{subArray: x}]]
};
objWithCycles.prop.self = objWithCycles;

console.log(getCycles(objWithCycles));

It produces the following output which is a list of cycles in the object:

[ 'root.prop.self', 'root.prop2[2][0].subArray.cycle' ]

How to detect circular references in JavaScript

1 Answers1