Assignment 14 - Graphs

by aren_anderson

HTML

<h1>
  Graphs
</h1>

<h4>
  Select two nodes:
</h4>
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">F</option>
</select>
 To
 <select id ="to">
  <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">F</option>
</select>
<br/><br/>
<input type="button" id="btnCalculate" value="Calculate Traversal" onclick="calc();" />

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

JavaScript

debugger;


//create graph
function graph(){
	this.edges = {};
}

//method to add node to graph
graph.prototype.addNode = function(name){
	this.edges[name] = {};
}

//method to add edges
graph.prototype.addEdge = function(from, to, cost){
	this.edges[from][to] = cost;
  this.edges[to][from] = cost;
}

//method to calulate paths
graph.prototype.calculate = function(from, to, cost, paths){
	paths.push(from);
  
  if(from == to){
  	printPath(paths, cost);
  }
  else{
  	for (var c in this.edges[from]){
    	if(paths.indexOf(c) < 0){
      	var pathCost = this.edges[from][c];
        this.calculate(c, to, cost + pathCost, paths);
      }
    }
  }
  paths.pop();
}

//function to output the paths
function printPath(paths, cost){
	var v = paths[0];
  for (var i = 1; i< paths.length; i++){
  	v = v + ", " + paths[i];
  }
  v += ": " + cost;
  
  var output = document.getElementById("output");
  output.innerHTML += v + "<br />"
}

window.calc = function(){
	var output = document.getElementById("output");
  output.innerHTML = "";
  var from = document.getElementById("from").value;
  var to = document.getElementById("to").value;
  
  var g = new graph();
  
  g.addNode("A");
  g.addNode("B");
  g.addNode("C");
  g.addNode("D");
  g.addNode("E");
  g.addNode("F");
  g.addNode("G");
  
  g.addEdge("A", "B", 2);
  g.addEdge("A", "C", 1);
  g.addEdge("B", "D", 1);
  g.addEdge("B", "G", 1);
  g.addEdge("C", "D", 1);
  g.addEdge("C", "E", 1);
  g.addEdge("D", "E", 2);
  g.addEdge("D", "F", 1);
  g.addEdge("D", "G", 2);
  
  output.innerHTML = from + " to " + to + "<br/>";
  g.calculate(from, to, 0, []);
}