min spanning tree

by Milos Zivkovic

HTML

<!--

Minimum spanning tree example using the Kruskal algorithm

this standalone version has no dependencies
L 335 to change point count

/-->

CSS

html, body {
    width:100%;
    height:100%;
    /*#0e1521*/
    background: #EEEEEE; /* Old browsers */
    background: -moz-radial-gradient(center, ellipse cover,  #EEEEEE 1%, #444444 100%); /* FF3.6+ */
    background: -webkit-gradient(radial, center center, 0px, center center, 100%, color-stop(1%,#EEEEEE), color-stop(100%,#444444)); /* Chrome,Safari4+ */
    background: -webkit-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* Chrome10+,Safari5.1+ */
    background: -o-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* Opera 12+ */
    background: -ms-radial-gradient(center, ellipse cover,  #EEEEEE 1%,#444444 100%); /* IE10+ */
    background: radial-gradient(ellipse at center,  #EEEEEE 1%,#444444 100%); /* W3C */
    filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#EEEEEE', endColorstr='#444444',GradientType=1 ); /* IE6-9 fallback on horizontal gradient */

    background-color:#444444;
    overflow:hidden;
}

JavaScript

/**
 * computes and returns a Minimum Spanning Tree using the Kruskal Algorithm
 * @param metric a function( edge ) to compute the weight of the edge
 * @param sortMethod a sort function( edge0, edge1 ) to sort edges by increasing weight
 * @constructor
 */
var KruskalMinimumSpanningTree = function( metric, sortMethod )
{

	this.metric = metric || function( edge )
	{
		var dx = edge.p0.x - edge.p1.x;
		var dy = edge.p0.y - edge.p1.y;
		edge.weight = ( dx*dx + dy*dy );
	};

	this.sortMethod = sortMethod || function( edge0, edge1 )
	{
		return edge0.weight - edge1.weight;
	};


	this.PARENT = [];
	this.RANK = [];
	this.tree = [];
	this.sortedEdges = [];

	this.find = function( vertex )
	{
		if( this.PARENT[ vertex.id ] == vertex )
		{
			return this.PARENT[ vertex.id ];
		}
		else
		{
			return this.find( this.PARENT[ vertex.id ] );
		}
	};

	this.union = function( root0, root1 )
	{
		var id0 = root0.id;
		var id1 = root1.id;

		if( this.RANK[ id0 ] > this.RANK[ id1 ] )
		{
			this.PARENT[ id1 ] = root0;
		}
		else if( this.RANK[ id0 ] < this.RANK[ id1 ] )
		{
			this.PARENT[ id0 ] = root1;
		}
		else
		{
			this.PARENT[ id0 ] = root1;
			this.RANK[ id1 ]++;
		}

	};

	this.makeSet = function( vertex )
	{
		this.PARENT[ vertex.id ] = vertex;
		this.RANK[ vertex.id ] = 0;
	};

	this.compute = function( vertices, edges )
	{

		var self = this;
	    this.tree = [];
		this.PARENT = [];
		this.RANK = [];

		vertices.forEach( function( vertex )
		{
			self.makeSet( vertex );
		} );

	    this.sortedEdges = edges.concat();

		this.sortedEdges.forEach( function( e )
		{
			self.metric( e );
		});

		this.sortedEdges.sort( this.sortMethod );

		for ( var i = 0; i < this.sortedEdges.length; i++)
		{

	        var edge = this.sortedEdges[ i ];

			var root1 = this.find( edge.p0 );
			var root2 = this.find( edge.p1 );

			if( root1 != root2 )
			{
				this.tree.push( edge );
				this.union( root1, root2 );
			}

			if( this.tree.length == vertices.length - 1 )
			{
				return...