<script>
function Min_Heap(data){
	this.data = [];
}
//min_heapify(i): creates a min_heap in data rooted at i
//pre: i is an index in data and there are two heaps (left, right)
//post: heap routed at i
Min_Heap.prototype.min_heapify = function(i){
	//---PRECONDITION CHECK---
	//assert(i<this.data.length);
	//---END PRECONDITION CHECK---
    var left = (2*(i+1))-1;		//left child of i
    var right = 2*(i+1);		//right child of i
    var smallest = i;
    if (left < this.heapsize && this.data[left].key < this.data[i].key){
        smallest = left;
    }
    if (right < this.heapsize && this.data[right].key < this.data[smallest].key){
        smallest = right;
    }
    if (smallest != i){
        var temp = this.data[smallest];
        this.data[smallest] = this.data[i];
        this.data[i] = temp;
        this.min_heapify(smallest);
    }
    //---POSTCONDITION CHECK---
	//assert(this.data[i]);
	//---END POSTCONDITION CHECK---
}
//invarient: data[i+1]...data[n-1] are roots of min heaps (n = data.length)
//pre: data is an array of size n
//post: data[1]...data[n-1] are roots of min heaps
Min_Heap.prototype.build_min_heap = function(){
	//---PRECONDITION CHECK---
	//assert(this.data.length);
	//---END PRECONDITION CHECK---
    this.heapsize = this.data.length;
	var i = Math.floor(this.heapsize/2)-1;
	//---INVARIENT INITILIZATION CHECK---
	//assert(is_min_heap(this.data, i+1, this.data.length/2-1));
	//---END INVARIENT INITILIZATION CHECK---
	for (i; i>=0; i--){
        this.min_heapify(i);
		//---INVARIENT MAINTENENCE CHECK---
		//assert(is_min_heap(this.data, i+1, this.data.length/2-1));
		//---END INVARIENT MAINTENENCE CHECK---
    }
	//---INVARIENT TERMINATION CHECK---
	//assert(is_min_heap(this.data, (i+1), (this.data.length/2-1)));
	//---END INVARIENT TERMINATION CHECK---
	//---POSTCONDITION CHECK---
	//assert(is_min_heap(this.data,0, this.data.length/2-1));
	//---END POSTCONDITION CHECK---
}
//insert an item to the min heap
Min_Heap.prototype.push = function(item, key){
	var obj = {item: item, key: key};
	this.data.push(obj);
	this.build_min_heap();
}
//removes the smallest key from the min heap and rebuilds the heap
Min_Heap.prototype.extract_min = function(){
	var min = this.data.shift();
	this.heapsize--;
	this.min_heapify(0);
	//Post condition: returns the smallest value from Min_heap
	//pc check:
	/*for (var i = 0; i<this.data.length; i++){
		assert(min.key <= this.data[i].key);
	}*/
	return min;
}
//checks if the heap is empty
Min_Heap.prototype.empty = function(){
	return (this.heapsize == 0)
}
 
