Assignment_14

Assign14

by dhizzybusy

HTML

<p id="Assignment 14">
  Graphs
</p>

<p>
In your Fiddle give one application of where a Graph is used by nearly everyone on nearly a daily basis (with the cost function). This is not a trick question.
</p>
<p>
We use graphs primarily in navigation whether through Google Maps or Apple Maps. These applications give us the optimal path or quickest route to our destination or destinations of choice.
</p>
<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" />

JavaScript

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


graph.prototype.add_node = function (label) {

this.edges[label] = {};
};

graph.prototype.add_edge = function (from, to, cost) {
  
this.edges[from][to] = cost;
this.edges[to][from] = cost;
};

graph.prototype.calculate_paths = function (from, to, cost, paths) {
paths.push(from);

if (from == to) {
  
display_path(paths, cost);
} else {
  
for (var connected in this.edges[from]) {
if (paths.indexOf(connected) < 0) {

var thiscost = this.edges[from][connected];
this.calculate_paths(connected, to, cost + thiscost, paths);
}
}
}
paths.pop();
};

function display_path(paths, cost) {
  
var value = paths[0];
for (var i = 1; i < paths.length; i++) {
value = value + ", " + paths[i];
}
value += ": " + cost;

  
var result = document.getElementById('result');
result.innerHTML += value + "<br />";
}

window.calculate = function () {
  
var result = document.getElementById('result');
result.innerHTML = "";


var from = document.getElementById('from').value;
var to = document.getElementById('to').value;

  

var g = new graph();

g.add_node('A');
g.add_node('B');
g.add_node('C');
g.add_node('D');
g.add_node('E');
g.add_node('F');
g.add_node('G');

  
g.add_edge('A', 'B', 1);
g.add_edge('A', 'C', 2);
g.add_edge('B', 'D', 1);
g.add_edge('B', 'G', 1);
g.add_edge('C', 'D', 1);
g.add_edge('C', 'E', 1);
g.add_edge('D', 'E', 1);
g.add_edge('D', 'F', 2);
g.add_edge('D', 'G', 1);

  
result.innerHTML = from + " to " + to + "<br />";
g.calculate_paths(from, to, 0, []);
};