Skip to content

Instantly share code, notes, and snippets.

@xianny
Created August 28, 2016 17:13
Show Gist options
  • Save xianny/6409e64552fa19900b9fd2b83887fe13 to your computer and use it in GitHub Desktop.
Save xianny/6409e64552fa19900b9fd2b83887fe13 to your computer and use it in GitHub Desktop.
/* Small script for edge contraction of graphs. I was reading about
randomised algorithms, which led to Karger's algorithm for finding
min-cut of a graph, which led to reading about graphs and cutsets,
and then wanting to find out how graphs and edge contraction can be
represented in code...
To run, just do `node edge-contraction.js` */
var graph =
[ ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'],
[0, 1, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1],
[0, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0] ];
console.log('adjacency matrix of starting graph:')
prettyPrint(graph);
while (graph.length > 3) {
graph = contractRandomEdge(graph);
prettyPrint(graph);
}
console.log('done');
function prettyPrint(graph) {
var header = graph[0];
console.log(" | " + header.join(' | '));
for (var i = 1; i < graph.length; i++) {
console.log(header[i-1] + " | " + graph[i].join(' | '));
}
}
function randomBetween(bottom, top) {
return Math.floor( Math.random() * ( 1 + top - bottom ) ) + bottom;
}
function contractRandomEdge(graph) {
// safely copy graph to avoid mutating original obj
var resGraph = new Array();
for (var i = 0; i < graph.length; i++) {
resGraph[i] = new Array();
for (var j = 0; j < graph.length; j++) {
resGraph[i][j] = graph[i][j];
}
}
while (resGraph.length == graph.length) {
var header = graph[0];
var num_vertices = graph.length - 1;
var v1 = randomBetween(0, num_vertices - 1);
var v2 = randomBetween(0, num_vertices - 1);
if (v1 != v2) {
console.log('contracting edges from vertex ' + header[v2] + ' into vertex ' + header[v1]);
// copy all v2 edges to v1
for (var i = 0; i <= num_vertices; i++) {
if ((graph[headerOffset(v2)][i]) == 1) {
resGraph[headerOffset(v1)][i] = 1;
resGraph[headerOffset(i)][v1] = 1;
}
}
resGraph[headerOffset(v1)][v1] = 0;
// remove v2 from first dimension
resGraph.splice(headerOffset(v2), 1);
// remove v2 from second dimension
for (i = 0; i <= num_vertices - 1; i++) {
resGraph[i].splice(v2, 1);
}
}
}
function headerOffset(num) {
return num+1;
}
return resGraph;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment