tsp-web-worker.js

self.addEventListener('message', function(e) {

  if( Array.isArray(e.data) ) {
    self.postMessage(permutateRoutesAndFindShortest(e.data))
  }

}, false);

function permutateRoutesAndFindShortest(received_array) {
  var coords_array = [];

  for (var i = 0; i < received_array.length; i += 2) {
    var node = [received_array[i], received_array[i + 1]];
    coords_array.push(node);
  }

  if (coords_array.length < 3) {
    coords_array.unshift(0);
    return JSON.stringify(coords_array);
  }

  var perms_count = calculateFactorial(coords_array.length - 1);
  var permengine = new engine(coords_array.length - 1);
  var permutation;
  var shortest_permutation = [];
  var shortest_route_length = 1000000;
  var second_shortest_permutation;
  var second_shortest_route_length = 1000000;
  var route_length;
  var first_coords = coords_array.shift();

  for (var index = 0; index < perms_count; index++) {
    permutation = permengine.index2perm(index);
    route_length = getRouteLength(permutation, coords_array, first_coords);
    if (route_length < shortest_route_length) {
      second_shortest_route_length = shortest_route_length;
      //console.log("2nd: " + second_shortest_route_length + " " + index);
      second_shortest_permutation = shortest_permutation.slice();
      shortest_route_length = route_length;
      //console.log("shortest: " + shortest_route_length + " " + index);
      shortest_permutation = permutation;
    } else if (route_length < second_shortest_route_length && route_length > shortest_route_length) {
      second_shortest_route_length = route_length;
      //console.log("2nd: " + second_shortest_route_length + " " + index);
      second_shortest_permutation = permutation;
    }
  }

  var shortest_route_array = shortest_permutation.map(getCoordsByPermIndex, coords_array);
  shortest_route_array.unshift(first_coords); //beginning
  shortest_route_array.push(first_coords); //ending

  var second_shortest_route_array = [];
  var both_routes_array = [];
  if (second_shortest_route_length !== 1000000) {
    second_shortest_route_array = second_shortest_permutation.map(getCoordsByPermIndex, coords_array);
    second_shortest_route_array.unshift(first_coords); //beginning
    second_shortest_route_array.push(first_coords); //ending
    both_routes_array = shortest_route_array.concat(second_shortest_route_array);
    both_routes_array.unshift(1); //array to be returned contains both shortest and 2nd shortest paths
    return JSON.stringify(both_routes_array);
  }

  shortest_route_array.unshift(0); //array to be returned contains only shortest path
  return JSON.stringify(shortest_route_array);
}

function calculateFactorial(num) {
  var rval = 1;
  for (var i = 2; i <= num; i++) rval = rval * i;
  return rval;
}

function getRouteLength(permutation, coords, first) {
  var route_length = 0;

  for (var index = 0; index < permutation.length; index++) {
    route_length += calculateDistance(coords[permutation[index] - 1], coords[permutation[index + 1] - 1]);
  }

  route_length += calculateDistance(first, coords[permutation[0] - 1]);
  route_length += calculateDistance(first, coords[permutation[permutation.length - 1] - 1]);

  //truncate to four decimals because same route with different direction can have a small length difference
  return Math.round(Number(route_length) * 10000) / 10000;
}

function calculateDistance(coords_1, coords_2) {
  if (!coords_2) {
    return 0;
  }
  var delta_x = coords_1[0] - coords_2[0];
  var delta_y = coords_1[1] - coords_2[1];
  return Math.sqrt(Math.pow(delta_x, 2) + Math.pow(delta_y, 2));
}

function getCoordsByPermIndex(index) {
  return this[index - 1];
}




/**
	Permutation Engine
	Written by Erik Poupaert, November 2012
	Licensed under the Library General Public License (LGPL).
*/

