Graphs

Graphs are possibly the most complex of the basic data structures you will deal with. This is your toughest assignment. Given the Graph shown... 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

by Neil Daley

HTML

<h1>Graphs</h1>

This assignment allows the user to select 2 nodes, then calculate and display the cost of each path between the 2 nodes.<br/>

<div><br/>
Select two nodes:
<br/>
From
<select id="source">
    <option value='A'selected >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'>F</option>
    <option value='G'>G</option>
</select>
To
<select id="destination">
    <option value='A'>A</option>
    <option value='B' selected>B</option>
    <option value='C'>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" style="color:white; background-color:blue" /><br/><br/>

<div id="result"></div><br /><br/>

<b><div id="fastest"><br />
</div></b>

JavaScript

var option = 0; // each path is an option
var best = 10000; // finding the best cost
var fastest = []; // an array to hold the fastest routes

// Graph function initially only contains an empty object  
function Graph() {
    this.edges = {};
}

// prototype for adding new nodes
Graph.prototype.addNode = function (letter) {

    // an adjacency list(array) for the edges
    this.edges[letter] = {};
};

// prototype for adding new edges
Graph.prototype.addEdge = function (source, destination, cost) {

    // undirected graph
    this.edges[source][destination] = cost;
    this.edges[destination][source] = cost;
};

// prototype for adding a new calculation call which is empty at the moment of invocation
Graph.prototype.calculate = function (source, destination, cost, paths) {

    // adding the current source to the path
    paths.push(source);
    
    // permutate and display all paths and costs using recursion
    if (source == destination) { 
    
    	// calling the function that handles the output
        display(paths, cost);
    } else { 
    	// if not we traverse the adjacency list
        for (var connected in this.edges[source]) {
        
        		// 'indexOf()'' method returns the first index
            if (paths.indexOf(connected) < 0) { 
            
 // if '< 0' then not visited yet store the current cost in "thisCost"
                var thisCost = this.edges[source][connected];
                
                // recurse back with the added cost
                this.calculate(connected, destination, cost + thisCost, paths);
            }
        }
    }
    paths.pop();
};

// function to display the results receives 2 arguments 
function display(paths, cost) {
	var value = paths[0]; 
  
  //we create a variable to hold the output value. 
  for (var i = 1; i < paths.length; i++) {
  
  	// add each node to the end of "value"
    value = value + " -to- " + paths[i];
  }
  option++;
  
  // the 'option' counter is increased
  value += " | cost =...