HenryW HenryW - 7 months ago 75
Javascript Question

adjacency list from JSON data

I try to programmaticly generate a new object as a adjacency list from the following provided sampleData to be used in jointJS, so it generates a organization chart in the end:

sampleData = [
{"id":"1224286", "label":"someLabel1", "image":"male.png", "level":"1"},
{"id":"1166041", "label":"someLabel2", "image":"male.png","refparent":"1224286", "level":"2"},
{"id":"1224376", "label":"someLabel3", "image":"male.png","refparent":"1224286", "level":"2"},
{"id":"1317500", "label":"someLabel4", "image":"male.png", "refparent":"1224286", "level":"2"},
{"id":"1232930", "label":"someLabel5", "image":"male.png", "refparent":"1166041", "level":"3"},
{"id":"1163148", "label":"someLabel6", "image":"male.png", "refparent":"1317500", "level":"3"},
{"id":"1279087", "label":"someLabel7", "image":"male.png", "refparent":"1166041", "level":"3"},
{"id":"1185740", "label":"someLabel8", "image":"male.png","refparent":"1224376", "level":"3"},
{"id":"1234273", "label":"someLabel9", "image":"male.png", "refparent":"1232930", "level":"4"},
{"id":"1210593", "label":"someLabel10", "image":"male.png", "refparent":"1185740", "level":"4"},
{"id":"1279247", "label":"someLabel11", "image":"male.png", "refparent":"1185740", "level":"4"},
{"id":"1316785", "label":"someLabel12", "image":"male.png", "refparent":"1232930", "level":"4"},
{"id":"1266325", "label":"someLabel13", "image":"male.png", "refparent":"1210593", "level":"5"}
];


The sampleData should be converted as in the following structure to use it as an adjacency list :

var list = {
'1224286': ['1166041', '1224376', '1317500'],
'1166041': ['1232930', '1279087'],
'1224376': ['1185740'],
'1317500': ['1163148'],
'1232930': ['1234273', '1316785'],
'1163148': [],
'1279087': [],
'1185740': ['1210593', '1279247'],
'1234273': [],
'1210593': ['1266325'],
'1279247': [],
'1316785': [],
'1266325': []
};


It is looking so simple but i just can't see it.

Answer

try this code (has n*n complexity)

var output = {};
sampleData.forEach(function(val){
  var id = val.id;
  var arr = [];
  sampleData.forEach(function(innerVal){
    if ( innerVal.refparent == id )
    {
       arr.push(innerVal.id);
    }
  });
  output[id] = arr;
});
console.log(output);

Or else you can transform the data-structure to get better performance

var transformed = {};
sampleData.forEach(function(val){
  var ref = val.refparent;
  transformed[ref] = transformed[ref] || [];
  transformed[ref].push(val.id);
});

//now iterate the original list to see what is missed out

var output = {}; 
sampleData.forEach(function(val){ 
  output[val.id] = transformed[val.id] || [];
});

This gives you 2n complexity.

DEMO

var sampleData = [
    {"id":"1224286", "label":"someLabel1", "image":"male.png", "level":"1"},
    {"id":"1166041", "label":"someLabel2", "image":"male.png","refparent":"1224286", "level":"2"},
    {"id":"1224376", "label":"someLabel3", "image":"male.png","refparent":"1224286", "level":"2"},
    {"id":"1317500", "label":"someLabel4", "image":"male.png", "refparent":"1224286", "level":"2"},
    {"id":"1232930", "label":"someLabel5", "image":"male.png", "refparent":"1166041", "level":"3"},
    {"id":"1163148", "label":"someLabel6", "image":"male.png", "refparent":"1317500", "level":"3"},
    {"id":"1279087", "label":"someLabel7", "image":"male.png", "refparent":"1166041", "level":"3"},
    {"id":"1185740", "label":"someLabel8", "image":"male.png","refparent":"1224376", "level":"3"},
    {"id":"1234273", "label":"someLabel9", "image":"male.png", "refparent":"1232930", "level":"4"},
    {"id":"1210593", "label":"someLabel10", "image":"male.png", "refparent":"1185740", "level":"4"},
    {"id":"1279247", "label":"someLabel11", "image":"male.png", "refparent":"1185740", "level":"4"},
    {"id":"1316785", "label":"someLabel12", "image":"male.png", "refparent":"1232930", "level":"4"},
    {"id":"1266325", "label":"someLabel13", "image":"male.png", "refparent":"1210593", "level":"5"}
];

var transformed = {};
sampleData.forEach(function(val){
  var ref = val.refparent;
  transformed[ref] = transformed[ref] || [];
  transformed[ref].push(val.id);
});

var output = {}; 
sampleData.forEach(function(val){ 
  output[val.id] = transformed[val.id] || [];
});

document.body.innerHTML += JSON.stringify(output,0,4);