MOD 11 - GRAPHS V5

by SHELDON PASCIAK

HTML

VERSION 5

GRAPH - finds paths between points<br /><br />

Uses queue and breadth first search to find all paths<br /><br />

Note --> Partial working recursive version included in this cost - but recursive version currently only finds the FIRST path it finds, not all paths or the shortest.<br /><br />
P.S. I read that the recursive version isn't good for very large graphs<br />
<BR />



<!--

Module 11 - Graphs - VERSION v4! - BASE - SHELDON PASCIAK

QUEUE VERSION
    queue version works well

RECURSIVE VERSION

    STILL A WORK IN PROGRESS -- recursive vrsion only finds one path, not the shortest and not all!

    REF: https://www.cs.bu.edu/teaching/c/tree/breadth-first/

 

Introduction

Graphs are possibly the most complex of the basic data structures you will deal with. They are covered in Topic - Graph Data Structures .
 
Assignment
 
This is your toughest assignment. Given the Graph shown (ignore pointers this is an undirected graph) - 
 
Allow the user to select 2 nodes. Then calculate and display the cost of each path between the 2 nodes.
F to C 
F, D, C: 2
F, D, E, C: 4
F, D, B, A, C: 5
F, D, G, B, A, C: 7

-->

Select two nodes:
 From: 
<select id="from">
    <option value='A'>A</option>
    <option value='B'>B</option>
    <option value='C'>C</option>
    <option value='D'>D</option>
    <option value='E'>E</option>
    <option value='F' selected>F</option>
    <option value='G'>G</option>
</select> 
 To: 
<select id="to">
    <option value='A'>A</option>
    <option value='B'>B</option>
    <option value='C' selected>C</option>
    <option value='D'>D</option>
    <option value='E'>E</option>
    <option value='F'>F</option>
    <option value='G'>G</option>
</select>
<input type="button" onclick="calculate();" value="Calculate" />
<br/>
<br/><span id="result" />


<!--

Allow the user to select 2 nodes. Then calculate and display the cost of each path between the 2 nodes.
F to C 
F, D, C: 2
F, D, E, C: 4
F, D, B, A, C: 5
F, D, G, B, A, C:...

JavaScript

// module 11 - program 1 - VERSION 5 - SHELDON PASCIAK
// This is a basic implementation of a Graph
// QUEUE version and RECURSIVE version

function Node(data) {
    this.data = data;
    this.neighbors = null; // addEdge smartly creates [] as needed
}

function Graph() {

    this.edges = {};

    this.visited = [];

    this.addNode = function (label) {
        this.edges[label] = new Node(label);
    };

    this.neighbors = function (label) {  
        return this.edges[label].neighbors;
    };

    this.addEdge = function (from, to, cost) {
        if (!(this.edges[from].neighbors)) this.edges[from].neighbors=[];
        if (!(this.edges[to].neighbors)) this.edges[to].neighbors=[];
        this.edges[from].neighbors.push(to);        
        this.edges[to].neighbors.push(from);
        this.edges[from][to] = cost;
        this.edges[to][from] = cost;
    };

    this.calculatePaths = function (from, to, cost, paths) {

        paths.push(from);   

        //document.getElementById('output').innerHTML += paths + "<br />";

        if (from==to) {              
            console.log("Found:" + paths + " cost:" + cost);
            this.displayPath(paths,cost);
            document.getElementById('output').innerHTML += paths + "<br />";
            return paths;
        }          

        var theN = this.edges[from].neighbors;   

        for (var i=0;i<theN.length;i++) {
            //document.getElementById('output').innerHTML += paths + " next neighbors " + theN + " <br />";
            if (paths.indexOf(theN[i])<0) {   
                if (this.edges[theN[i]][from]) cost += this.edges[theN[i]][from];
                return this.calculatePaths(theN[i],to,cost,paths);  
            }

        }

        return null;

    };    

    //used for recursive version - uses cost calc at it progresses
    this.displayPath = function (path, cost) {
        var strResult="";
        if (!path) return;
        strResult = path.toString() + " : " + cost;
       ...