Code viewer for World: Breadth-first search (Kevi...

See raw JS.

// Cloned by Pavan Kirageri on 14 Oct 2021 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 = [];
    // 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/pk1997/test1.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);
    console.log("graph start is", graph.start)
    // Run the search!
    bfs();
}
let success = false;

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?
        console.log(success)
        if (node == graph.end || success) {
            success = true
            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];
                console.log(graph.end, neighbor)
                // Any neighbor not already searched add to queue
                if (graph.end === neighbor) {
                    {
                        console.log("inside if ")
                        success = true
                        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;
                    }
                }
                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 = path.length > 0 ? '<h1> Path length ' + path.length + '</h1>' : '<h1> Path cannot be found</h1>';

    for (var i = path.length - 1; i >= 0; i--) {
        s = s + path[i].label + "<br>";
    }

    AB.newDiv("theoutput");

    $("#theoutput").css({
        "margin": "30",
        "padding": "30",
        "display": "inline-block",
        "border": "1px solid black"
    });

    $("#theoutput").html(s);


}