What is the most efficient way to aggregate a value from a JSON tree in d3.js?

Question

Assume you have a D3 JSON input with an unordered tree hierarchy like this:

{
"generated": "2017-02-21T14:02:18.652071",
"name": "root",
"children": [
{
  "name": "level1",
  "module_name": "level1",
  "children": [

  ],
  "size": "16"
},
{
  "authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
  "name": "child.js",
  "weight": "1.0",
  "module_name": "child.js",
  "children": [

  ],
  "size": "14"
},
{
  "authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
  "name": "child_1.js",
  "weight": "1.0",
  "module_name": "child_1.js",
  "children": [
      {
        "authorid": "e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
        "name": "child_1_1.js",
        "module_name": "child_1_1.js",
        "children": [

        ],
        "size": "112"
      },  
  ],
  "size": "14"
},
{
  "authorid": "e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
  "name": "child_3.js",
  "module_name": "child_3.js",
  "children": [

  ],
  "size": "133"
}...

The structure can have any depth.

Now we need to aggregate / group all "authorid" values so we have a grouped array / map of the containing hashes of all authors from the nested JSON tree like this:

[
"46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
"e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
]

All duplicates should be aggregated as string values into a grouped value list.

The purpose of the resulting array is to filter a html table from the according node entrys that are visible in the d3 chart.

What is the most elegant way to reach this without plain javascript recursion. Is it possible to use a nested JSON as input for d3.nest or is there another performant way i.e. filter to get the above result?

Answer 1

If you are free to use ES6 features, one of the cleanest solutions can be implemented using a generator function for recursively walking through the data structure in combination with a Set allowing only unique entries.

function* getAuthorIds(arr) {
  for (let {authorid, children} of arr) { 
    if (authorid) yield authorid;
    if (children) yield* getAuthorIds(children);
  }
}

var uniqueAuthorIds = [...new Set(getAuthorIds(data))];

The generator function gets passed an array of objects over which it will iterate using a for-of loop. It will yield the authorid if the object contains a property of this name. After that, it checks, if the object contains an array of children and, if it does, delegates to the generator for these children by using yield*. This is where recursion happens to walk through the entire hierarchy.

To get a collection of unique authorids you can construct a Set from all values of authorid, which were found throughout your data. The Set by definition guarantees the values stored in it to be unique. The trick here is to pass the generator created for your data by calling getAuthorIds(data) directly to the Set's constructor. This is possible because the constructor accepts an iterable object, i.e. an object implementing the iterable protocol, which is exactly what a Generator implicitly does.

Because in your question you asked for an array of authorids, as a last step, an array is created from the Set using the spread operator.

Have a look at the following working demo:

var data = [{
"generated": "2017-02-21T14:02:18.652071",
"name": "root",
"children": [{
  "name": "level1",
  "module_name": "level1",
  "children": [

  ],
  "size": "16"
  }, {
    "authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
    "name": "child.js",
    "weight": "1.0",
    "module_name": "child.js",
    "children": [

    ],
    "size": "14"
  }, {
    "authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
    "name": "child_1.js",
    "weight": "1.0",
    "module_name": "child_1.js",
    "children": [{
          "authorid": "e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
          "name": "child_1_1.js",
          "module_name": "child_1_1.js",
          "children": [

          ],
          "size": "112"
    }],
    "size": "14"
  }, {
    "authorid": "e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
    "name": "child_3.js",
    "module_name": "child_3.js",
    "children": [

    ],
    "size": "133"
  }]
}];

function* getAuthorIds(arr) {
  for (let {authorid, children} of arr) { 
    if (authorid) yield authorid;
    if (children) yield* getAuthorIds(children);
  }
}

var uniqueAuthorIds = [...new Set(getAuthorIds(data))];

console.log(uniqueAuthorIds);

Answer 2

Try this :

var jsonObj = {
	"generated": "2017-02-21T14:02:18.652071",
	"name": "root",
	"children": [{
		"name": "level1",
		"module_name": "level1",
		"children": [

		],
		"size": "16"
	}, {
		"authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
		"name": "child.js",
		"weight": "1.0",
		"module_name": "child.js",
		"children": [

		],
		"size": "14"
	}, {
		"authorid": "46f14ba664314322e217383c4166d9e89892de93cbe2bb6bf2ea1645f910a24955c22fd384924a2f715efa34d07149ba284c2947c788f7c25a99308dfb2d7a6c",
		"name": "child_1.js",
		"weight": "1.0",
		"module_name": "child_1.js",
		"children": [{
			"authorid": "e5b333a985d12c2f0ccc878fc81d5e3d04732ef398631022443e25c2372e165f4f0d3d61f3f8caf8ccf4fa6e6af336834062d883d52fd3b67b2e15bd8599207a",
			"name": "child_1_1.js",
			"module_name": "child_1_1.js",
			"children": [

			],
			"size": "112"
		}],
		"size": "14"
	}]
};

var arr = [];

function checkKey(object) {
    if(object.hasOwnProperty('authorid'))
        arr.push(object.authorid);

    for(var i=0;i<Object.keys(object).length;i++) {
        if(typeof object[Object.keys(object)[i]]=="object"){
            checkKey(object[Object.keys(object)[i]]);
        }
    }
}

checkKey(jsonObj);

console.log(arr);

Answer 3

I think d3 is not needed for this task as a simple recursive function should fit pretty well.

var ids = [];
function collectAuthorIdsRecursively(elem) {
    for (var i = 0; i < elem.children.length; i++) {
        var child = elem.children[i];
        if (child.hasOwnProperty('authorid') && ids.indexOf(child.authorid) < 0) {
            ids.push(child.authorid);
        }

        if (child.hasOwnProperty('children') && child.children instanceof Array) {
            collectAuthorIdsRecursively(child);
        }
    }
}

collectAuthorIdsRecursively(data);

jsfiddle example