Assignment 14 – Graphs
Objective
Demonstrate the ability to implement and traverse a graph
Supports learning objectives 1, 2 and 3
1. Describe both complex and simple data structures.
2. Select the correct data structure and algorithm to solve specific problems.
3. Implement data structures and algorithms in computer code.
Introduction
Graphs are possibly the most complex of the basic data structures you will deal with. They are covered in Topic – Graph Data Structures . There are a lot of ways to represent a Graph (by nodes, by edges, by nodes and edges). You may wish to research different methods to represent Graphs as some are much easier to use than others.
Assignment
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.
Example:
a to e
a, f, e: 23
a, c, f, e: 20
a, c, d, e: 26
a, c, b, d, e: 40
a, b, c, d , e: 34
a, b, d, e: 28
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.
Submission Instructions
You will submit a link to your code in JSFiddle. You can submit this as text file.
Grading Criteria
Partial Credit is available on this assignment based on your ability to
- Construct a graph that represents the assignment
- Traverse the graph
- Find the optimal path
Information
A JSFiddle with a sample implementation of a Graph is at http://jsfiddle.net/reaglin/wykhhuwo/ this sample graph defines nodes as having a collection of edges, which is one representation of a Graph.
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;
}
The Graph can then be created with the code
var Graph = function() {
// This is a specific implementation of a graph
// that uses nodes, edges, and paths.
this.nodes = []; // An array of node
this.edges = []; // An array of edges
this.paths = []; // We need to keep track of paths.
this.addNode = function(_name) {
var node = new Node(_name);
this.nodes.push(node);
return node;
};
this.addEdge = function(_from, _to, _cost) {
var edge = new Edge(_cost);
edge.from = _from;
edge.to = _to;
edge.cost = _cost;
this.edges.push(edge);
_from.edges.push(edge);
};
this.printNodes = function() {
var s = "All Nodes in Graph <br/>";
for (var i = 0; i < this.nodes.length; i++) {
s = s + "Node: " + i + " Name: " + this.nodes[i].name + "</br>";
}
return s;
}
this.printEdges = function() {
var s = "All Edges in Graph <br/>";
for (var i = 0; i < this.edges.length; i++) {
s += "Edge: " + i + " From: " + this.edges[i].from.name + " To: " + this.edges[i].to.name + " Cost: " + this.edges[i].cost + "</br>";
}
return s;
}
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. I will be happy to answer any questions on the discussion board of potential traversal algorithms. This is where working through the questions in the Geeks Quiz can help you understand these algorithms – there are excellent discussions there – and once again, I will be happy to help you along the way.
Bottom line – the best way to learn about graphs is to research and create one. Ask questions if you get stuck and share resources that will help others to understand the concept and the implementation.