The Prüfer Sequence

Reading time ~1 minute

The Prüfer Sequence is a cool way of representing a tree of nodes with a sequence of labels. I wrote a javascript version to create arbitrary tree structures for testing node streams for a recent project. Here’s an implementation for converting a sequence to an array of connected edges:

function prufer(a) {
  var tree = [];
  var T = Array.apply(null, Array(a.length + 2)).map(function(_, i) { return i; });
  var deg = Array.apply(null, Array(1*T.length)).map(function() { return 1; });
  a.map(function(i) { deg[i]++; });

  for(var i = 0; i < a.length; i++) {
    for(var j = 0; j < T.length; j++) {
      if(deg[T[j]] === 1) {
        tree.push([a[i], T[j]]);
        deg[a[i]]--;
        deg[T[j]]--;
        break;
      }
    }
  }

  var last = T.filter(function(x) { return deg[x] === 1; });
  tree.push(last);

  return tree;
}

See the Pen WbNeYg by Johnathan Leppert (@jleppert) on CodePen.

Here’s the code on github and npm module.

Stereo Vision with Oculus Rift

Making a stereo vision camera and real-time IP video with Oculus Rift Continue reading

PostGIS Geocoder using Tiger Data

Published on May 01, 2014