Given a set of edges of multiple graphs return vertice set for each graph

graph-group-vertices.js

/**
 * I had a task to get sets of vertices for multiple graphs
 * given a set of edges.
 *
 * So if input looks like
 *
 *  [A, B], [C, B], [D, C], [K, L], [Z, X], [M, L]
 *
 * Output should be
 *
 *  [A, B, C, D], [K, L, M], [X, Z]
 * 
 * Below I present two algorithms, two functions to accomplish result.
 * 
 * First one uses mapping of vertice to unique vertices set. So if
 * connected vertices are both mapped, we do nothing. If neither is
 * mapped, we add vertices set initialized with those vertices. If
 * one only is mapped, we add another to set and map it to existing set. 
 *
 * Another one uses JavaScript Array#reduce() to loop through elements
 * and accumulate vertice sets, looping each time through existing vertice
 * sets.
 *
 * P.S.: I did not compare performance yet, but for sure can say that
 * in case of big edge cardinality reduce solution will suck
 */
'use strict';

let assert = require('assert');


function generateEdges(num, min, max) {
  var out = [];
  while (num--) {
    out.push([random(), random()]);
  }

  function random() {
    return min + Math.round((max - min) * Math.random());
  }

  return out;
}


function groupReduce(edges) {
  return edges.reduce(function addVertices(out, edge) {
    let s = edge[0];
    let e = edge[1];

    let i = 0;
    let set;
    while ((set = out[i++])) {
      if (~set.indexOf(s) && ~set.indexOf(e)) {
        return out;
      }
      else if (~set.indexOf(s)) {
        set.push(e);
        return out;
      }
      else if (~set.indexOf(e)) {
        set.push(s);
        return out;
      }
    }
    out.push([s, e]);
    return out;
  }, []);
}


function groupSimple(edges) {
  let edge;
  let i = 0;
  let vertices = [];
  let mapping = {};

  edges.sort(function verticeSorter(first, second) {
    if (first[0] > first[1]) {
      first.sort();
    }
    if (second[0] > second[1]) {
      second.sort();
    }

    if (first[0] !== second[0]) {
      return first[0] - second[0];
    }
    else {
      return 0;
    }
  });

  while ((edge = edges[i++])) {
    let s = edge[0];
    let e = edge[1];
    let set;

    if (s in mapping && e in mapping) {
      continue;
    }

    if (!(s in mapping) && !(e in mapping)) {
      set = edge.slice(0);
      mapping[s] = set;
      mapping[e] = set;
      vertices.push(set);
    }
    else if (s in mapping) {
      set = mapping[s];
      set.push(e);
      mapping[e] = set;
    }
    else if (e in mapping) {
      set = mapping[e];
      set.push(s);
      mapping[s] = set;
    }
  }
  return vertices;
}

let edges = generateEdges(1000000, 1, 100);

console.time('Simple: ');
let simple = groupSimple(edges);
console.timeEnd('Simple: ');


console.time('Reduce: ');
var reduce = groupReduce(edges);
console.timeEnd('Reduce: ');


assert.equal(simple.length, reduce.length);