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.

See also LAP-JV Worker.

Using d3-annotation() by @susielu.

forked from Fil's block: LAP-JV

<!DOCTYPE html>
<head>
  <meta charset="utf-8">
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="https://cdn.jsdelivr.net/gh/fil/lap-jv/lap.js"></script>
<script src="https://cdn.jsdelivr.net/gh/susielu/d3-annotation/d3-annotation.js"></script> 
  
<link rel="stylesheet" href="d3-annotation.css">  
  <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 = 7, n = m * m, w = Math.ceil(440/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)
    .attr('fill-opacity', 0.5);

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;
      data[c].cost = costs[c][k];
    });

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);
  
  const max = d3.scan(data.map(d => -d.cost)),
        annotation = d3.annotation()
        .type(d3.annotationCalloutCircle)
        .annotations(
          [data[max]]
          .map(d => {
           return {
            data: d,
            dx: 25,
            dy: 15,
            note: {
               title: "Most expensive attribution",
               label: "cost: "+ d3.format('$0.2f')(Math.sqrt(d.cost)),
            },
            subject: {
              radius: 17,
              radiusPadding: 2,
            },
          }
        }))
        .accessors({ x: d => w/2 + w * d.i, y: d =>  w/2 + w * d.j })

setTimeout(() => {
    svg.append("g")
        .attr("class", "annotation-centroids")
        .call(annotation)    
   }, 1800)
  }

</script>
</body>

Updated missing url https://cdn.rawgit.com/Fil/lap-jv/master/lap.js to https://cdn.jsdelivr.net/gh/fil/lap-jv/lap.js

Updated missing url https://cdn.rawgit.com/susielu/d3-annotation/master/d3-annotation.js to https://cdn.jsdelivr.net/gh/susielu/d3-annotation/d3-annotation.js

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

https://cdn.rawgit.com/Fil/lap-jv/master/lap.js

https://cdn.rawgit.com/susielu/d3-annotation/master/d3-annotation.js