edge-contraction.js

/* 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;
}