Complex d3.nest() manipulation

Question

I have an array of arrays that looks like this:

var arrays = [[1,2,3,4,5],
              [1,2,6,4,5],
              [1,3,6,4,5],
              [1,2,3,6,5],
              [1,7,5],
              [1,7,3,5]]

I want to use d3.nest() or even just standard javascript to convert this data into a nested data structure that I can use with d3.partition.

Specifically, I want to create this flare.json data format.

The levels of the json object I want to create with d3.nest() correspond to the index positions in the array. Notice that 1 is in the first position in all the subarrays in the example data above; therefore, it is at root of the tree. At the next positions in the arrays there are three values, 2, 3, and 7, therefore, the root value 1 has 3 children. At this point the tree looks like this:

      1
    / | \
   2  3  7

At the third position in the subarrays there are four values, 3, 5, and 6. These children would be places into the tree as follows:

            1
        ____|___
       /    |    \
      2     3     7
     / \   /     / \
    3   6 6     3   5

How can I produce this data structure using d3.nest()? The full data structure with the example data I showed above should look like this:

   {"label": 1, 
     "children": [
        {"label": 2, "children": [
            {"label": 3, "children": [
                {"label": 4, "children": [
                    {"label": 5}
                ]},
                {"label": 6, "children": [
                    {"label": 5}
                ]}
            ]},
            {"label": 6, "children": [
                {"label": 4, "children": [
                    {"label": 5}
                ]}
            ]},
        {"label": 3, "children": [
            {"label": 6, "children": [
                {"label": 4, "children": [
                    {"label": 5}
                ]}
            ]}
        ]},
        {"label": 7, "children": [
            {"label": 3, "children": [
                {"label": 5}
            ]},
            {"label": 5}
        ]}
      ]}
    ]}

I'm trying to convert my array data structure above using something like this (very wrong):

var data = d3.nest()
  .key(function(d, i) { return d.i; })
  .rollup(function(d) { return d.length; })

I've been banging my head for a week to try and understand how I can produce this hierarchical data structure from an array of arrays. I'd be very grateful if someone could help me out.

@meetamit's answer in the comments is good, but in my case my tree is too deep to repeatedly apply .keys() to the data, so I cannot manually write a function like this.

Answer 1

Here's a more straightforward function that just uses nested for-loops to cycle through all the path instructions in each of your set of arrays.

To make it easier to find the child element with a given label, I have implemented children as a data object/associative array instead of a numbered array. If you want to be really robust, you could use a d3.map for the reasons described at that link, but if your labels are actually integers than that's not going to be a problem. Either way, it just means that when you need to access the children as an array (e.g., for the d3 layout functions), you have to specify a function to make an array out of the values of the object -- the d3.values(object) utility function does it for you.

The key code:

var root={}, 
    path, node, next, i,j, N, M;

for (i = 0, N=arrays.length; i<N; i++){
    //for each path in the data array 
    path = arrays[i];
    node = root; //start the path from the root

    for (j=0,M=path.length; j<M; j++){
        //follow the path through the tree
        //creating new nodes as necessary

        if (!node.children){ 
            //undefined, so create it:
            node.children = {}; 
        //children is defined as an object 
        //(not array) to allow named keys
        }

        next = node.children[path[j]];
        //find the child node whose key matches
        //the label of this step in the path

        if (!next) {
            //undefined, so create
            next = node.children[path[j]] = 
                {label:path[j]};
        }
        node = next; 
        // step down the tree before analyzing the
        // next step in the path.        
    }    
}

Implemented with your sample data array and a basic cluster dendogram charting method:
http://fiddle.jshell.net/KWc73/

Edited to add: As mentioned in the comments, to get the output looking exactly as requested:

1. Access the data's root object from the default root object's children array.
2. Use a recursive function to cycle through the tree, replacing the children objects with children arrays.

Like this:

root = d3.values(root.children)[0];
//this is the root from the original data, 
//assuming all paths start from one root, like in the example data

//recurse through the tree, turning the child
//objects into arrays
function childrenToArray(n){
    if (n.children) {
        //this node has children

        n.children = d3.values(n.children);
        //convert to array

        n.children.forEach(childrenToArray);
        //recurse down tree
    }
}
childrenToArray(root);

Updated fiddle:
http://fiddle.jshell.net/KWc73/1/

Answer 2

If you extend the specification of Array, it's not actually that complex. The basic idea is to build up the tree level by level, taking each array element at a time and comparing to the previous one. This is the code (minus extensions):

function process(prevs, i) {
  var vals = arrays.filter(function(d) { return prevs === null || d.slice(0, i).compare(prevs); })
                 .map(function(d) { return d[i]; }).getUnique();
  return vals.map(function(d) {
    var ret = { label: d }
    if(i < arrays.map(function(d) { return d.length; }).max() - 1) {
        tmp = process(prevs === null ? [d] : prevs.concat([d]), i+1);
        if(tmp.filter(function(d) { return d.label != undefined; }).length > 0)
          ret.children = tmp;
    }
    return ret;
  });
}

No guarantees that it won't break for edge cases, but it seems to work fine with your data.

Complete jsfiddle here.

Some more detailed explanations:

• First, we get the arrays that are relevant for the current path. This is done by filtering out those that are not the same as prevs, which is our current (partial) path. At the start, prevs is null and nothing is filtered.
• For these arrays, we get the values that corresponds to the current level in the tree (the ith element). Duplicates are filtered. This is done by the .map() and .getUnique().
• For each of the values we got this way, there will be a return value. So we iterate over them (vals.map()). For each, we set the label attribute. The rest of the code determines whether there are children and gets them through a recursive call. To do this, we first check whether there are elements left in the arrays, i.e. if we are at the deepest level of the tree. If so, we make the recursive call, passing in the new prev that includes the element we are currently processing and the next level (i+1). Finally, we check the result of this recursive call for empty elements -- if there are only empty children, we don't save them. This is necessary because not all of the arrays (i.e. not all of the paths) have the same length.