Untitled

<html>
<body>
<div id="output">

</div>
<script>
function NodeSet() {
	this.array = [];
}

NodeSet.prototype.clear = function() {
	this.array = [];
}

NodeSet.prototype.add = function(node) {
	this.array[node.id] = node;
}

NodeSet.prototype.includes = function(node) {
	return this.array[node.id] !== undefined;
}

NodeSet.prototype.size = function() {
	return this.array.length;
}

function Node(id) {
	this.id = id;
	this.children = [];
	this.parents  = [];
}

Node.prototype.toString = function() {
	return "[Node " + this.id + "]";
}

function nodeEq(nodeA, nodeB) {
	return nodeA.id === nodeB.id;
}

function connect(tail, head) {
	tail.children.push(head);
	head.parents.push(tail);
}

function BuildPath(sourceNode, meetingNode, backwardStack) {
	let path = BidirectionalIterativeDeepeningDepthFirstSearch(sourceNode,
															   meetingNode);
	path.splice(-1, 1);
	path.push(...backwardStack);
	return path;
}

function DepthLimitedSearchForward(node, depth, frontier) {
	if (depth === 0) {
		frontier.add(node);
		return;
	}

	node.children.forEach(function(child) {
		DepthLimitedSearchForward(child, depth -  1, frontier);
	});
}

function DepthLimitedSearchBackward(node, depth, backwardStack, frontier) {
	backwardStack.unshift(node);

	if (depth === 0) {
		if (frontier.includes(node)) {
			return node;
		}

		backwardStack.shift();
		return null;
	}

	for (var i = 0; i !== node.parents.length; i++) {
		let parent = node.parents[i];
		let meetingNode = DepthLimitedSearchBackward(parent, depth - 1, backwardStack, frontier);

		if (meetingNode !== null) {
			return meetingNode;
		}
	}

	backwardStack.shift();
	return null;
}

function BidirectionalIterativeDeepeningDepthFirstSearch(sourceNode,
														 targetNode) {
	if (sourceNode.id === targetNode.id) {
		return [sourceNode];
	}

	let frontier = new NodeSet();
	let backwardStack = [];
	let depth = 0;

	while (true) {
		DepthLimitedSearchForward(sourceNode, depth, frontier);

		for (var i = 0; i < 2; i++) {
			let meetingNode = DepthLimitedSearchBackward(targetNode,
							           					 depth + i,
												         backwardStack,
														 frontier);

			if (meetingNode !== null) {
				return BuildPath(sourceNode,
								 meetingNode,
								 backwardStack);
			}

			backwardStack = [];
		}

		frontier.clear();
		depth++;
	}
}

function DequeNode(elem) {
	this.next = undefined;
	this.elem = elem;
}

function Deque() {
	this.head = undefined;
	this.tail = undefined;
	this.size = 0;
}

Deque.prototype.shift = function() {
	let ret = this.head.elem;
	this.head = this.head.next;
	this.size--;
	return ret;
}

Deque.prototype.push = function(elem) {
	let newNode = new DequeNode(elem);

	if (this.head) {
		this.tail.next = newNode;
	} else {
		this.head = newNode;
	}

	this.size++;
	this.tail = newNode;
}

Deque.prototype.length = function() {
	return this.size;
}

Deque.prototype.front = function() {
	return this.head.elem;
}

let NULL = "NULL";

function tracebackPath(touchNode, parentsA, parentsB) {
	let path = [];
	let current = touchNode;

	while (current != NULL) {
		path.push(current);
		current = parentsA.get(current);
	}

	path.reverse();

	if (parentsB) {
		current = parentsB.get(touchNode);

		while (current != NULL) {
			path.push(current);
			current = parentsB.get(current);
		}
	}

	return path;
}

function NodeMap() {
	this.array = [];
	this.size = 0;
}

NodeMap.prototype.put = function(key, value) {
	if (this.array[key.id] === undefined) {
		this.array[key.id] = value;
		this.size++;
	}
}

NodeMap.prototype.get = function(key) {
	return this.array[key.id];
}

NodeMap.prototype.containsKey = function(key) {
	return this.array[key.id] !== undefined;
}

NodeMap.prototype.length = function() {
	return this.size;
}

