// Cloned by Tristan Everitt on 29 Sep 2022 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": "30",
});
$("#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 = [];
this.edges = [];
// Start and end
this.start = null;
this.end = null;
}
// 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) {
let 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 (const element of this.nodes) {
element.searched = false;
element.parent = null;
}
};
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Node object
function Node(label) {
// 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.actor = false;
this.film = false;
this.x = AB.randomIntAtoB(0, width / 1.2);
this.y = AB.randomIntAtoB(0, height / 1.2);
this.hits = 1;
this.visited = false;
}
function Edge(start, end) {
this.start = start;
this.end = end;
}
// Connect one or more neighbors
Node.prototype.connect = function (neighbour) // 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 (const element of arguments) {
this.edges.push(element); // increase the size of the array
// Connect both ways
element.edges.push(this);
graph.edges.push(new Edge(this, element));
graph.edges.push(new Edge(element, this));
}
};
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// The data
let data;
// The graph
let graph;
// A lookup table for actors
// (redundant, the graph could handle this)
let actors;
// Dropdown menu for actors
let actorlist;
function preload() {
data = loadJSON('/uploads/tristan/exercise3.9-breadth-first-bacon.json');
}
function setup() {
createCanvas(ABWorld.fullwidth(), ABWorld.fullheight());
// Create the graph
graph = new Graph();
// A separate lookup table for actors
actors = {};
// For all movies
for (const movie of data.movies) {
// Add the movie to the graph
let movieNode = graph.addNode(movie.title); // Node movie
movieNode.film = true;
// Go through all the cast list
for (const cast of movie.cast) {
let actorNode;
// Does the actor exist already?
if (actors[cast]) {
actorNode = actors[cast];
}
// If not add a new node
else {
actorNode = graph.addNode(cast); // Node person
actors[cast] = actorNode;
}
actorNode.actor = true;
// Connect movie and actor
movieNode.connect(actorNode); // movie connects to person
}
}
// Create dropdown
actorlist = createSelect(); // https://p5js.org/reference/#/p5/createSelect
actorlist.parent('actorlist');
// Add all the actors
for (const actor of Object.keys(actors)) {
actorlist.option(actor);
}
// Set up an event
actorlist.changed(findbacon);
}
function findbacon() {
// Clear everyone from having been searched
graph.clear();
// Start and end
let start = actors[actorlist.value()];
start.colour = 'red';
let end = actors['Kevin Bacon'];
end.x = width / 2;
end.y = height / 2; // Mr Bacon is the centre of the universe
end.colour = 'green';
graph.setStart(start);
graph.setEnd(end);
// Run the search!
bfs();
}
function reachedDestination(node) {
console.log("found goal node: " + node.label);
let path = [];
// Figure out the path
path.push(node);
node.visited = true;
let next = node.parent;
while (next) {
path.push(next);
next.visited = true;
next = next.parent;
}
return path;
}
function bfs() {
// Create a queue ad path
let queue = [];
let path = [];
// Get started
queue.push(graph.start);
for (const n of graph.nodes) {
n.visited = false;
}
while (queue.length > 0) // inside the loop we keep adding things to queue
{
let node = queue.shift(); // remove first item
console.log("======");
console.log("start of search of " + node.label);
// Are we done?
if (node === graph.end) {
path = reachedDestination(node);
break;
} else if (node.searched) {
// TE Bug-fix
console.log("previously search so skip: " + node.label);
} else {
console.log("checking neighbours of " + node.label);
// Check all neighbors
// console.log ("checking " + next.length + " neighbours");
for (const neighbour of node.edges) {
// Any neighbour not already searched add to queue
if (!neighbour.searched) {
if (neighbour === graph.end) {
// TE Bug-fix
// Update the parent
neighbour.parent = node;
path = reachedDestination(neighbour);
queue = [];
break;
} else {
console.log("adding unsearched neighbour " + neighbour.label + " to queue");
queue.push(neighbour);
// Update the parent
neighbour.parent = node;
}
}
}
// Mark node as searched
node.searched = true;
console.log("end of search of " + node.label);
// console.log ("======" );
}
} // end of while loop
// now output path
console.log('finished search for path');
clear();
ready = true;
let msg = 'Path length: ' + path.length;
msg += '<br/>F=Film | S=Start | E=End';
msg += '<br/>Tip: Hover over nodes for details.';
msg += '<br/>Tip: Click on the dropdown and use the up-down arrow to re-draw lines.';
AB.msg(msg);
}
let ready = false;
function draw() {
background(255);
if (graph !== null && ready) {
for (const n of graph.nodes) {
n.show();
}
for (const e of graph.edges) {
e.showLine();
}
}
}
// Draw connections as lines
Edge.prototype.showLine = function () {
noFill();
const visited = this.start.visited && this.end.visited;
stroke(visited ? 'blue' : 'grey');
strokeWeight(visited ? 2 : 0.15);
line(this.start.x, this.start.y, this.end.x, this.end.y);
};
Node.prototype.show = function () {
textAlign(CENTER);
let v;
const start = graph.start.label === this.label;
const end = graph.end.label === this.label;
stroke(0);
let hoverOverLabel = true;
if (start) {
fill('green');
v = 'S';
let w = textWidth(v);
ellipse(this.x, this.y, w * 8, w * 8);
//hoverOverLabel = true;
} else if (end) {
fill('red');
v = 'E';
let w = textWidth(v);
ellipse(this.x, this.y, w * 8, w * 8);
//hoverOverLabel = true;
} else if (this.film) {
fill('orange');
v = 'F';
let w = textWidth(v);
ellipse(this.x, this.y, w * 4, w * 4);
//hoverOverLabel = true;
} else {
fill('yellow');
ellipse(this.x, this.y, 5, 5);
}
fill(0);
noStroke();
if (hoverOverLabel && dist(mouseX, mouseY, this.x, this.y) < 10) {
fill(150);
strokeWeight(1);
ellipse(this.x, this.y, 10, 10);
fill(50);
text(this.label, this.x + 15, this.y - 15);
} else {
text(v, this.x, this.y);
}
};