2
\$\begingroup\$

(See the previous iteration.)

Now I have reworked my pathfinder program, and I ended up with this:

<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>

Example output

Source node: [Node 437100]
Target node: [Node 368960]

BIDDFS:
1: [Node 437100]
2: [Node 815624]
3: [Node 858313]
4: [Node 506296]
5: [Node 956880]
6: [Node 172071]
7: [Node 406177]
8: [Node 443935]
9: [Node 250512]
10: [Node 368960]
Duration: 5 ms.

Bidirectional BFS:
1: [Node 437100]
2: [Node 815624]
3: [Node 858313]
4: [Node 506296]
5: [Node 956880]
6: [Node 172071]
7: [Node 406177]
8: [Node 443935]
9: [Node 250512]
10: [Node 368960]
Duration: 20 ms.

BFS:
1: [Node 437100]
2: [Node 815624]
3: [Node 966613]
4: [Node 62273]
5: [Node 951283]
6: [Node 238369]
7: [Node 436275]
8: [Node 327303]
9: [Node 818069]
10: [Node 368960]
Duration: 652 ms.

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$
  • \$\begingroup\$ Is function BidirectionalIterativeDeepeningDepthFirstSearch declared correctly, it seems odd to me? \$\endgroup\$ – dfhwze Sep 7 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.