Simulated annealing TSP in D3

.gitignore

*~
doc

README.md

Simulated annealing optimisation of the Traveling Salesman problem, animated with D3.

annealing.js

/**
   Simulated annealing
   @constructor
   @param {Graph} graph A graph to optimise
   @param {Object} cfg Configuration
   @param {number} [cfg.initialTemperature=1.0] Initial temperature
   @param {number} [cfg.alpha=0.9] Temperature decrement factor
   @param {number} [cfg.niter=100] Number of iteratiorn before temperature change
   @param {number} [cfg.k=0.01] Normalising constant

   @see {@link http://en.wikipedia.org/wiki/Simulated_annealing}
  */
var Annealing = function(cfg) {
    this.cfg = _.extend({
        initialTemperature: 1.0,
        alpha: 0.9,
        niter: 100,
        k: 0.01
    }, cfg);

    this.handlers = {
        progress: undefined
    };
}

Annealing.prototype._callback = function(name) {
    if(this.handlers[name]) {
        return this.handlers[name].apply(this, Array.prototype.slice.call(arguments, 1));
    }

    return undefined;
}

/**
   Start simulated annealing
   @function
   @param {Graph} graph A graph
   @return {Annealing}
  */
Annealing.prototype.start = function(graph) {
    this._callback('progress', 10);
    return this;
}

/**
   Install progress event callback
   @function
   @param {Annealing~on_progress_cb} cb A callback
   @return {Annealing}
  */
Annealing.prototype.on_progress = function(cb) {
    this.handlers.progress = typeof cb == 'function' ? cb : undefined;
    return this;
}

/**
 * Progress callback
 * @callback Annealing~on_progress_cb
 * @this {Annealing}
 * @param {number} current Current progress
 * @param {number} total Total progress
 */

annealing_worker.js

/** @module AnnealingWorker
    @desc To be started by a worker thread. Will run a simulated annealing process
    when onmessage has been received.
*/

importScripts('//cdnjs.cloudflare.com/ajax/libs/lodash.js/2.2.1/lodash.min.js');
importScripts('annealing.js');


/** Start the simulated annealing process
    @param {Object} event
    @param {Object} event.data
    @param {Graph} event.data.graph A graph to be annealed
    @param {Object} event.data.cfg Annealing configuration, see {@link Annealing}
  */
onmessage = function(event) {
    cfg = event.data.cfg || {};
    graph = event.data.graph || {};

    var annealing = new Annealing(cfg);
    annealing.on_progress(function(progres) {
        postMessage(progres);
    });

    annealing.start(graph);
}

d3graph.js

/**
   D3 representation of a TSP graph
   @constructor
   @param {string} parentDom DOM to be extended with a D3 SVG
   @param {Object} cfg Configuration
   @param {number} [cfg.width=parent DOM width] Graph width
   @param {number} [cfg.height=parent DOM height] Graph height
*/
var D3Graph = function(parentDom, cfg) {
    this.cfg = _.extend({
        width: $(parentDom).parent().width(),
        height: $(parentDom).parent().height()
    }, cfg);

    var svg = d3.select(parentDom)
        .append('svg')
        .attr('width', this.cfg.width)
        .attr('height', this.cfg.height);

    svg.append('rect')
        .attr('x', 0)
        .attr('y', 0)
        .attr('width', this.cfg.width)
        .attr('height', this.cfg.height)
        .attr('class', 'frame');

    _.extend(this, {
        graph: undefined,
        svg: svg,
        links: svg.append('g').attr('id', 'links'),
        nodes: svg.append('g').attr('id', 'nodes'),
        color: d3.scale.category20(),
    });

}

/** Set the current graph
    @param {Graph} graph A graph
 */
D3Graph.prototype.setGraph = function(graph) {
    var self = this;

    this.graph = graph;

    // remove old data
    this.links.selectAll(".link")
        .data([])
        .exit()
        .remove();

    this.nodes.selectAll(".node")
        .data([])
        .exit()
        .remove();

    // add new data
    this.links.selectAll('.link')
        .data(graph.links)
        .enter()
        .append('line')
        .attr('class', 'link')
        .attr('x1', function(d) { return d.source.x; })
        .attr('y1', function(d) { return d.source.y; })
        .attr('x2', function(d) { return d.target.x; })
        .attr('y2', function(d) { return d.target.y; })
        .style('stroke-width', function(d) { return Math.sqrt(d.value); }),

    this.nodes.selectAll('.node')
        .data(graph.nodes)
        .enter()
        .append('circle')
        .attr('class', 'node')
        .attr('r', 5)
        .attr('cx', function(d) { return d.x; })
        .attr('cy', function(d) { return d.y; })
        .style('fill', function(d) { return self.color(d.id); });
}