function engine(n)
{

	if(n<2) throw new Error('Cannot initialize engine; n must not be smaller than 2');

	this.n=n;

	function cache()
	{
		this.hits=0;
		this.misses=0;
		this.enabled=true;
	}

	cache.prototype.report=function()
	{
		var total=this.hits+this.misses;
		if(total)
		{
			var perc_hits=Math.floor(this.hits/total*100);
			return 'count='+(Object.keys(this).length-3)+' hits='+this.hits+' misses='+
				this.misses+' total='+total+' hits perc='+perc_hits+'%';
		}
		else
		{
			return 'function was never called';
		}
	}

	/**
		@method fac(k)

		computes fac(k) as k!
	*/

	this.facCache=new cache();
	this.fac=function(k)
	{
		if(k<1) throw new Error('called fac(k) with negative or zero k:'+k);
		if(k==1) return 1;
		//check if we can serve from cache
		if(this.facCache.enabled)
			if(this.facCache[k])
			{
				this.facCache.hits++;
				return this.facCache[k];
			}
		//the calculation itself
		var result=k*this.fac(k-1);
		//cache the results
		this.facCache.misses++;
		if(this.facCache.enabled)
			this.facCache[k]=result;
		//return the result
		return result;
	}

	/**
		number of indexes for permutations with n elements
	 */

	this.indexCount=this.fac(n);

	/**
		@method firstChoiceForIndex(index,m)

		calculates the first choice for an index for permutations with m elements

		the index runs from 0 ... m!-1
		for example, if m=5, then the index run from 0..5!-1,
			that is, from 0..120 - 1,
			that is, from 0..119

		for m=5, there are 5 choices possible for the first element.
		There are always 4!=24 remaining choices
		choice	index_start	index_end
		1	(1-1)*24=0	0 +(24-1)=23
		2	(2-1)*24=24	24+(24-1)=47
		3	(3-1)*24=48	48+(24-1)=71
		4	(4-1)*24=72	72+(24-1)=95
		5	(5-1)*24=96	96+(24-1)=119

		in general:
		1	(1-1)*(m-1)!	(1-1)*(m-1)!+(m-1)
		k	(k-1)*(m-1)!	(k-1)*(m-1)!+(m-1)

		so, the relationship between index and k is:
		(k-1)*(m-1)! <= index <= (k-1)*(m-1)!+(m-1)

		k <= index/(m-1)!+1 which will be a fractional number
		k <= index/(m-1)!
		k_low=floor(k)
		k_high=floor(k+1)


	*/

	this.firstChoiceCache=new cache();
	this.firstChoiceForIndex=function(index,m)
	{
		if(index==0) return 1;
		//check if we can serve from cache
		var key=JSON.stringify(arguments);
		if(this.firstChoiceCache.enabled)
			if(this.firstChoiceCache[key])
			{
			    this.firstChoiceCache.hits++;
			    return this.firstChoiceCache[key];
			}
		//the calculation itself
		var k=index/this.fac(m-1);
		var k_low=Math.floor(k);
		var k_high=k_low+1;
		//cache the results
		this.firstChoiceCache.misses++;
		if(this.firstChoiceCache.enabled)
			this.firstChoiceCache[key]=k_high;
		//return the result
		return k_high;
	}

	/**
		@method remainingChoices(prefix)

		calculates the remaining choices given a set of choices (=prefix)

		for example, if for n=7, we choose the prefix [1 4 2]
		the remaining choices are [2 3 5 6 7]
		another example, n=5, prefix=[5 1], then remaining choices=[2 3 4]
	*/

	this.remainingChoicesCache=new cache();
	this.remainingChoices=function(prefix)
	{
		var key=JSON.stringify(prefix);
		//check if we can serve from cache
		if(this.remainingChoicesCache.enabled)
			if(this.remainingChoicesCache[key])
			{
			    this.remainingChoicesCache.hits++;
			    return this.remainingChoicesCache[key];
			}
		//the calculation itself
		result=[];
		for(var i=1; i<=n; i++)
		{
			if(prefix.indexOf(i)==-1) result.push(i);
		}
		//cache the results
		this.remainingChoicesCache.misses++;
		if(this.remainingChoicesCache.enabled)
			this.remainingChoicesCache[key]=result;
		//return the result
		return result;
	}

	/**
		@method indexStartForFirstChoice(index,m)

		for example m=5
		choice	index_start
		1	(1-1)*24=0
		2	(2-1)*24=24
		3	(3-1)*24=48
		4	(4-1)*24=72
		5	(5-1)*24=96

		we first calculate the choice for the index (firstChoiceForIndex) and then the index_start for the index

	*/

	this.indexStartForFirstChoiceCache=new cache();
	this.indexStartForFirstChoice=function(index,m)
	{
		var key=JSON.stringify(arguments);
		//check if we can serve from cache
		if(this.indexStartForFirstChoiceCache.enabled)
			if(this.indexStartForFirstChoiceCache[key])
			{
			    this.indexStartForFirstChoiceCache.hits++;
			    return this.indexStartForFirstChoiceCache[key];
			}
		//the calculation itself
		result=(this.firstChoiceForIndex(index,m)-1)*this.fac(m-1);
		//cache the results
		this.indexStartForFirstChoiceCache.misses++;
		if(this.indexStartForFirstChoiceCache.enabled)
			this.indexStartForFirstChoiceCache[key]=result;
		//return the result
		return result;
	}

	/**
		@method indexStartForFirstChoice(index,m)

		for example m=5
		choice	index_start
		1	(1-1)*24=0
		2	(2-1)*24=24
		3	(3-1)*24=48
		4	(4-1)*24=72
		5	(5-1)*24=96

		we first calculate the choice for the index (firstChoiceForIndex) and then the index_start

	*/

	this.index2permCalc=function (index,m,prefix)
	{
		var remainingChoices=this.remainingChoices(prefix);
		var choice=remainingChoices[this.firstChoiceForIndex(index,m)-1];
		prefix.push(choice);
		if(prefix.length<n) this.index2permCalc(index-this.indexStartForFirstChoice(index,m),m-1,prefix);
		return prefix;
	}

	/**
		@method index2perm(index)
		Computes the permutation for an index
	*/

	this.index2perm=function (index)
	{
	    return this.index2permCalc(index,this.n,[]);
	}

	/**
		@method nextPerm(perm)
		Computes the next permutation for a given permutation
	*/

	this.nextPerm=function(perm)
	{
		perm=perm.slice(0); //create a copy
		while(perm.length!=0)
		{
			perm.pop(); //remove one element
			var remainingChoices=this.remainingChoices(perm);
			var lastChoice=perm.slice(-1)[0]; //last element
			//look for element that is larger in remaining choices
			for(var i=0; i<remainingChoices.length; i++)
			{
				var candidate=remainingChoices[i];
				//next element found
				if(candidate>lastChoice)
				{
					perm[perm.length-1]=candidate;
					remainingChoices=this.remainingChoices(perm);
					return perm.concat(remainingChoices);
				}
			}
		}
		return null;
	}

	/*
		@method perm2index(perm)

		Example: n=5, index of [3 2 1 4 5]
		choice 	remaining choices	count 	index	index_start
		3	[1 2 3 4 5]		5	3	(3-1)*(5-1)! 	48
		2	[1 2 4 5]		4	2	(2-1)*(4-1)!	6
		1	[1 4 5]			3	1	(1-1)*(3-1)!	0
		4	[4 5]			2	1	(1-1)*(2-1)!	0
		5	last element never contributes to the index
										---
									index=	54
		In general
		index of [a1 a2 a3 ... an]
		contribution of ak to index: (index(k,remainingChoices)-1)*(remainingChoices.count-1)!
	*/

	this.perm2index=function(perm)
	{
	    var sum=0;
	    for(var i=0;i<this.n-1; i++)
	    {
		    var prefix=perm.slice(0,i);
		    var remainingChoices=this.remainingChoices(prefix);
		    var factorIndex=remainingChoices.indexOf(perm[i]);
		    var factorFac=this.fac(this.n-1-i);
		    sum+=factorIndex*factorFac;
	    }
	    return sum;
	}

	/*
		@method skipForward(perm,prefixSize)

        Example: [1 2 3] [4 9 5 7 8 6]
        We know, according to external rules, that [1 2 3] is an invalid permutation.
        Therefore, there is no point in evaluating the entire range of [1 2 3] [. . . . . .]
        It saves us 6!=24 evaluations.
        We know that range [1 2 3] ends with remaining choices [9 8 7 6 5 4]. After that, range [1 2 4] starts.

        call the function to return the next permutation, that is the first one starting with [1 2 4]:

            nextPermutation=skipForward([1 2 3 4 9 5 7 8 6],4);
	*/

    this.skipForward=function(perm,prefixSize)
    {
	    var prefix=perm.slice(0,prefixSize);
	    //last permutation for prefix is by sorting the remaining choices from high to low
	    var lastPermForPrefix=this.remainingChoices(prefix).slice(0).reverse();
	    perm=prefix.concat(lastPermForPrefix);
	    return this.nextPerm(perm);
    }


    /** the initial permutation */

    this.initialPerm=function()
    {
        return this.index2perm(0);
    }

    /** the last permutation */

    this.lastPerm=function()
    {
        return this.initialPerm().reverse();
    }

}