Workaround for serializing a graph-theoretic tree with JSON?

Question

I have an array of nodes. Each node has an array of children and a pointer to its parent. I would like to serialize it using JSON.stringify, but with the parent pointers I obviously end up with circular references, and JSON throws an exception. What can I do to work-around the circular references and serialize with JSON?

Related question: Chrome sendrequest error: TypeError: Converting circular structure to JSON

i've an idea how to handle this -- but gimme some time... – TheHe Aug 28 '12 at 00:18 — TheHe, Aug 28 '12 at 00:18

score 1 · Answer 1 · answered Aug 28 '12 at 02:42

have a try -- usage-information and demo-data are at the buttom:

// class
var Decircularizer = function() {};
// class contents
Decircularizer.prototype = {
    curId: 0x01,
    idField: '{`id´}',
    _getNewId: function() {
        return this.curId++;
    },
    _getVisited: function(obj) {
        return obj[''+this.idField];
    },
    _setVisited: function(obj) {
        return (obj[''+this.idField] = this._getNewId());
    },
    _removeVisited: function(obj){
        delete obj['' + this.idField];
    },
    decycle: function(obj, depth) {
        var $this = this;
        depth = depth || 0;
        var key = this._getVisited(obj);
        if (key > 0x00) return this.idField + key;

        if(!jQuery.isPlainObject(obj))
            return obj;

        key = this._setVisited(obj);
        jQuery.each(obj, function(prop, val){
            if (prop == $this.idField) return;
            if (jQuery.isFunction(obj[prop])) delete obj[prop];
            else obj[prop] = $this.decycle(val, depth + 1);
        });
        return obj;
    },
    recycle: function(obj){
        var $this = this;
        var ids = {};
        this._searchIds(obj, ids);
        return this._recycle(obj, ids);
    },
    _recycle: function(obj, ids){
        var $this = this;
        if(!jQuery.isPlainObject(obj))
            return obj;
        jQuery.each(obj, function(prop, val){
            var xval = ids[val];
            if(xval)
                obj[prop] = xval;
            else
                obj[prop] = $this._recycle(val, ids);
        });
        return obj;
    },
    _searchIds: function(obj, ids){
        var $this = this
        var ids = ids || {};
        var key = this._getVisited(obj);

        if(key > 0x00) {
            ids[this.idField + key] = obj;
            $this._removeVisited(obj);
        }

        if(!jQuery.isPlainObject(obj))
            return ids;

        jQuery.each(obj, function(prop, val){
            $this._searchIds(val, ids);
        });
        return ids;
    }
};

// EXAMPLE DATA
var a = {};
var a2 = {}
a.b = a;
a.c = "hallo";
a.e = 123;
a.f = a2;
a2.x = a;

// USAGE
// new class
var ser = new Decircularizer();

// uncycle
var cleanObjectWithOutCirculars = ser.decycle(a);
console.debug(cleanObjectWithOutCirculars);


/* object looks like
Object {c: "hallo", e: 123, b: "{`id´}1", {`id´}: 1, f: Object}
    b: "{`id´}1"
    c: "hallo"
    e: 123
    f: Object
        x: "{`id´}1"
        {`id´}: 2
        __proto__: Object
    {`id´}: 1
    __proto__: Object 
*/

// recycle 
var aNew = ser.recycle(cleanObjectWithOutCirculars);
console.debug(aNew)

/*
Object {c: "hallo", e: 123, b: Object, f: Object}
    b: Object
        b: Object
        c: "hallo"
        e: 123
    f: Object
        x: Object
        __proto__: Object
    __proto__: Object
    c: "hallo"
    e: 123
    f: Object
        x: Object
            b: Object
            c: "hallo"
            e: 123
            f: Object
            __proto__: Object
        __proto__: Object
    __proto__: Object
*/

// correct (Y)

score 1 · Accepted Answer · answered Aug 28 '12 at 03:11

You should create a customized toJson function in the objects that have parents.

From the documentation

If an object being stringified has a property named toJSON whose value is a function, then the toJSON method customizes JSON stringification behavior

var x = {
  foo: 'foo',
  toJSON: function () {
    return 'bar';
  }
};
var json = JSON.stringify({x: x});

So you could create that function in the objects that have parent references, something like this maybe?

MyObj = function(){
    this.xxx = 'foobar';
    this.zzz = 'foooobar';
    this.name = 'foo';
    this.parent = ...;
    toJSON = function(){
        tmp = '{'
        for(prop in MyObj){
            if(prop == 'parent'){
                tmp += 'parent: "'+ this['parent'].name +'"'; //maybe?? optional!
            }else{
                tmp += prop + ':' + this[prop].stringify + ','; //you will still use the browser function
            }
            tmp += '}            
        }
        return tmp;
    }
}

Do you also have to write a parse function, or is that taken care of automatically? — Joe, Aug 30 '12 at 02:57
You will never have the circular references problem when parsing, so you can use the prebuilt functions or even the eval function and it should be fine — Frank Orellana, Aug 30 '12 at 03:43

Workaround for serializing a graph-theoretic tree with JSON?

2 Answers2