/** Get the current graph
    @return {Graph}
*/
D3Graph.prototype.getGraph = function() {
    return this.graph;
}

/** Get the graph width
    @return {number}
*/
D3Graph.prototype.width = function() {
    return this.cfg.width;
}

/** Get the graph height
    @return {number}
 */
D3Graph.prototype.height = function() {
    return this.cfg.height;
}

index.css

#graph {
    padding: 5px;
}

.node {
    stroke: #000000;
    stroke-width: 1.5px;
    fill-opacity: .6;
    stroke-opacity: .4;
}

.link {
    stroke: #999;
    stroke-opacity: .5;
}

.frame {
    stroke: #FF0000;
    stroke-opacity: .3;
    fill: transparent;
}

index.html

<!DOCTYPE html>
<html>
  <head>
    <link rel="stylesheet" href="//netdna.bootstrapcdn.com/bootstrap/3.0.0/css/bootstrap.min.css">
    <link rel="stylesheet" href="//code.jquery.com/ui/1.10.3/themes/smoothness/jquery-ui.css">
    <link href="index.css" rel="stylesheet">
  </head>

  <body>
    <div class="container">

      <div class="row">
        <div class="col-xs-8">
          <div id="graph"></div>
        </div>

        <div class="col-xs-4">
          <table class="table" id="params-table">
            <col width="20%">
            <col width="60%">
            <col width="20%">
            <tr>
              <td colspan="3">
                <button class="btn btn-default" id="do-reset-graph">Reset graph</button>
              </td>
            </tr>
            <tr>
              <td colspan="3">
                <button class="btn btn-default" id="do-reset-params">Reset params</button>
              </td>
            </tr>
            <tr>
              <td colspan="3">
                <button class="btn btn-default" id="do-optimise">Anneal</button>
              </td>
            </tr>
          </table>
        </div>
      </div>

      <div class="row">
        <div class="col-xs-12 text-center text-muted" id="graph">
          References:
          <a href="https://gist.github.com/ivitjuk/7037958">[This app on Gist]</a>
          <a href="http://en.wikipedia.org/wiki/Simulated_annealing">[Simulated annealing]</a>
          <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem">[Travelling salesman problem]</a>
          <a href="https://github.com/mbostock/d3/wiki">[D3]</a>
        </div>
      </div>

    </div>

    <script src="//code.jquery.com/jquery-1.10.1.min.js"></script>
    <script src="//code.jquery.com/ui/1.10.3/jquery-ui.js"></script>
    <script src="//netdna.bootstrapcdn.com/bootstrap/3.0.0/js/bootstrap.min.js"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/lodash.js/2.2.1/lodash.min.js"></script>
    <script src="//d3js.org/d3.v3.min.js" charset="utf-8"></script>
    <script src="d3graph.js"></script>
    <script src="link_set.js"></script>
    <script src="util.js"></script>
    <script src="index.js"></script>

  </body>
</html>

index.js

/** Graph node
    @typedef {Object} Node
    @property {number} x X coordinate
    @property {number} y Y coordinate
    @property {number} id Id
*/

/** Graph link
    @typedef {Object} Link
    @property {Node} source Source node
    @property {Node} target Target node
*/

/** Graph
    @typedef {Object} Graph
    @property {Array<Node>} nodes List of nodes
    @property {Array<Link>} links List of links
*/

$(document).ready(function() {
    var graph = new D3Graph('#graph',
                            { height: 350 });


    util.initParameters($('#params-table'));

    $('#do-reset-params').click(function() { util.resetParams(['nNodes']); });


    $('#param-nNodes').on('slide', function(event, ui) {
        util.resetGraph(graph, ui.value);
    });


    $('#do-reset-graph').click(function(e) {
        e.preventDefault();
        util.resetGraph(graph, $('#param-nNodes').slider('value'));
    });


    $('#do-optimise').click(function(e) {
        e.preventDefault();

        var annealing = new Worker("annealing_worker.js");

        annealing.onmessage = function (event) {
            console.log("Annealing message: " + event.data);
        };

        annealing.postMessage({ graph: graph.getGraph(),
                                cfg: {}});
    });


    util.resetParams();
    util.resetGraph(graph, $('#param-nNodes').slider('value'));
});

