OU-EEI exp-b3-d3

distance.txt

0 1 1 3
0 3 1 3
1 2 1 3
1 3 1 4
2 4 1 4
2 5 1 3
3 4 1 5
3 7 1 3
4 5 1 5
4 7 1 4
5 6 1 3
5 8 1 4
6 8 1 3
7 8 1 4
7 9 1 3
8 9 1 3

main.js

(function(){
  var network = new (require("./NetworkObj.js").NetworkObj())(),
	keepDuration = parseInt(process.argv[2], 10), mode = parseInt(process.argv[3], 10),
	isOnDemand = true, preferWidest = false,
	route = {}, x = 0, i = 0, j = 0, count = 0;

	if(isNaN(keepDuration)){
		keepDuration = 10;
	}

	if(!isNaN(mode)){
		if(mode % 2 === 0){
			isOnDemand = false;
		}
		if(mode >= 2){
			preferWidest = true;
		}
	}

	switch(keepDuration){
		case 0:
			x = 1000;

			for(count = 0, i = 0; i < x; i += 1){
				network.spaces = network.getInitSpaces();

				for(j = 0; true;){
					route = network.getRouteByDijkstra(Math.floor(Math.random() * 10), Math.floor(Math.random() * 10), isOnDemand, preferWidest);

					if(isNaN(route.dist)){
						break;
					}

					j += 1;
				}

				count += j;
			}

			break;
		default:
			x = 10000;

			for(i = 0; i < keepDuration; i += 1){
				network.connections.push([]);
			}

			for(count = 0, i = 0; i < x; i += 1){
				route = network.getRouteByDijkstra(Math.floor(Math.random() * 10), Math.floor(Math.random() * 10), isOnDemand, preferWidest);

				if(isNaN(route.dist)){
					count += 1;
				}

				network.connections.push(route.route);

				network.linkDown(network.connections.shift());
			}
	}

	process.stdout.write((count / x).toString());

	return;
})();

NetworkObj.js