function BidirectionalBreadthFirstSearch(s, t) {
	let queueA = new Deque();
	let queueB = new Deque();

	let parentsA = new NodeMap();
	let parentsB = new NodeMap();

	let distanceA = new NodeMap();
	let distanceB = new NodeMap();

	queueA.push(s);
	queueB.push(t);

	parentsA.put(s, NULL);
	parentsB.put(t, NULL);

	distanceA.put(s, 0);
	distanceB.put(t, 0);

	let bestCost = 1000 * 1000 * 1000;
	let touchNode = undefined;

	while (queueA.length() > 0 && queueB.length() > 0) {
		let distA = distanceA.get(queueA.front());
		let distB = distanceB.get(queueB.front());

		if (touchNode && bestCost < distA + distB) {
			return tracebackPath(touchNode,
								 parentsA,
								 parentsB);
		}

		if (distanceA.length() < distanceB.length()) {
			let current = queueA.shift();

			for (let i = 0; i < current.children.length; i++) {
				let child = current.children[i];

				if (!distanceA.containsKey(child)) {
					 distanceA.put(child, distanceA.get(current) + 1);
					 parentsA.put(child, current);
					 queueA.push(child);

					 if (distanceB.containsKey(child)
						&&
						bestCost > distanceA.get(child) + distanceB.get(child)) {
						bestCost = distanceA.get(child) + distanceB.get(child);
						touchNode = child;
					}
				}
			}
		} else {
			let current = queueB.shift();

			for (let i = 0; i < current.parents.length; i++) {
				let parent = current.parents[i];

				if (!distanceB.containsKey(parent)) {
					 distanceB.put(parent, distanceB.get(current) + 1);
					 parentsB.put(parent, current);
					 queueB.push(parent);

					if (distanceA.containsKey(parent)
						&&
						bestCost > distanceA.get(parent) + distanceB.get(parent)) {
						bestCost = distanceA.get(parent) + distanceB.get(parent);
						touchNode = parent;
					}
				}
			}
		}
	}

	return [];
}

function BreadthFirstSearch(source, target) {
	let queue = new Deque();
	let parents = new NodeMap();

	queue.push(source);
	parents.put(source, NULL);

	while (queue.length() > 0) {
		let current = queue.shift();

		if (current.id === target.id) {
			return tracebackPath(current, parents, undefined);
		}

		for (let i = 0; i < current.children.length; i++) {
			let child = current.children[i];

			if (!parents.containsKey(child)) {
				parents.put(child, current);
				queue.push(child);
			}
		}
	}

	return [];
}

function createGraph(nodes, arcs) {
	let graph = [];

	for (var id = 0; id < nodes; id++) {
    	graph.push(new Node(id));
    }

    for (var i = 0; i < arcs; i++) {
    	let tailIndex = Math.floor(Math.random() * nodes);
    	let headIndex = Math.floor(Math.random() * nodes);
    	connect(graph[tailIndex], graph[headIndex]);
    }

	return graph;
}

let outputDiv = document.getElementById("output");

const NODES = 1000000;
const ARCS  = 5000000;
const graph = createGraph(NODES, ARCS);

let sourceIndex = Math.floor(Math.random() * NODES);
let targetIndex = Math.floor(Math.random() * NODES);

let sourceNode = graph[sourceIndex];
let targetNode = graph[targetIndex];

console.log("Source node: " + sourceNode);
console.log("Target node: " + targetNode);
outputDiv.innerHTML += "Source node: " + sourceNode + "<br>" +
					   "Target node: " + targetNode + "<br>";

outputDiv.innerHTML += "<br>BIDDFS:";

var startTime = new Date().getMilliseconds();
var path = BidirectionalIterativeDeepeningDepthFirstSearch(sourceNode,
														   targetNode);
var endTime = new Date().getMilliseconds();
var num = 1;

for (var i = 0; i < path.length; i++) {
	let node = path[i];
	outputDiv.innerHTML += "<br>" + num + ": " + node;
	console.log(num++ + ": " + node);
}

let duration = endTime - startTime;
console.log("Duration: " + duration + " ms.");
outputDiv.innerHTML += "<br>Duration: " + duration + " ms.";
outputDiv.innerHTML += "<br><br>Bidirectional BFS:";

startTime = new Date().getMilliseconds();
var path2 = BidirectionalBreadthFirstSearch(sourceNode,
											targetNode);
endTime = new Date().getMilliseconds();
duration = endTime - startTime;
num = 1;

for (var i = 0; i < path2.length; i++) {
	let node = path2[i];
	outputDiv.innerHTML += "<br>" + num + ": " + node;
	console.log(num++ + ": " + node);
}

console.log("Duration: " + (endTime - startTime) + " ms.");
outputDiv.innerHTML += "<br>Duration: " + duration + " ms.";
outputDiv.innerHTML += "<br><br>BFS:";

startTime = new Date().getMilliseconds();
var path3 = BreadthFirstSearch(sourceNode,
							   targetNode);
endTime = new Date().getMilliseconds();
duration = endTime - startTime;
num = 1;

for (var i = 0; i < path3.length; i++) {
	let node = path3[i];
	outputDiv.innerHTML += "<br>" + num + ": " + node;
	console.log(num++ + ": " + node);
}

console.log("Duration: " + duration + " ms.");
outputDiv.innerHTML += "<br>Duration: " + duration + " ms.";
</script>
</body>
</html>