link_set.js

/**
   Track added links. Only keep unique.
   @constructor
   @property {Array<Link>} links A set of unique links
*/
var LinkSet = function() {
    this.linkSet = {};
    this.links = [];
}


/** Add a link
    @function
    @param {Link} l Link
*/
LinkSet.prototype.addLink = function(l) {
    var lname = String(l.source.id) + String(l.target.id);
    if(!this.linkSet.hasOwnProperty(lname)) {
        this.links.push(l);
        this.linkSet[lname] = true;
        this.linkSet[String(l.target.id) + String(l.source.id)] = true;
    }
}

util.js

/**
   @typedef util~ApplicationParameters
   @property {number} temp Initial annealing temperature
   @property {number} alpha Cooling factor
   @property {number} nIter Number of annealing iterations
   @property {number} k Normalising constant
   @property {number} nNodes Number of graph nodes
  */

/** Utilities
    @namespace
*/
var util = {
    /** Generate a random planar graph
        @function
        @param {Object} cfg - Configuration
        @param {number} cfg.nNodes - Number of nodes in the graph
        @param {number} cfg.height - Height of the graph map
        @param {number} cfg.width  - Width of the graph map
        @return {Graph} Generated graph
    */
    generateGraph: function(cfg) {

        var cfg = _.extend({
            height: 100,
            width: 100,
            nNodes: 10,
        }, cfg);

        var nodes = _.map(_.range(cfg.nNodes), function(n) {
            return {
                id: n,
                x: 10 + Math.random() * (cfg.width-20),
                y: 10 + Math.random() * (cfg.height-20),
            };
        });

        var delaunay = d3.geom.voronoi().triangles(_.map(nodes, function(n) {
            var ret = [n.x, n.y];
            ret.id = n.id;
            return ret;
        }, this));


        var linkset = new LinkSet();

        _.each(delaunay, function(d) {
            linkset.addLink({
                source: nodes[d[0].id],
                target: nodes[d[1].id]
            });

            linkset.addLink({
                source: nodes[d[1].id],
                target: nodes[d[2].id]
            });

            linkset.addLink({
                source: nodes[d[2].id],
                target: nodes[d[0].id]
            });
        }, this);

        return {
            nodes: nodes,
            links: linkset.links
        };
    },

    /** Calculate length of a link
        @param {Link} l A link
        @return {number} Length of the link
    */
    linkLength: function(l) {
        return Math.sqrt(Math.pow(l.source.x - l.target.x, 2) +
                         Math.pow(l.source.y - l.target.y, 2));
    },

    /** Application parameters
        @type {util~ApplicationParameters}
      */
    params: {
        temp:   { min: 0.0, max: 100.0,  step: 0.1,  value: 1.0 },
        alpha:  { min: 0.0, max: 1.0,    step: 0.01, value: 0.9 },
        nIter:  { min: 1,   max: 999,    step: 1,    value: 100 },
        k:      { min: 0.0, max: 1.0,    step: 0.01, value: 0.01 },
        nNodes: { min: 10,  max: 200,    step: 5,    value: 50 }
    },


    /** Initialise parameters ui table
        @param {Object} parent - Parent table jQuery object
      */
    initParameters: function(parent) {
        var table = $('#params-table');

        _.each(util.params, function(param, name) {
            var row = $('<tr>');
            row.append($('<td>').text(name));
            row.append($('<td>').append($('<div>').prop('id', 'param-' + name)));
            row.append($('<td>').append($('<div>').prop('id', 'value-' + name)));
            table.append(row);
        });
    },

    /** Reset all parameters to their default values
        @param {Array<string>} [ignore=[]] A list of parameters to ignore
     */
    resetParams: function(ignore) {
        ignore = ignore || [];

        _.each(util.params, function(param, name) {
            if(_.indexOf(ignore, name) >= 0) {
                return;
            }

            $("#param-" + name).slider(
                _.extend(param, { orientation: "horizontal",
                                  slide: function(event, ui) {
                                      $('#value-' + name).text(ui.value);
                                  }
                                }
                        ));
            $('#value-' + name).text(param.value);
        });
    },

    /** Reset the graph
        @param {Graph} graph The graph
        @param {number} nnodes Number of nodes
      */
    resetGraph: function(graph, nnodes) {
        graph.setGraph(util.generateGraph({
            height: graph.height(),
            width: graph.width(),
            nNodes: nnodes
        }));
    }
}