Algorithm for determining equality of circular data structures in JavaScript

Question

var ones = [1];
ones[1] = ones;
ones;
// => [1, [1, [1, [1, [1, ...]]]]]

var ones_ = [1];
ones_[1] = ones_;
ones_;
// => [1, [1, [1, [1, [1, ...]]]]]

How does one determine that ones and ones_ are equal? Is there an algorithm which handles circular structures such as the above?

Answer 1

A basic way to solve this problem is to note that if, during a recursive comparison, we ever end up again comparing the same pair of objects that we're already comparing, then we may simply assume that they're equal. This works because, if they're not equal after all, then the comparison that is already in progress will eventually find some difference between them.

Thus, we may simply start with a basic recursive comparison function, and add a stack of objects being currently compared:

function isEqual (a, b) {
    var stack = [];
    function _isEqual (a, b) {
        // console.log("->", stack.length);
        // handle some simple cases first
        if (a === b) return true;
        if (typeof(a) !== "object" || typeof(b) !== "object") return false;
        // XXX: typeof(null) === "object", but Object.getPrototypeOf(null) throws!
        if (a === null || b === null) return false;
        var proto = Object.getPrototypeOf(a);
        if (proto !== Object.getPrototypeOf(b)) return false;
        // assume that non-identical objects of unrecognized type are not equal
        // XXX: could add code here to properly compare e.g. Date objects
        if (proto !== Object.prototype && proto !== Array.prototype) return false;

        // check the stack before doing a recursive comparison
        for (var i = 0; i < stack.length; i++) {
            if (a === stack[i][0] && b === stack[i][1]) return true;
            // if (b === stack[i][0] && a === stack[i][1]) return true;
        }

        // do the objects even have the same keys?
        for (var prop in a) if (!(prop in b)) return false;
        for (var prop in b) if (!(prop in a)) return false;

        // nothing to do but recurse!
        stack.push([a, b]);
        for (var prop in a) {
            if (!(_isEqual(a[prop], b[prop]))) {
                stack.pop();
                return false;
            }
        }
        stack.pop();
        return true;
    }
    return _isEqual(a, b);
}

// TEST CASES:

var ones = [1]; ones[1] = ones;
var foo = [1]; foo[1] = [1, foo];
var bar = [1]; bar[1] = [1, ones];
console.log("ones == foo:", isEqual(ones, foo));
console.log("ones == bar:", isEqual(ones, bar));
console.log("foo == bar:", isEqual(foo, bar));

var obj = {}; obj["x"] = obj; obj["y"] = {obj};
console.log("obj == obj[x]:", isEqual(obj, obj["x"]));
console.log("obj != obj[y]:", !isEqual(obj, obj["y"]));

var seven = []; seven[0] = [[[[[[seven]]]]]];
var eleven = []; eleven[0] = [[[[[[[[[[eleven]]]]]]]]]];
console.log("seven == eleven:", isEqual(seven, eleven));
console.log("[seven] == [eleven]:", isEqual([seven], [eleven]));
console.log("[seven] == seven:", isEqual([seven], seven));
console.log("[seven] == [[[eleven]]]:", isEqual([seven], [[[eleven]]]));

Note that a lot of the complexity in the code above is due to it trying to accept and (more or less) gracefully handle any mixture of different kinds of JavaScript values, including primitives, null values, arrays, plain objects and all the other miscellaneous things a JS variable can contain. If you know your inputs can only contain a limited range of data types, then it may be possible to simplify this code considerably.

Ps. Due to the stack comparison, the runtime of this code can be up to O(nd), where n is the number of nodes in the trees that need to be compared (which can be more than expected; for example, comparing the objects seven and eleven in the snippet above takes 77 recursive calls) and d is the depth of the stack (which, in this case, also gets up to 77). In ES2015, a potentially useful optimization could be to use a Map of previously seen objects to reduce the stack lookup from O(d) to effectively O(1). If we expected the data structures being compared to generally have a lot of repetitive branches containing references to the same objects, it might even be useful to expand this into a general cache of previously seen objects that we've already found to be equal.

Answer 2

You can 'decycle' an object by iterating it and replacing already seen objects with "pointers" (=indexes in some array). Once you get decycled structs, simply serialize them and compare as strings:

let encode = function (x) {

    function _enc(x, lst) {
        if (typeof x !== 'object')
            return x;

        let i = lst.indexOf(x);
        if (i >= 0)
            return {'->': i};
        lst.push(x);

        let y = {};
        for (let k of Object.keys(x))
            y[k] = _enc(x[k], lst)

        return y;
    }

    return JSON.stringify(_enc(x, []));
};

//////

let ones = [1];
ones[1] = ones;

let ones_ = [1];
ones_[1] = ones_;

console.log(encode(ones) === encode(ones_))

// more interesting example

a = {
    b: {
        c: 123
    }
};

a.b.d = a;
a.x = [9, a.b];


a2 = {
    b: {
        c: 123
    }
};

a2.b.d = a2;
a2.x = [9, a2.b];

console.log(encode(a) === encode(a2))