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
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