// Cloned by Harpreet Singh on 22 Oct 2019 from World "Breadth-first search (Kevin Bacon)" by "Coding Train" project
// Please leave this clone trail here.
// Breadth-first search
// Port from:
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs/P2_six_degrees_kevin_bacon
// https://www.youtube.com/watch?v=piBq7VD0ZSo
// Hard to visualise graph
AB.headerRHS();
AB.newDiv("selectdiv");
$("#selectdiv").css({
"margin-top": "200",
"float": "right"
});
$("#selectdiv").html("Pick an actor: <span id='actorlist'></span> ");
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Graph object
function Graph()
{
// store nodes by key and also in an array
this.graph = {};
this.nodes = [];
// Start and end
this.start = null;
this.end = null;
// Now a "rest distance" between nodes
this.springLength = 64;
}
// Set the start
Graph.prototype.setStart = function(node)
{
this.start = node;
}
// Set the end
Graph.prototype.setEnd = function(node)
{
this.end = node;
}
// Add a node
Graph.prototype.addNode = function(label)
{
var n = new Node(label);
// Add to both the graph object and the nodes array
this.graph[label] = n;
this.nodes.push(n);
return n;
}
// Clear all searched and parent values
Graph.prototype.clear = function()
{
for (var i = 0; i < this.nodes.length; i++)
{
this.nodes[i].searched = false;
this.nodes[i].inQueue = false;
this.nodes[i].parent = null;
this.nodes[i].col = color(0);
}
}
// Draw everything
Graph.prototype.show = function() {
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].showEdges();
}
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].show();
}
}
// Simulate some physics!
Graph.prototype.simulate = function() {
// First node always in center
this.nodes[0].pos.set(width / 2, height / 2);
// Look at every node against every other node
for (var i = 1; i < this.nodes.length; i++) {
var node1 = this.nodes[i];
for (var j = 0; j < this.nodes.length; j++) {
// Nodes don't interact with themselves!
if (i == j) continue;
var node2 = this.nodes[j];
// A vector that points between the nodes
var force = p5.Vector.sub(node1.pos, node2.pos);
var dist = force.mag();
// What is spring force?
var spring = 0;
var k = 0.06;
// If they are connected calculate
if (node1.isConnected(node2) || node2.isConnected(node1)) {
spring = k * (this.springLength - dist);
}
// All nodes need their own space even if not connected
var separate = 1 / (dist * k);
// Apply the force!
force.setMag(spring + separate)
node1.vel.add(force);
// Slow down velocity so that it dampens over time
node1.vel.mult(0.95);
}
}
// Add velocity to position for all nodes
for (var i = 0; i < this.nodes.length; i++) {
var node = this.nodes[i];
node.pos.add(node.vel);
}
}
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Node object
function Node(label)
{
// Nodes have physics now!
this.pos = createVector(random(width),random(height));
this.vel = createVector();
// And a color
this.col = color(0);
// Has a label
this.label = label;
// zero or more edges
this.edges = [];
// No parent and not searched by default
this.parent = null;
this.searched = false;
this.inQueue = false;
}
// Connect one or more neighbors
Node.prototype.connect = function(neighbor) // one Node (movie) has a connection to another Node (person)
{
// This is a fancy way of having a function
// that can accept a variable number of arguments
for (var i = 0; i < arguments.length; i++)
{
this.edges.push(arguments[i]); // increase the size of the array
// Connect both ways
arguments[i].edges.push(this);
}
}
// Is this node connected to another node?
Node.prototype.isConnected = function(neighbor) {
var index = this.edges.indexOf(neighbor);
if (index >= 0) {
return true;
} else {
return false;
}
}
// Draw!
Node.prototype.show = function() {
textAlign(CENTER);
var w = textWidth(this.label);
stroke(255);
fill(this.col);
ellipse(this.pos.x, this.pos.y, 30, 30);//w * 2, w * 2);
fill(255);
noStroke();
text(this.label, this.pos.x, this.pos.y);
}
// Highlight!
Node.prototype.highlight = function() {
this.col = color(0, 150, 0);
}
// Draw connections as lines
Node.prototype.showEdges = function() {
noFill();
stroke(255);
for (var i = 0; i < this.edges.length; i++) {
line(this.pos.x, this.pos.y, this.edges[i].pos.x, this.edges[i].pos.y);
}
}
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// The data
var data;
// The graph
var graph;
// A lookup table for actors
// (redundant, the graph could handle this)
var actors;
// Dropdown menu for actors
var actorlist;
function preload()
{
data = loadJSON('/uploads/codingtrain/bacon.json');
}
function setup()
{
//noCanvas();
createCanvas(1200, 750);
// Create the graph
graph = new Graph();
// A separate lookup table for actors
actors = {};
// For all movies
var movies = data.movies;
for (var i = 0; i < movies.length; i++)
{
// Title and castlist
var movie = movies[i].title;
var cast = movies[i].cast;
// Add the movie to the graph
var movieNode = graph.addNode(movie); // Node movie
// Go through all the cast list
for (var j = 0; j < cast.length; j++)
{
var name = cast[j];
var actorNode;
// Does the actor exist already?
if (actors[name]) actorNode = actors[name];
// If not add a new node
else
{
actorNode = graph.addNode(name); // Node person
actors[name] = actorNode;
}
// Connect movie and actor
movieNode.connect(actorNode); // movie connects to person
}
}
// Create dropdown
actorlist = createSelect(); // https://p5js.org/reference/#/p5/createSelect
actorlist.parent('actorlist');
var allactors = Object.keys(actors);
// Add all the actors
for (var i = 0; i < allactors.length; i++)
actorlist.option(allactors[i]);
// Set up an event
actorlist.changed(findbacon);
//findbacon();
}
function findbacon()
{
// Clear everyone from having been searched
graph.clear();
// Start and end
var start = actors[actorlist.value()];
//var start = actors['Tim Daly'];
var end = actors['Kevin Bacon'];
graph.setStart(start);
graph.setEnd(end);
// Run the search!
bfs();
}
function bfs()
{
// Create a queue ad path
var queue = [];
var path = [];
// Get started
queue.push(graph.start);
while (queue.length > 0) // inside the loop we keep adding things to queue
{
var node = queue.shift(); // remove first item
console.log ("======" );
console.log ("start of search of " + node.label);
// Are we done?
if (node == graph.end)
{
console.log ("found goal node");
// Figure out the path
path.push(node);
var next = node.parent;
while (next)
{
path.push(next);
next.inQueue = true;
next = next.parent;
}
break;
}
else
{
console.log ("checking neighbours of " + node.label);
// Check all neighbors
var next = node.edges;
// console.log ("checking " + next.length + " neighbours");
for (var i = 0; i < next.length; i++)
{
var neighbor = next[i];
// Any neighbor not already searched add to queue
if (!neighbor.searched && !neighbor.inQueue)
{
console.log ("adding unsearched neighbour " + neighbor.label + " to queue");
queue.push(neighbor);
// Update the parent
neighbor.inQueue = true;
neighbor.parent = node;
}
}
// Mark node as searched
node.searched = true;
console.log ("end of search of " + node.label);
// console.log ("======" );
}
} // end of while loop
for (var i = 0; i < path.length; i++) {
path[i].highlight();
}
//drawGraph();
showDiv(path);
}
function draw() {
background(51);
graph.simulate();
graph.show();
}
function showDiv(path){
// now output path
console.log('finished search for path');
// path = bacon + movie + x + movie + x ... + movie + x
var s = '<h1> Path length ' + path.length + '</h1>';
for (var i = path.length-1; i >= 0; i--)
{
//for every alternate item change the color
if (i%2 == 0)
s = s + "<span style=\"color:green\"><b>" + path[i].label + "</b></span>" + "<br>";
else
s = s + "<span style=\"color:red\">" + path[i].label + "</span><br>";
}
AB.newDiv("theoutput");
$("#theoutput").css({
"margin-top": "100",
"margin-left": "1300",
"display": "inline-block",
"border": "1px solid black"
});
$("#theoutput").html(s);
}