Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

D3: use nest function to turn flat data with parent key into a hierarchy

I'm sure there's a really simple elegant way to do this but I can't quite figure it out. I have some input data that looks like this:

[
{id: 1, name: "Peter"},
{id: 2, name: "Paul", manager: 1},
{id: 3, name: "Mary", manager: 1},
{id: 4, name: "John", manager: 2},
{id: 5, name: "Jane", manager: 2}
]

If possible, I would like to use the d3.js nest operator to get a structure to use in the hierarchy layout. Like this:

[ 
   {name: "Peter", children: [
          {name:"Paul", children: [
              {name:"John"},
              {name:"Jane"}
          ]},
          {name:"Mary"}
      ]
   }
]
like image 243
prauchfuss Avatar asked Aug 13 '12 13:08

prauchfuss


1 Answers

You can't use the nest operator here because nesting produces a fixed hierarchy: the number of levels in the output hierarchy is the same as the number of key functions you specify.

That said, you can write your own function which produces a tree. Assuming that the root node is the first node in the input array, you can create a map from id to node, and then construct the tree lazily.

function tree(nodes) {
  var nodeById = {};

  // Index the nodes by id, in case they come out of order.
  nodes.forEach(function(d) {
    nodeById[d.id] = d;
  });

  // Lazily compute children.
  nodes.forEach(function(d) {
    if ("manager" in d) {
      var manager = nodeById[d.manager];
      if (manager.children) manager.children.push(d);
      else manager.children = [d];
    }
  });

  return nodes[0];
}

If you know that the nodes are listed in order such that managers appear before their reports, you can simplify the code to iterate only once.

like image 144
mbostock Avatar answered Oct 26 '22 13:10

mbostock