COP3530 Assignment 14 - Graphs

by Jeff Santos

HTML

<input type="button" value="Create Graph" onClick="createGraph();"/>
<br/><br/>
Select two nodes:
<br/><br/>
From
<select id="from"></select>
To
<select id="to"></select>
<input type="button" value="Calculate" onClick="calc();"/>
<br/><br/>
<div id="output"/>

JavaScript

function Node(value)
{
	this.content = value;
	this.edges = [];
	
	this.addEdge = function(otherNode, cost)
	{
		this.edges.push({"node": otherNode, "cost": cost});
	}
	
	this.toString = function()
	{
		return this.content;
	}
	
	this.printEdges = function()
	{
		var str = "Node: " + this.content + "\n";
		for(i = 0; i < this.edges.length; i++)
		{
			str += " |-- to: " + this.edges[i].node + ", cost: " + this.edges[i].cost + "\n";
		}
		return str;
	}
}

function Graph()
{
	this.nodes = {};
	
	this.add = function(value)
	{
		var newNode = new Node(value);
		this.nodes[value] = newNode;
		return newNode;
	}
	
	this.connect = function(val1, val2, cost)
	{
		var node1 = this.nodes[val1];
		var node2 = this.nodes[val2];
		node1.addEdge(node2, cost);
		node2.addEdge(node1, cost);
	}
	
	this.printNodes = function()
	{
		var str = "";
		for(var key in this.nodes)
		{
			str += "Node: " + this.nodes[key] + "\n";
		}
		return str;
	}
	
	this.printEdges = function()
	{
		var str = "";
		for(var key in this.nodes)
		{
			str += this.nodes[key].printEdges() + "\n";
		}
		return str;
	}
	
	this.BFS = function(fromVal, toVal)
	{
		var paths = [];
		var queue = [];
		
		var root = this.nodes[fromVal];
		
		var tempChecked = {};
		tempChecked[root.content] = true;
		queue.push({"node": root, "parent": null, "cost": 0, "checked": tempChecked});
		
		while(queue.length > 0)
		{
			current = queue.dequeue();
			if(current.node.content == toVal)
			{
				paths.push(current);
			}
			else
			{
				for(i = 0; i < current.node.edges.length; i++)
				{
					var edge = current.node.edges[i];
					var checkSet = clone(current.checked);
					if(checkSet[edge.node.content] != true)
					{
						checkSet[edge.node.content] = true;
						queue.push({
							"node": edge.node,
							"parent": current,
							"cost": edge.cost,
							"checked": checkSet
						});
					}
				}
			}
		}
		
		return paths;
	}
}

function print(msg, erase =...