// 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: "); // 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; } // 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].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; } // 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); } } // 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(); // 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); } function findbacon() { // Clear everyone from having been searched graph.clear(); // Start and end var start = actors[actorlist.value()]; 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 = 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) { console.log ("adding unsearched neighbour " + neighbor.label + " to queue"); queue.push(neighbor); // Update the parent neighbor.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'); // path = bacon + movie + x + movie + x ... + movie + x var s = '