Fil/.block

## .block
license: mit
border: no

## README.md

      
    Raw
  

              README.md
            
          
    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 and LAP-JV with annotation.

  
## index.html
<!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>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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>