Graphs are possibly the most complex of the basic data structures you will deal
ID: 673797 • Letter: G
Question
Graphs are possibly the most complex of the basic data structures you will deal with. They are covered in Topic - https://cop3530.pbworks.com/w/page/97920059/Topic%20-%20Graph%20Data%20Structures
Using Javascript and JSFiddle, 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
A JSFiddle with a sample submission of a Graph is at http://jsfiddle.net/reaglin/wykhhuwo/
Please include screenshots and / or templates of the Javascript program Thank you!
Explanation / Answer
var array=[]; var errors=[]; var avalible_paths=[];
var myVertices = ['A','B','C','D','E','F','G'];//valid user entries
var graph = new Graph();
var result, total, start, end;
document.getElementById("click").onclick = function() {myFormSubmit()};
function myFormSubmit() {
array=[], errors=[], avalible_paths=[], graph = new Graph();//reset
start = document.getElementById("start-node").value.toUpperCase();
end = document.getElementById("end-node").value.toUpperCase();
try {
if (start == "") throw "You didn't enter a start node.";
if (myVertices.indexOf(start) == -1) throw "Enter a letter (from A to G) node for start. You entered " + start;
}
catch(err) {
errors.push(err);
}
try {
if (end == "") throw "You didn't enter a end node.";
if (myVertices.indexOf(end) == -1) throw "Enter a letter (from A to G) node end. You entered " + end;
}
catch(err) {
errors.push(err);
}
document.getElementById('output').innerHTML = errors.join("<br>");
if (errors.length == 0) {
//do this if no errors
for (var i=0; i<myVertices.length; i++) {
graph.addVertix(myVertices[i]);
}
graph.addEdge('A','B',2);
graph.addEdge('A','C',1);
graph.addEdge('C','D',1);
graph.addEdge('C','E',1);
graph.addEdge('B','D',1);
graph.addEdge('B','G',1);
graph.addEdge('E','D',2);
graph.addEdge('D','F',1);
graph.addEdge('D','G',2);
document.getElementById('output').innerHTML = graph.toString(start, end);
display_cost_each_path_between_2_nodes(start, end);
document.getElementById('output2').innerHTML = start + ' to ' + end;
document.getElementById('output3').innerHTML = avalible_paths.join("<br>");
}
}
function Dictionary() {
var items = {};
this.has = function(key) {
return key in items;
};
this.set = function(key, value) {
items[key] = value;
};
this.get = function(key) {
return this.has(key) ? items[key] : undefined;
};
}
function Queue() {
var items = [];
this.enqueue = function(element){
items.push( element);
};
this.dequeue = function(){
return items.shift();
};
this.front = function(){
return items[0];
};
this.isEmpty = function(){
return items.length == 0;
};
this.size = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}
function Graph() {
var vertices = [];
var adjList = new Dictionary();
this.addVertix = function(v) {
vertices.push(v);
adjList.set(v, []);
};
this.addEdge = function(v, w, weight) {
adjList.get(v).push(w);
adjList.get(w).push(v);
adjList.get(w).push(weight);//add path weight
adjList.get(v).push(weight);//add path weight
};
//alternate with start and end?
this.toString = function(start, end) {//start and end node passed in
start_index = myVertices.indexOf(start);
end_index = myVertices.indexOf(end);
var s='';
for (var i=0; i<vertices.length; i++) {
var thenum=''; var weights=[]; var check;//for path weight, also reset here
s += vertices[start_index] + ' -> ';
var neighbors = adjList.get(vertices[i]);
for (var j=0; j<neighbors.length; j++) {
function isOdd(num) { return num % 2;}//function to check if number odd
if (isOdd(j) == true) {//weight is all odd numbers
check = neighbors[j] + ' ';// added string to get around neighbors[j].match error
weights.push(parseInt(check.match(/d/g)));//get numbers from string and add to array
}
function isEven(num) { return num % 2 == 0;}//function to check if number even, and skip weight in string
if (isEven(j) == true) {
s += neighbors[j] + ' ';
}
}
s += ':' + eval(weights.join('+')) + /*' '*/ "<br>";
}
return s;
};
//BFS
var initializeColor = function() {
var color = [];
for (var i=0; i<vertices.length; i++) {
color[vertices[i]] = 'white';
}
return color;
};
this.BFS = function(v, callback) {
var color = initializeColor(),
queue = new Queue(),
d = [],
pred = [];
queue.enqueue(v);
for (var i=0; i<vertices.length; i++) {
d[vertices[i]] = 0;
pred[vertices[i]] = null;
}
while (!queue.isEmpty()) {
var u = queue.dequeue(),
neighbors = adjList.get(u);
color[u] = 'grey';
for (var i=0; i<neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === 'white') {
color[w] = 'grey';
d[w] = d[u] +1;
pred[w] = u;
queue.enqueue(w);
}
}
color[u] = 'black';
}
return {
distances: d,
predecessors: pred
};
};
}
function Stack() {
var items = [];
this.push = function(element){
items.push(element);
};
this.pop = function(){
return items.pop();
}; this.peek = function(){
return items[ items.length-1];
}; this.isEmpty = function(){
return items.length == 0;
}; this.size = function(){
return items.length;
}; this.clear = function(){
items = [];
};
this.print = function(){
console.log(items.toString());
};
}
//Allow the user to select 2 nodes. Then calculate and display the cost of each path between the 2 nodes.
function display_cost_each_path_between_2_nodes(start, end) {
start_index = myVertices.indexOf(start);
end_index = myVertices.indexOf(end);
var shortestPathA = graph.BFS(myVertices[start_index]);
var fromVertex = myVertices[start_index];
for (var i = 1; i<myVertices.length; i++){
var toVertex = myVertices[i],
path = new Stack();
for (var v=toVertex; v !== fromVertex; v=shortestPathA.predecessors[v]) {
path.push(v);
}
path.push(fromVertex);
var s = path.pop();
while (!path.isEmpty()){
s += ' ' + path.pop();
}
avalible_paths.push(s);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.