//checks that A is a max heap routed at i
function is_max_heap(A, i, n){
	if (i >= n){
		return true;
	}
	if (A[i].key <= A[2*(i+1)-1].key && A[i].key <= A[2*(i+1)].key && is_min_heap(A, 2*(i+1)-1, n) && is_min_heap(A, 2*(i+1), n)){
		return true;
	}
	else{
		return false;
	}
}
 
 
function Graph(type, num_nodes, directed){
	this.size = num_nodes;
	this.directed = directed;
	if (type == "matrix"){
		this.type = "matrix";
		this.matrix = new Array(num_nodes);
		//set up an empty n by n 2D array to be used as the matrix (n being number of nodes)
		for (var i = 0; i < num_nodes; i++){
			var temp_array = new Array(num_nodes);
			for (var j = 0; j <num_nodes; j++){
				temp_array[j] = null;
			}
			this.matrix[i] = temp_array;
		}
	}
	else{
		this.type = "list";
		//create an empty list of length num_nodes
		this.list = new Array(num_nodes);
		for (var i = 0; i < num_nodes; i++){
			this.list[i] = [];
		}
	}
}
//returns all nodes in graph
Graph.prototype.nodes = function(){
	var all_nodes = new Array();
	//add each node to the array all_nodes
	for (var i = 0; i < this.size; i++){
		all_nodes.push(i);
	}
	return all_nodes;
}
//return all edges in a graph
Graph.prototype.edges = function(){
	var all_edges = new Array();
	if (this.type=="matrix"){
		//iterate through the matrix
		for (var i = 0; i <this.size; i++){
			for (var j = 0; j<this.size; j++){
				if (!(this.matrix[i][j]===null)){
					//if an edge is found add it into the all_edges array
					all_edges.push({source: i, destination: j, weight: this.matrix[i][j]});
				}
			}
		}
	}
	else{
		//iterate through the list
		for (var i = 0; i <this.size; i++){
			for (var j = 0; j < this.list[i].length; j++){
				//for each edge add it into the all_edges array
				all_edges.push({source: i, destination: this.list[i][j].node, weight: this.list[i][j].weight});
			}
		}
	}
	return all_edges;
}
//return nodes adjacent to node
Graph.prototype.adjacent = function(node){
	var adjacent_nodes = new Array();
	if (this.type=="matrix"){
		//iterate through node's column in the matrix
		for (var i = 0; i < this.size; i++){
			if (!(this.matrix[node][i]===null)){
				//if an edge is found add the adjacent node to the adjacent_nodes array
				adjacent_nodes.push(i);
			}
		}
	}else{
		//iterate through the adjacency list entry for node
		for (var i = 0; i < this.list[node].length; i++){
			//add each adjacent node to the adjacent_nodes array
			adjacent_nodes.push(this.list[node][i].node);
		}
	}
	return adjacent_nodes;
}
//return the edge weight of the edge from node1 to node2
//(returns 'undefined' if an edge doesnt exist between the two nodes
Graph.prototype.weight = function(node1, node2){
	if (this.type=="matrix"){
		return this.matrix[node1][node2];
	}
	else{
		for (var i = 0; i < this.list[node1].length; i++){
			if (this.list[node1][i].node == node2){
				//if node2 is found as an adjacent node return its weight
				return this.list[node1][i].weight
			}
		}
	}
}
//inserts an edge into the graph
Graph.prototype.insert_edge = function(node1, node2, weight){
	if (this.type=="matrix"){
		if (this.matrix[node1][node2] === null){
			this.matrix[node1][node2] = weight;
			//make sur ethe edge doesnt already exist
			if (this.directed != true){
				//if graph is undirected insert the edge for the inverse
				this.matrix[node2][node1] = weight;
			}
			return true;
		}else{
			return false;
		}
	}
	else{
		for (var i = 0; i < this.list[node1].length; i++){
			//make sure the edge doesnt already exist
			if (this.list[node1][i].node == node2){
				return false;
			}
		}
		this.list[node1].push({node: node2, weight: weight});
		if (this.directed != true){
			//if graph is undirected insert the edge for the inverse
			this.list[node2].push({node: node1, weight: weight});
		}
		return true;
	}
}
 
//Pre: no negative edge weights in connected graph G.
//Post: every node is labeled by its shortest distance (dist[node]) back to the source and predeccessors[node] contains the previous node in the shortest path
function dijkstras(G,s){
	//precondition check
	var edges = G.edges();
	for (var e in edges){
		if (edges[e].weight<0){
			alert("negative edge weight found");
			return;
		}
	}
	//end precondition check
 
	var predecessors = new Array();
	var dist = new Array();
	dist[s] = 0;
	//var inPath = new Array();
	var queue = new Min_Heap();
	queue.push(s,0);
	while (!queue.empty()){
		var u = queue.extract_min().item;
		//inPath.push(u);
		for (var v in G.adjacent(u)){
			if (dist[v]>dist[u]+G.weight(u,v) || typeof dist[v] === 'undefined'/*undefined is treated as infinity*/){
				//u is the closest node to s(because it has the smallest key. (from extract_min)
				//the closest adjacent node is selected.  -> greedy choice is made
				dist[v] = dist[u] + G.weight(u,v);
				predecessors[v] = u;
				queue.push(v, dist[v]+G.weight(u,v));
			}
		}
	}
	return predecessors;
}
 
