Javascript Gruppierung verknüpfte Knoten

Question

Ich habe 2 Listen - Knoten und Links ... Nun, was ich möchte, ist die effizienteste Möglichkeit, alle direkt/indirekt verknüpfte Elemente in verschiedene Gruppen hinzuzufügen .... Für zB 0 ist mit 1 verbunden, die mit 2 verbunden ist, so dass Knoten 0, 1, 2 zur Gruppe 1 werden .... Knoten 3 ist mit 4 verbunden, also wird es Gruppe 2 und so weiter .... Vielen Dank im Voraus für Ihre Hilfe :) Dies ist Teil einer d3-Implementierung am tun ..

PS: Diese Listen werden leicht in Zehntausende von Knoten und Links sein.

"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

Dies ist ein klassisches UnionFind-Problem. Die Idee ist, jeden Knoten als eine Menge zu sehen, die einen Zeiger auf seinen Vater hat. Knoten mit demselben Vater sind in derselben Gruppe. Für dein Problem können wir am Anfang n Sets erstellen. Und dann iteriere den Link, um alle mit dem gleichen Link verbundenen Personen zu gruppieren. Die Komplexität ist O (n), wobei n die Anzahl der Knoten ist.

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

In der Lösung I unter Gruppen von link S AM schaffen, die, gut, miteinander verbunden. Ich tue dies, indem ich alle from/to Kombinationen durchlaufe, und finde heraus, ob beide bereits zu irgendeiner der akkumulierenden Gruppen von link s hinzugefügt worden sind. Wenn dies der Fall ist, füge ich einfach den Wert from und to dieser Gruppe hinzu (oder füge sie wieder hinzu). Wenn weder der from noch to Wert noch gruppiert wurde, dann mache ich eine neue Gruppe und füge sowohl die Werte from als auch to hinzu. Beachten Sie, dass diese "Gruppen" eigentlich Javascript-Sätze sind, ein neuer ES6/ES2015-Datentyp, der es viel einfacher macht, mit "Gruppen" von Elementen umzugehen, für die keine Duplikate benötigt und/oder erlaubt sind.

Sobald die Gruppen/Gruppen von Verbindungen eingerichtet sind, füge ich dann einfach ein Attribut zu jedem node hinzu, das anzeigt, welche Gruppe von link s es ein Teil von ist.

Beachten Sie, dass ich für diesen Demo-Code einige node Werte vereinfacht/entschachtelt habe. Ich habe auch einige zusätzliche Links hinzugefügt, nur um einige weitere Fälle zu demonstrieren, die behandelt werden müssen.

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

Dieser Code Spieße ein Objekt, dessen Schlüssel die Knoten-ID und deren Werte eine Gruppen-ID, sequentiell nicht unbedingt.

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