Last active
September 22, 2015 13:36
-
-
Save estliberitas/f3389b5ad73693b884e4 to your computer and use it in GitHub Desktop.
Given a set of edges of multiple graphs return vertice set for each graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment