javascript grouping linked nodes

Question

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

Answer 1

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

Answer 2

In the solution below I am creating groups of links that are, well, linked to each other. I do so by looping through all of the from/to combinations, and finding out if either has already been added to any of the accumulating groups of links. If they have, then I just add (or re-add) both the from and to value to that group. If neither the from nor to value has yet been grouped, then I make a new group and add both the from and to values to it. Note that these "groups" are actually Javascript sets, a new ES6/ES2015 data type that makes it much easier to deal with "groups" of elements for which no duplicates are needed and/or allowed.

Once the groups/sets of links are established, I then simply add an attribute to each node that indicates which group of links it is a part of.

Note that, for the sake of this demo code, I've simplified/de-cluttered some node values. I've also added some extra links, just to demonstrate some further cases that need handling.

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

This code spits out an object whose keys are the node id and whose values are a group id, not necessarily sequential.

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