exports.NetworkObj = function(){
	var NetworkObj = function(){
		this.connections = [];
		this.spaces = this.getInitSpaces();
	};
	NetworkObj.prototype = (function(){
		var edges = [];

		require("fs").readFileSync("distance.txt").toString().replace(/\r/, "").split("\n").forEach(function(row){
			var values = row.split(" "),
			node1 = parseInt(values[0], 10), node2 = parseInt(values[1], 10), dist = parseInt(values[2], 10), width = parseInt(values[3], 10);

			if(isNaN(node1) || isNaN(node2)){
				return;
			}

			edges.push({
				from : (node1 < node2 ? node1 : node2),
				to : (node2 > node1 ? node2 : node1),
				dist : dist,
				width : width
			});
		});

		edges.sort(function(a, b){
			return a.width > b.width ? -1 : (a.width < b.width ? 1 : 0);
		});

		return {
			dumpEdges : function(){
				return console.log(edges);
			},
			genNodeInfo : function(){
				var nodes = [];

				edges.forEach(function(edge){
					nodes[edge.from] = {dist : NaN, before : {node : null, edge : NaN}, done : false};
					nodes[edge.to] = {dist : NaN, before : {node : null, edge : NaN}, done : false};
				});

				return nodes;
			},
			getInitSpaces : function(){
				var ret = [];

				edges.forEach(function(edge, key){
					ret[key] = edge.width;
				});

				return ret;
			},
			getNeighbours : function(origin){
				var ret = [];

				edges.forEach(function(edge, key){
					if(edge.from === origin){
						ret.push({node : edge.to, edge : key});
					}else if(edge.to === origin){
						ret.push({node : edge.from, edge : key});
					}
				});

				return ret;
			},
			getDistance : function(edge){
				return edges[edge].dist;
			},
			getWidth : function(edge){
				return edges[edge].width;
			},
			getMaxWidth : function(thr){
				var ret = 0;

				edges.forEach(function(edge){
					ret = (edge.width > ret && (thr === undefined || edge.width < thr)) ? edge.width : ret;
				});

				return ret;
			}
		};
	})();
	NetworkObj.prototype.getMaxSpace = function(thr){
		var ret = 0;

		this.spaces.forEach(function(space){
			ret = (space > ret && (thr === undefined || space < thr)) ? space : ret;
		});

		return ret;
	};
	NetworkObj.prototype.reserveEdge = function(edge){
		this.spaces[edge] -= 1;
		return;
	};
	NetworkObj.prototype.releaseEdge = function(edge){
		this.spaces[edge] += 1;
		return;
	};
	NetworkObj.prototype.linkUp = function(route){
		var network = this;

		route.forEach(function(node){
			if(isNaN(node.before.edge)){
				return;
			}

			network.reserveEdge(node.before.edge);
		});
	};
	NetworkObj.prototype.linkDown = function(route){
		var network = this;

		route.forEach(function(node){
			if(isNaN(node.before.edge)){
				return;
			}

			network.releaseEdge(node.before.edge);
		});
	};
	NetworkObj.prototype.getRouteByDijkstra = function(from, to, isOnDemand, preferWidest){
		var network = this,
		nodes = network.genNodeInfo(),

		ret = {
			dist : NaN,
			route : [
				{node : from, dist : NaN, before : {node : null, edge : NaN}},
				{node : to, dist : NaN, before : {node : null, edge : NaN}}
			]
		},

		route = [], curTry = 0, curNode = null, nextNode = null,

		updateNeighbour = function(neighbour){
			var tmpDist = 0;

			// Skip done nodes
			if(nodes[neighbour.node].done === true){
				return;
			}

			// Skip if the edge is full for on-demand mode
			if(isOnDemand && network.spaces[neighbour.edge] < 1){
				return;
			}

			// Skip if width (space for on-demand mode) is smaller than the current try
			if(preferWidest && (isOnDemand ? network.spaces[neighbour.edge] : network.getWidth(neighbour.edge)) < curTry){
				return;
			}

			// Update distance
			tmpDist = nodes[curNode].dist + network.getDistance(neighbour.edge);
			if(isNaN(nodes[neighbour.node].dist) || nodes[neighbour.node].dist > tmpDist){
				nodes[neighbour.node].dist = tmpDist;
				nodes[neighbour.node].before.node = curNode;
				nodes[neighbour.node].before.edge = neighbour.edge;
			}
		},
		detNextNode = function(node, key){
			if(!isNaN(node.dist) && node.done === false && (nextNode === null || node.dist < nodes[nextNode].dist)){
				nextNode = key;
			}
		},
		nextTry = function(curTry){
			return isOnDemand ? network.getMaxSpace(curTry) : network.getMaxWidth(curTry);
		};

		// bootstrap
		nodes[from].dist = 0;
		curNode = from;
		curTry = nextTry();

		while(true){
			nodes[curNode].done = true;

			network.getNeighbours(curNode).forEach(updateNeighbour);

			nextNode = null;
			nodes.forEach(detNextNode);

			// Check whether further processes are needed
			if(nextNode === null || nextNode === to){
				if(nextNode === null && preferWidest && (curTry = nextTry(curTry)) !== 0){
					nodes = network.genNodeInfo();
					nodes[from].dist = 0;
					nextNode = from;
				}else{
					break;
				}
			}

			// Make the nearest neighbour the next current node
			curNode = nextNode;
		}

		// Trace route
		curNode = to;
		while(curNode !== from){
			if(isNaN(nodes[curNode].dist) || network.spaces[nodes[curNode].before.edge] < 1){
				return ret;
			}

			route.unshift({node : curNode, dist : nodes[curNode].dist, before : nodes[curNode].before});

			curNode = nodes[curNode].before.node;
		}
		route.unshift({node : curNode, dist : nodes[curNode].dist, before : nodes[curNode].before});

		network.linkUp(route);

		ret.dist = nodes[to].dist;
		ret.route = route;
		return ret;
	};

	return NetworkObj;
};