我有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);
更多推荐
发布评论