javascript分组链接节点(javascript grouping linked nodes)

javascript分组链接节点(javascript grouping linked nodes)

我有2个列表 - 节点和链接......现在我想要的是将所有直接/间接链接的元素添加到不同组中的最有效方法....例如，0连接到1连接到2所以节点0,1,2成为第1组....节点3连接到4所以它变成第2组，依此类推....感谢您的帮助:)这是d3实现的一部分。 。

PS：这些列表将很容易在数以万计的节点和链接。

"nodes":[ { "id":0, "x":1509.9862, "y":-609.1013 }, { "id":1, "x":1645.9578, "y":-85.06705 }, { "id":2, "x":1948.1533, "y":-469.3646 }, { "id":3, "x":348.1533, "y":-669.3646 }, { "id":4, "x":1448.1533, "y":-1469.3646 } ... ] "links":[ { "from":0, "to":1 }, { "from":1, "to":2 }, { "from":3, "to":4 } ... ]

I have 2 lists - nodes and links... Now what I would want is the most efficient way to add all the directly/indirectly linked elements into different groups.... For eg, 0 is connected to 1 which is connected to 2 so nodes 0,1,2 become group 1.... node 3 is connected to 4 so it becomes group 2 and so on.... Thanks in advance for your help :) This is part of a d3 implementation am doing..

PS: These lists will easily be in tens of thousands of nodes and links.

"nodes":[ { "id":0, "x":1509.9862, "y":-609.1013 }, { "id":1, "x":1645.9578, "y":-85.06705 }, { "id":2, "x":1948.1533, "y":-469.3646 }, { "id":3, "x":348.1533, "y":-669.3646 }, { "id":4, "x":1448.1533, "y":-1469.3646 } ... ] "links":[ { "from":0, "to":1 }, { "from":1, "to":2 }, { "from":3, "to":4 } ... ]

最满意答案

这是一个典型的UnionFind问题。 这个想法是将每个节点看作一个指向其父的指针集。 与父亲相同的节点在同一组中。 因此，对于您的问题，我们可以在开始时创建n组。 然后遍历链接，将通过相同链接连接的所有人分组。 复杂度是O（n），其中n是节点的数量。

nodes = [{
    "id": 0,
    "x": 1509.9862,
    "y": -609.1013
  },
  {
    "id": 1,
    "x": 1645.9578,
    "y": -85.06705
  },
  {
    "id": 2,
    "x": 1948.1533,
    "y": -469.3646
  },
  {
    "id": 3,
    "x": 348.1533,
    "y": -669.3646
  },
  {
    "id": 4,
    "x": 1448.1533,
    "y": -1469.3646
  }
];

links = [{
    "from": 0,
    "to": 1
  },
  {
    "from": 1,
    "to": 2
  },
  {
    "from": 3,
    "to": 4
  }
];

// union-find is a data structure that can union two sets and check
// whether two element in the same set.

var father = {};

function group(nodes, links) {
  // create n set with each set has the node as its only element
  nodes.forEach(function(node, i) {
    father[node.id] = node.id;
  });

  // union each set that has a link between them
  links.forEach(function(link, i) {
    union(link.from, link.to);
  });

  // for each unioned set, group nodes together
  var id = 1;
  var groupIdCnt = {};
  var groupIds = {};
  nodes.forEach(function(node, i) {
    var f = find(node.id);
    if (typeof groupIds[f] === 'undefined') {
      groupIds[f] = id;
      groupIdCnt[id] = 1;
      id++;
    } else {
      groupIdCnt[groupIds[f]]++;
    }
  });

  var groups = {};
  nodes.forEach(function(node, i) {
    var f = find(node.id);
    if (groupIdCnt[groupIds[f]] === 1) {
      node['group'] = 0;
    } else {
      node['group'] = groupIds[f];
    }

    if (typeof groups[node['group']] === 'undefined') {
      groups[node['group']] = [];
    }
    groups[node['group']].push(node);
  });

  return Object.values(groups);

}

// find father of each set
function find(node) {
  // if it is the root, return
  if (father[node] === node) {
    return node;
  }
  // if not, find the father and point to it
  father[node] = find(father[node]);
  return father[node];
}

// update the father of set which includes node1 to the father of set which includes node 2
function union(node1, node2) {
  father[find(node1)] = find(node2);
}

// O(n), since we visit each node once
var groups = group(nodes, links);
console.log(nodes);
console.log(groups); 
  
 
This is a classic UnionFind problem. The idea is to see each node as a set that has a pointer point to its father. Nodes with the same father are in the same group. So for your problem, we can create n sets at the beginning. And then iterate through the link to group everyone connected by the same link. The complexity is O(n), where n is the number of nodes.
 
 
 
  
  
nodes = [{
    "id": 0,
    "x": 1509.9862,
    "y": -609.1013
  },
  {
    "id": 1,
    "x": 1645.9578,
    "y": -85.06705
  },
  {
    "id": 2,
    "x": 1948.1533,
    "y": -469.3646
  },
  {
    "id": 3,
    "x": 348.1533,
    "y": -669.3646
  },
  {
    "id": 4,
    "x": 1448.1533,
    "y": -1469.3646
  }
];

links = [{
    "from": 0,
    "to": 1
  },
  {
    "from": 1,
    "to": 2
  },
  {
    "from": 3,
    "to": 4
  }
];

// union-find is a data structure that can union two sets and check
// whether two element in the same set.

var father = {};

function group(nodes, links) {
  // create n set with each set has the node as its only element
  nodes.forEach(function(node, i) {
    father[node.id] = node.id;
  });

  // union each set that has a link between them
  links.forEach(function(link, i) {
    union(link.from, link.to);
  });

  // for each unioned set, group nodes together
  var id = 1;
  var groupIdCnt = {};
  var groupIds = {};
  nodes.forEach(function(node, i) {
    var f = find(node.id);
    if (typeof groupIds[f] === 'undefined') {
      groupIds[f] = id;
      groupIdCnt[id] = 1;
      id++;
    } else {
      groupIdCnt[groupIds[f]]++;
    }
  });

  var groups = {};
  nodes.forEach(function(node, i) {
    var f = find(node.id);
    if (groupIdCnt[groupIds[f]] === 1) {
      node['group'] = 0;
    } else {
      node['group'] = groupIds[f];
    }

    if (typeof groups[node['group']] === 'undefined') {
      groups[node['group']] = [];
    }
    groups[node['group']].push(node);
  });

  return Object.values(groups);

}

// find father of each set
function find(node) {
  // if it is the root, return
  if (father[node] === node) {
    return node;
  }
  // if not, find the father and point to it
  father[node] = find(father[node]);
  return father[node];
}

// update the father of set which includes node1 to the father of set which includes node 2
function union(node1, node2) {
  father[find(node1)] = find(node2);
}

// O(n), since we visit each node once
var groups = group(nodes, links);
console.log(nodes);
console.log(groups);