Visualizing 

NP-Complete Problems


December 3, 2013

P V

NP-What?

  • Class of problems
  • Polynomial time to verify solution
  • No known efficient way to find solution
  • Examples:
    • Traveling Salesman Problem
    • Graph Coloring Problem
    • Knapsack Problem

Randall Munroe's take on NP-Complete


D3.js + Data = ♥


...where's my data...

Generate it as we solve the problem!





NP-Food

Building Data


  • Problem solved via recursion
  • Create a tree that follows the recursion path
  • Dynamically populate tree with essential info:
    • Append as children new selections
    • Update parents as info about children is discovered

Building Data

vis = {
    "cost" : 2250,
    "known" : false,
    "tray" : [],
    "branch" : [
        {
            "cost" : -248,
            "known" : true,
            "isGood" : false,
            "branch" : [],
            "tray" : [...]
        },
        {
            "cost" : 1151,
            "known" : true,
            "isGood" : true,
            "tray" : [...],
            "branch" : [...]
        }
    ]
}       

Using Data

Prepare a  d3.layout.cluster()
var cluster = d3.layout.cluster()
                .size([360,1])
                .value(function(d) { return d.cost; })
                .children(function(d) { return d.branch; });
Enter the data
var nodes = cluster.nodes(vis);
Massage the nodes to have the appropriate x-coordinates
(done similarly to Phylogenetic Tree of Life
credit to Jason Davies)

Using the Data

Append the nodes!

var node = visual.selectAll("g.node")
    .data(nodes.filter(function(n) { return n.x !== undefined; }))
    .enter().append("circle")
    .attr("transform", function(d) { return "rotate(" + (d.x - 90) + ") translate(" + d.y + ")"; })
    .attr("r", function(d) { return d.isGood ? 4 : 2.5; })
    .attr('fill', nodeFill)
    .on('click', function(d) { showToolTip(d); })
    .attr('class', 'invisib')
    .transition()
    .attr('class', function(d) { return nodeClass(d); })
    .delay(function(d, i){ 
      if(nodes.length < 15){
        return i*(1000/nodes.length);
      }
      return i*(5000/nodes.length);
    })
    .duration(0);
    

Using the Data

Similar idea for the links

Using the Data

On drawing finish, programmatically click the "closest" node

window.setTimeout(function() {
    var c = d3.select($('.close-cost')[0]); 
    c.on('click')(c[0][0]);
  }, nodes.length < 15 ? 1500 : 5500);
    

Thank you!



Feel free to reach out


@poviro

Visualizing NP-Complete Problems

By liviro

Visualizing NP-Complete Problems

Given during the December NYC D3.js Meetup.

  • 1,355