javascript - 来自 JSON 数据的邻接列表

Question

我尝试以编程方式从以下提供的要在 jointJS 中使用的示例数据生成一个新对象作为邻接列表，因此它最终生成一个组织结构图:

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"}
];

sampleData 应按以下结构进行转换，以将其用作邻接列表:

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': []
};

看起来很简单，但我就是看不出来。

Answer 1

尝试这个代码(有 n*n 复杂度)

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);

或者您可以转换数据结构以获得更好的性能

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] || [];
});

这会给你 2n 的复杂性。

演示

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);