Traverse Array of objects to generate d3 Sankey Chart data

Question

This input (tree-like structure) has to be formatted to a particular format to draw a d3 sankey diagram chart.

let unformattedJson = [
  {
    "key": "a1",
    "value": 30,
    "buckets": [
      {
        "key": "a2",
        "value": 10 
      },
      {
        "key": "b2",
        "value": 20 
      }
    ]
  },
  {
    "key": "b1",
    "value": 70,
    "buckets": [
      {
        "key": "b2",
        "value": 40 
      },
      {
        "key": "c2",
        "value": 30 
      }
    ]
  }
]

Expected output I need to generate is:

{
  "nodes": [
    {"nodeId":0,"name":"a1"},
    {"nodeId":1,"name":"a2"},
    {"nodeId":2,"name":"b2"},
    {"nodeId":3,"name":"b1"},
    {"nodeId":4,"name":"c2"}
  ],
  "links": [
    {"source":0,"target":1,"value":10},
    {"source":0,"target":2,"value":20},
    {"source":3,"target":2,"value":40},
    {"source":3,"target":4,"value":30}
  ]
}

My approach for the solution. I made two functions to calculate node and links. For nodes, I made a recursive functions to get all the unique keys and assigned a id for each keys. And I made another functions to get all the relationship between the keys.

let makeNodeObj = function(orObj, index){
    let obj = {};
    obj.nodeId = index;
    obj.name = orObj;
    return obj;
}

var getUniqueKeys = (old, arr)=>{
  let toRet = old;
  arr.forEach((data,index)=>{
    if(toRet.indexOf(data.key)<0){ //remove duplicates
      toRet.push(data.key);
    }
    if(data.buckets !== undefined && data.buckets.length>0){
        getUniqueKeys(toRet, data.buckets);
    }
  });
  return toRet;
}

let uniqueKeys = getUniqueKeys([],unformattedJson);

let nodes = uniqueKeys.map((data,index)=>{
  return makeNodeObj(data,index);
});

let getNodeId = function(nodes, key){
  let node = nodes.find((data)=>{
    return data.name == key
  });
  return node.nodeId;
}

let links = [];
unformattedJson.map((data)=>{
  let sourceId = getNodeId(nodes, data.key);
  if(data.buckets.length>0){
    data.buckets.map((data2)=>{
      let targetId = getNodeId(nodes,data2.key);
      let linkObj = {};
      linkObj.source = sourceId;
      linkObj.target = targetId;
      linkObj.value = data2.value;
      links.push(linkObj);
    })
  }
});

console.log({
  nodes, links
});

My solution will only work if there are only one level-deep buckets. How to achieve this for multiple nested buckets inside child?

Answer 1

I made a recursive approach for generate the expected output. Associations between a key and his generated id are keep with a Map. The approach uses the idea of traversing the tree with Deep First Search algorithm.

let unformattedJson = [
  {
    "key": "a1",
    "value": 30,
    "buckets": [
      {
        "key": "a2",
        "value": 10,
        "buckets": [
          {"key": "a3", "value": 99}
        ]
      },
      {"key": "b2", "value": 20}
    ]
  },
  {
    "key": "b1",
    "value": 70,
    "buckets": [
      {"key": "b2", "value": 40},
      {"key": "c2", "value": 30}
    ]
  }
];

const getData = (input, visited=new Map(), parent, nodes=[], links=[]) =>
{
    input.forEach(x =>
    {
        // Add node into the node list, if not visited previosuly.

        if (!visited.has(x.key))
        {
            let currId = nodes.length;
            nodes.push({nodeId: currId, name: x.key});
            visited.set(x.key, currId);
        }

        // If a parent node exists, add relation into the links list.

        if (parent)
        {
            // Note, we use the "Map" to get the ids.

            links.push({
                source: visited.get(parent.key),
                target: visited.get(x.key),
                value: x.value
            });
        }

        // Traverse (if required) to the next level of deep.

        if (x.buckets)
            getData(x.buckets, visited, x, nodes, links)
    });

    return {nodes: nodes, links: links};
}

console.log(getData(unformattedJson));