University of South Florida JavaScript Graph Creation Project Hi, I need JavaScript and corresponding HTML code to do the following: Given the Graph shown

University of South Florida JavaScript Graph Creation Project Hi, I need JavaScript and corresponding HTML code to do the following:

Given the Graph shown (ignore pointers this is an undirected graph in that you can traverse from node to node in any direction)

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

In your code, 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.

Construct a graph that represents the assignment
Traverse the graph
Find the optimal path

Additional Info:

var Node = function(_name) {
this.name = _name;
this.edges = [];
return this;
}

In the sample implementation Edges also keep track of their nodes and their cost

var Edge = function(_cost) {
this.from = null;
this.to = null;
this.cost = null;
return this;
}

Note that this information is redundant, the Graph can contain a collection of Edges or a collection of Nodes – both will work.

A very commonly used representation of a Graph (basically because the code for this is readily available with a Google Search is this representation;

function graph() {
this.edges = {};
this.paths = [];
}
graph.prototype.add_node = function (label) {
this.edges[label] = {};
};

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

In this representation the property edges is defined as an object in the constructor of the graph; this.edges = {}.

In the add_node the index of the edges property is set defined as an object in the add_node function; this.edges[label] = {}.

Finally when adding an edge the code sets up a 2D array that allows accessing the cost value through the from and to variables (which must correspond to the string labels of the nodes); this.edges[from][to] = cost.

A recursive function is then employed to create all the paths through the graph. The exit clause of the recursive function is when the graph loops back on itself; if (from == to) display_path(paths, cost). paths is simply an array of all the paths calculated.

Finally the simplest representation of a Graph is simply as a collection of Nodes. You still need edges, but they are not object members of the Graph.

var Graph = function() {
this.nodes = [];
}

var Node = function(Name) {
this.name = Name;
this.edges = [];
return this;
}

var Edge = function(From, To, Cost) {
this.from = From;
this.to = To;
this.cost = Cost;
return this;
}

Additional Information

You will work with graphs a lot in your career, they are everywhere and as an IT professional you are expected to know what they are and how they can be represented. So here is your chance to learn.

There are multiple ways to represent a Graph – you should at least know some of them. The discussion at Khan Academy is excellent for this – https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Another representation is an adjacency matrix, though I personally believe an adjacency list is a simpler and easier to understand representation of a graph – discussion of both of these are here – http://www.geeksforgeeks.org/graph-and-its-representations/ . The examples are implemented in C, though the translation to javascript is not terrible (if you need help with any of the steps – use the discussion board).

Once you have selected a representation of the Graph – the next step is the implementation of a traversal algorithm.