MOD 11 - GRAPHS V4

by SHELDON PASCIAK

HTML

This version only finds one path.  NOT all paths.  NOT shortest path. <br /><br />

Still working on it...<br /><br />

<!--

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

    STILL A WORK IN PROGRESS -- only finds one path, not the shortest and not all!
 
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:
<br />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: 7

-->

<div id="output"></div>

JavaScript

// module 11 - program 1 - VERSION 4 - SHELDON PASCIAK
// This is a basic implementation of a Graph

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

function Graph() {

    this.edges = {};

    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;   
        
        document.getElementById('output').innerHTML += paths + " next neighbors <br />";
        
        for (var i=0;i<theN.length;i++) {

            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;
        
    };

    this.displayPath = function (path, cost) {
        var strResult="";
        // path could also include cost
        if (!path) return;
        //for (var i=0;i<path.length-1;i++){
           // newCost +=...