LAP-JV Worker

LAP-JV

Linear Assignment Problem — algorithm by R. Jonker and A. Volgenant

Ported to javascript by Philippe Rivière, from the C++ implementation found at https://github.com/yongyanghz/LAPJV-algorithm-c

See Fil/lap-jv for details, and a simpler example.

<!DOCTYPE html>
<head>
  <meta charset="utf-8">
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <style>
    body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
  </style>
</head>

<body>
  <script>
    // Feel free to change or delete any of the code you see in this editor!
    var svg = d3.select("body").append("svg")
      .attr("width", 960)
      .attr("height", 500)

const m = 40, n = m * m, w = Math.ceil(480/m);
    
    // const data = d3.range(n).map(k => [Math.floor(100 * m * (2 + Math.cos( k ))/4)/100, Math.floor(100 * m * (2 + Math.sin(k))/4)/100]);
    const data = d3.range(n).map(k => [m * Math.random(), m * Math.random()]);
    // const data = d3.range(n).map(k => [m * (1 + Math.cos(k))/2, m * (1 + Math.sin(k))/2]);
    // const data = d3.range(n).map(k => { const i = k % m, j = (k-i)/m; return [i + Math.random(),j + Math.random()]; });
    
    data.map(d => d.color = d3.rgb(Math.random()*255, Math.random()*255, Math.random()*255));
    
    svg.selectAll('circle')
    .data(data)
    .enter()
    .append('circle')
    .attr('r', 3);
    
    svg.selectAll('circle')
    .attr('cx', d => w * d[0])
    .attr('cy', d => w * d[1])
    .attr('fill', d => d.color);

createWorker('worker.js', (worker) => {
      const start = performance.now();
     worker.postMessage({
           m: m,
           data: data,
     });

worker.onmessage = function (e) {
       if (e.data.assign) {
         console.log(n + ': ' + Math.ceil(performance.now() - start) + 'ms')
         draw(e.data.assign);
       }
     }
    });

function draw(res) {
    res.col.map((c, k) => {
      const i = k % m, j = (k-i)/m;
      data[c].i = i;
      data[c].j = j;
    });
  svg.selectAll('line')
    .data(data)
    .enter()
    .append('line')
    .attr('x1', d => w * d[0])
    .attr('y1', d => w * d[1])
    .attr('x2', d => w * d[0])
    .attr('y2', d => w * d[1])
    .attr('stroke', d => d.color)
    .attr('opacity', 0.8)
    .transition()
    .duration(1500)
    .attr('x2', d => w/2 + w * d.i)
    .attr('y2', d => w/2 + w * d.j)
    ;

setTimeout(function() {
      svg.selectAll('circle')
      .transition()
    .duration(500)
    .attr('cx', d => w/2 + w * d.i)
    .attr('cy', d => w/2 + w * d.j);
     if (false) svg.selectAll('line')
        .transition()
    .attr('x1', d => w/2 + w * d.i)
    .attr('y1', d => w/2 + w * d.j)
    .duration(500)

}, 1500);
  }

function createWorker(s, cb) {
  const worker = new Worker(window.URL.createObjectURL(new Blob([`
importScripts('https://raw.githack.com/Fil/lap-jv/master/lap.js');
self.onmessage = function(e){
  const m = e.data.m,
        n = m * m,
        data = e.data.data;
  const costs = function(a, k) {
    const d = data[a],
        i = k % m,
        j = (k-i)/m;
    const dx = d[0] - i - 0.5, dy = d[1] - j - 0.5;
    return dx * dx + dy * dy;
  };

self.postMessage({
    assign: lap(n, costs)
  });
};`], {
     type: "text/javascript"
  })));
  if (typeof cb == 'function') {
    cb(worker);
  }
}
  
  </script>
</body>

https://d3js.org/d3.v4.min.js