javascript分組鏈接的節點

Question

我有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 
    } 
    ... 
    ] 

Answer 1

這是一個典型的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);

Answer 2

在下面我創建的link S中的值爲，那麼，相互連接基團的溶液。我這樣做是通過遍歷所有的from/to組合，並確定是否已被添加到任何累積組link s。如果他們有，那麼我只需向該組添加（或重新添加）from和to值。如果from和to值都尚未分組，則我創建一個新組並將from和to值都添加到該組中。請注意，這些「組」實際上是Javascript集合，這是一種新的ES6/ES2015數據類型，可以更輕鬆地處理不需要和/或允許重複的元素的「組」。

一旦建立了一組/一組連接，我就簡單地向每個node添加一個屬性，表明它屬於哪一組link。

請注意，爲了演示代碼，我簡化了/取消了一些node值。我還添加了一些額外的鏈接，只是爲了演示一些需要處理的進一步案例。

const groupNodes = (nodes, links) => { 
 
    const groups = links.reduce((grps, {from, to}) => { 
 
    if (!grps.some(grp => { 
 
     if (grp.has(from) || grp.has(to)) return grp.add(from).add(to); 
 
    })) grps.push(new Set([from, to])); 
 
    return grps; 
 
    }, []); 
 
    nodes.forEach(node => { 
 
    groups.forEach((grp, i) => { if (grp.has(node.id)) node.group = i; }); 
 
    }); 
 
    return nodes; 
 
}; 
 

 

 

 
const nodes = [ 
 
    { 
 
    "id":0, 
 
    "x":0, 
 
    "y":0 
 
    }, 
 
    { 
 
    "id":1, 
 
    "x":11, 
 
    "y":-11 
 
    }, 
 
    { 
 
    "id":2, 
 
    "x":22, 
 
    "y":-22 
 
    }, 
 
    { 
 
    "id":3, 
 
    "x":33, 
 
    "y":-33 
 
    }, 
 
    { 
 
    "id":4, 
 
    "x":44, 
 
    "y":-44 
 
    }, 
 
    { 
 
    "id":5, 
 
    "x":55, 
 
    "y":-55 
 
    }, 
 
    { 
 
    "id":6, 
 
    "x":66, 
 
    "y":-66 
 
    } 
 
]; 
 
const links = [ 
 
    { 
 
    "from": 0, 
 
    "to" : 1 
 
    }, 
 
    { 
 
    "from": 1, 
 
    "to" : 2 
 
    }, 
 
    { 
 
    "from": 2, 
 
    "to" : 0 
 
    }, 
 
    { 
 
    "from": 3, 
 
    "to" : 4 
 
    }, 
 
    { 
 
    "from": 4, 
 
    "to" : 5 
 
    }, 
 
    { 
 
    "from": 6, 
 
    "to" : 0 
 
    } 
 
]; 
 

 
console.log(JSON.stringify(groupNodes(nodes, links)));

Answer 3

此代碼吐出的對象的鍵是節點ID和其值的組ID，不一定連續的。

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

 
var groups = {}; 
 
var nextGrp = 1; 
 

 
for (var i=0, l; l = obj.links[i]; i++) { 
 
    if (groups[l.from]) { 
 
    if (groups[l.to]) { 
 
     if (groups[l.to] != groups[l.from]) { 
 
     // the two items span two different groups which must now be joined into 1 
 
     for (var j in groups) { 
 
      if (groups[j] == groups[l.to]) { 
 
      groups[j] = groups[l.from]; 
 
      } 
 
     } 
 
     } 
 
    } else { 
 
     groups[l.to] = groups[l.from]; 
 
    } 
 
    } else if (groups[l.to]) { 
 
    groups[l.from] = groups[l.to]; 
 
    } else { 
 
    groups[l.from] = nextGrp; 
 
    groups[l.to] = nextGrp; 
 
    nextGrp++; 
 
    } 
 
} 
 

 
console.log(groups);