LAP-JV simple example [UNLISTED]

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.

<!DOCTYPE html>
<head>
  <meta charset="utf-8">
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="https://raw.githack.com/fil/lap-jv/master/lap.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 = 12, n = m * m, w = Math.ceil(480/m);
    
    const data = d3.range(n).map(k => [m * Math.random(), m * Math.random()]);
    
    data.map(d => d.color = d3.rgb(Math.random()*255, Math.random()*255, Math.random()*255));
    
    svg.selectAll('line')
    .data(data)
    .enter()
    .append('line')

svg.selectAll('circle')
    .data(data)
    .enter()
    .append('circle')
    .attr('r', 13)
    .attr('cx', d => w * d[0])
    .attr('cy', d => w * d[1])
    .attr('fill', d => d.color);

const costs = data.map(d => d3.range(n).map( k => {
      const 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;
    }));

draw(lap(n, costs));

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')
    .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);

}, 1500);
  }

</script>
</body>

Updated missing url https://raw.githack.com/Fil/lap-jv/master/lap.js to https://raw.githack.com/fil/lap-jv/master/lap.js

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

https://raw.githack.com/Fil/lap-jv/master/lap.js