//Pre: graph G (can have negative edge weights).
//Post: every node is labeled by its shortest distance (dist[node]) back to the source and predeccessors[node] contains the previous node in the shortest path
function bellmanFord(G, s){
	var dist = new Array();
	var u, v;
	var predecessors = new Array();
	for (var v in G.nodes()){
		if (v == s){
			dist[v] = 0;
		}
		else{
			dist[v] = null;
		}
		predecessors[v] = null;
	}
	for (var i = 1; i<G.nodes().length; i++){
		var edge = G.edges();
		for (var e in edge){
			u = edge[e].source;
			v = edge[e].destination;
			if (dist[u] + edge[e].weight < dist[v] || dist[v] === null){
				dist[v] = dist[u] + edge[e].weight
				predecessors[v] = u;
			}
		}
	}
	for (var e in G.edges()){
		u = e.source;
		v = e.destination;
		if (dist[u] + e.weight < dist[v]){
			alert("Negative edge weight cycle found");
		}
	}
	return predecessors;
}
 
//function used to extract the shortest path to a given destination from the predecessor array
function getShortestPath(predecessors, destination){
	var d = destination;
	var nodes = [];
	var u = d;
	var predecessor;
	while (u){
		nodes.push(u);
		predecessor = predecessors[u];
		u = predecessors[u];
	}
	nodes.reverse();
	return nodes;
}
//generates a random graph by inserting a number of random edges equal to num_v squared times density
function generate_graph_vers1(num_v, density, directed, min_weight, max_weight){
	var G = new Graph("matrix", num_v, directed);
	var G2 = new Graph("list", num_v, directed);
	if (directed==true){
		var num_edges = Math.floor(density*((num_v*num_v)));
	}
	else{
		var num_edges = Math.floor(density*((num_v*num_v)/2));
	}
	var i = 0;
	while(i < num_edges){
		var ind1 = Math.floor(Math.random()*(num_v));
		var ind2 = Math.floor(Math.random()*(num_v));
		var weight = Math.floor(Math.random()*(max_weight-min_weight))+min_weight;
		if (G.insert_edge(ind1, ind2, weight)){
			G2.insert_edge(ind2, ind2, weight);
			i++;
		}
	}
	return {matrix: G, list: G2};
}
//generates a random graph by inserting random edges with a probability of density between each set of vertices
function generate_graph_vers2(num_v, density, directed, min_weight, max_weight){
	var G = new Graph("matrix", num_v, directed);
	var G2 = new Graph("list", num_v, directed);
	var i = 0;
	for (var i = 0; i < num_v; i++){
		for (var j = 0; j < num_v; j++){
			if (Math.random() <= density){	
				var weight = Math.floor(Math.random()*(max_weight-min_weight))+min_weight;
				G.insert_edge(i, j, weight);
				G2.insert_edge(i, j, weight);
			}
		}
	}
	return {matrix: G, list: G2};
}
 
function test_SSSP(G, alg, type){
	var d = new Date();
	d = d.getTime();
	if (type=="matrix"){
		var g = G.matrix;
	}else{
		var g = G.list;
	}
	if (alg[0]=="d"){
		dijkstras(g,0);
	}else{
		bellmanFord(g,0);
	}
	var d2 = new Date();
	d2 = d2.getTime();
	var runtime = d2-d;
	console.log(runtime);
}
 
var G = generate_graph_vers1(10,.5, false, 1,10);
console.log(G);
var p = dijkstras(G.matrix, 2);
var p2 = dijkstras(G.list, 2);
var p3 = bellmanFord(G.matrix, 2);
var p4 = bellmanFord(G.list, 2);
 
 
</script>