added support for edge references

make-github-pseudonymous-again · make-github-pseudonymous-again · commit 97b96ae67c0d · 2014-05-24T13:35:12.000+02:00
diff --git a/js/src/001 undirected/offline/algo/eulerian/blossom.js b/js/src/001 undirected/offline/algo/eulerian/blossom.js
diff --git a/js/src/001 undirected/offline/algo/eulerian/eventour.js b/js/src/001 undirected/offline/algo/eulerian/eventour.js
@@ -32,10 +32,10 @@ var eventour_t = function(){
 
 			while(true){
 				var end = true;
-				it[i] = g.eitr(u, function(e){
-					if(free[i][e[0][0]] > 0){
+				it[i] = g.eitr(u, function(_, v){
+					if(free[i][v[0]] > 0){
 						tour.splice(j, 0, i);
-						u = e[0];
+						u = v;
 
 						++j;
 						if (!done[u[0]]) r.push([u[0], j]);
diff --git a/js/src/001 undirected/offline/algo/eulerian/oddgraph.js b/js/src/001 undirected/offline/algo/eulerian/oddgraph.js
@@ -8,8 +8,8 @@ var oddgraph_t = function(){
 
 		g.vitr(function(v){
 			var i = 0;
-			g.eitr(v, function(e){
-				i += (e[0] !== v);
+			g.eitr(v, function(_, u){
+				i += (u !== v);
 			});
 
 			if(i % 2 === 1){
diff --git a/js/src/001 undirected/offline/algo/eulerian/simplegraph.js b/js/src/001 undirected/offline/algo/eulerian/simplegraph.js
@@ -12,25 +12,23 @@ var simplegraph_t = function(){
 			i = v[0]; // indice of v in dist
 			V[i] = h.vadd(v);
 				
-			g.eitr(v, function(e){
+			g.eitr(v, function(_, u, w){
 
-				var u = e[0]; // dest
-				var w = e[1]; // weigth
 				j = u[0];
 
 				if(i >= j) return;
 
-				if (w < dist[i][j][1] ){
-					dist[i][j] = e;
+				if (w < dist[i][j] ){
+					dist[i][j] = w;
 				}
 			});
 		});
 				
 
 		for (i = 0; i < order; ++i){
 			for (j = i + 1; j < order; ++j){
-				if ( dist[i][j][1] < Infinity ){
-					h.eadd( V[i], V[j], dist[i][j][1] );
+				if ( dist[i][j] < Infinity ){
+					h.eadd( V[i], V[j], dist[i][j] );
 				}
 			}
 		}
diff --git a/js/src/001 undirected/offline/algo/sp/dijkstra.js b/js/src/001 undirected/offline/algo/sp/dijkstra.js
@@ -11,23 +11,23 @@ var dijkstra_t = function(priority_queue_t){
 		used[s[0]] = true;
 		busy[s[0]] = true;
 
-		g.eitr(s, function(e){
-			dist[e[0][0]] = e[1];
-			busy[e[0][0]] = true;
-			left.push(e[0]);
+		g.eitr(s, function(_, u, w){
+			dist[u[0]] = w;
+			busy[u[0]] = true;
+			left.push(u);
 		});
 
 		while(left.length){
 
 			var m = left.pop();
 			used[m[0]] = true;
 				
-			g.eitr(m, function(e){
-				var y = e[0];
+			g.eitr(m, function(_, u, w){
+				var y = u;
 				
 				if(!used[y[0]]){
 
-					var v = dist[m[0]] + e[1];
+					var v = dist[m[0]] + w;
 
 					if(v < dist[y[0]]){
 						dist[y[0]] = v;
diff --git a/js/src/001 undirected/offline/algo/sp/sptreedfs.js b/js/src/001 undirected/offline/algo/sp/sptreedfs.js
@@ -4,10 +4,9 @@ var sptreedfs_t = function(){
 
 	var dfs = function(g, next, dist, s, t){
 
-		g.eitr([s], function(e){
-			var u = e[0][0];
-			var w = e[1];
-
+		g.eitr([s], function(_, u, w){
+			u = u[0];
+			
 			if(dist[u][t] === w + dist[s][t] && next[u][t] === -1){
 				next[u][t] = s;
 				dfs(g, next, dist, u, t);
diff --git a/js/src/001 undirected/offline/algo/util/amat.js b/js/src/001 undirected/offline/algo/util/amat.js
@@ -5,8 +5,8 @@ var amat_t = function(){
 	var amat = function(g, order, dist){
 
 		g.vitr(function(v){
-			g.eitr(v, function(e){
-				dist[v[0]][e[0][0]] = e[1];
+			g.eitr(v, function(_, u, w){
+				dist[v[0]][u[0]] = w;
 			});
 		});
 		
diff --git a/js/src/001 undirected/offline/algo/util/d2s.js b/js/src/001 undirected/offline/algo/util/d2s.js
@@ -7,8 +7,7 @@ var d2s = function(g, h, V){
 	});
 
 	g.vitr(function(u){
-		g.eitr(u, function(e){
-			var v = e[0], w = e[1];
+		g.eitr(u, function(_, v, w){
 			if(u[0] <= v[0]) h.eadd(V[u[0]], V[v[0]], w);
 		});
 	});
diff --git a/js/src/001 undirected/online/data/dense.js b/js/src/001 undirected/online/data/dense.js
@@ -16,12 +16,14 @@ var dense_graph_t = function(){
 		this.ad.push(ref);
 
 		var j = len;
-		while(j--) this.pt[j].push([null, -1]);
+		while(j--) this.pt[j].push([null, null, -1]);
 
 		this.pt.push(new Array(len + 1));
 
-		j = len + 1;
-		while(j--) this.pt[len][j] = [null, -1];
+		j = len;
+		while(j--) this.pt[len][j] = this.pt[j][len];
+
+		this.pt[len][len] = [null, null, -1];
 
 		return ref;
 	};
@@ -44,21 +46,21 @@ var dense_graph_t = function(){
 	graph.prototype.eadd = function(u, v, w){
 		var i = u[0], j = v[0];
 
-		this.pt[i][j][0] = v;
-		this.pt[i][j][1] = w;
-		this.pt[j][i][0] = u;
-		this.pt[j][i][1] = w;
-
-		return [this.pt[i][j], this.pt[j][i]];
+		this.pt[i][j][0] = u;
+		this.pt[i][j][1] = v;
+		this.pt[i][j][2] = w;
+		
+		return this.pt[i][j];
 
 	};
 
 	graph.prototype.edel = function(e){
 
-		var i = e[0][0][0], j = e[1][0][0];
+		var i = e[0][0], j = e[1][0];
 
 		this.pt[i][j][0] = null;
-		this.pt[j][i][0] = null;
+		this.pt[i][j][1] = null;
+		this.pt[i][j][2] = -1;
 
 	};
 
@@ -79,7 +81,7 @@ var dense_graph_t = function(){
 
 			if(this.pt[i][j][0] === null) continue;
 
-			if(fn.call(this, this.pt[i][j])) break;
+			if(fn.call(this, this.pt[i][j], this.ad[j], this.pt[i][j][2])) break;
 
 		}
 
diff --git a/js/src/001 undirected/online/data/sparse.js b/js/src/001 undirected/online/data/sparse.js
@@ -51,6 +51,10 @@ var sparse_graph_t = function(){
 		this.end = [null, this.beg, null];
 		this.beg[2] = this.end;
 
+		this.ebeg = [null, null, -1, null, null];
+		this.eend = [null, null, -1, this.ebeg, null];
+		this.ebeg[4] = this.eend;
+
 	};
 
 	/**
@@ -69,7 +73,7 @@ var sparse_graph_t = function(){
 		//   > [end][1][1] is the previous [end][1]
 		//   > [end] and [end][1] are sane
 		//   > [end][1][1][2] is still pointing to [end]
-		this.end[1] = [h, this.end[1], this.end, [-1, -1, null, null]];
+		this.end[1] = [h, this.end[1], this.end, [null, -1, null, null]];
 
 		// update [end][1][1][2] to fix the invariant break
 		this.end[1][1][2] = this.end[1];
@@ -80,14 +84,7 @@ var sparse_graph_t = function(){
 
 	graph.prototype.vdel = function(i){
 
-		this.eitr(i, function(e) {
-			e[2][3] = e[3];
-			if(e[3] !== null) e[3][2] = e[2];
-			e = e[4];
-			if(e === null) return;
-			e[2][3] = e[3];
-			if(e[3] !== null) e[3][2] = e[2];
-		});
+		this.eitr(i, function(e) { this.edel(e); });
 
 		
 		i[1][2] = i[2]; // next of pref becomes next
@@ -101,27 +98,35 @@ var sparse_graph_t = function(){
 		if(i[3][3][3] !== null) i[3][3][3][2] = i[3][3];
 
 		if(j !== i){
-			j[3][3] = [i, w, j[3], j[3][3], i[3][3]];
+			j[3][3] = [i, w, j[3], j[3][3], null];
 			if(j[3][3][3] !== null) j[3][3][3][2] = j[3][3];
-
-			i[3][3][4] = j[3][3];
 		}
 
-		return [i[3][3], j[3][3]];
+		this.eend[3] = [i, j, w, this.eend[3], this.eend, i[3][3], j[3][3]];
+
+		this.eend[3][3][4] = this.eend[3];
+
+		i[3][3][4] = j[3][3][4] = this.eend[3];
+
+		return this.eend[3];
 
 	};
 
 	graph.prototype.edel = function(e){
 
-		e[0][2][3] = e[0][3];
-		if(e[0][3] !== null) e[0][3][2] = e[0][2];
+		e[5][2][3] = e[5][3];
+		if(e[5][3] !== null) e[5][3][2] = e[5][2];
 
 
-		if(e[1] !== e[0]){
-			e[1][2][3] = e[1][3];
-			if(e[1][3] !== null) e[1][3][2] = e[1][2];
+		if(e[6] !== e[5]){
+			e[6][2][3] = e[6][3];
+			if(e[6][3] !== null) e[6][3][2] = e[6][2];
 		}
 
+
+		e[3][4] = e[4]; // next of pref becomes next
+		e[4][3] = e[3]; // prev of next becomes prev
+
 	};
 
 
@@ -144,7 +149,7 @@ var sparse_graph_t = function(){
 
 		while(e !== null){
 
-			if(fn.call(this, e)) return e[3];
+			if(fn.call(this, e[4], e[0], e[1])) return e[3];
 
 			e = e[3];
 		}
diff --git a/test/js/src/undirected/offline/algo/eulerian/dup.js b/test/js/src/undirected/offline/algo/eulerian/dup.js
@@ -45,9 +45,9 @@ var check = function(label, n, E, m){
 
 		var count = [gn.sqmat(2, n, 0), gn.sqmat(2, n, 0)];
 
-		g.vitr(function(w){
-			g.eitr(w, function(e){
-				++count[0][w[0]][e[0][0]];
+		g.vitr(function(u){
+			g.eitr(u, function(_, v){
+				++count[0][u[0]][v[0]];
 			});
 		});
 
@@ -62,9 +62,9 @@ var check = function(label, n, E, m){
 			}
 		}
 
-		h.vitr(function(w){
-			h.eitr(w, function(e){
-				++count[1][w[0]][e[0][0]];
+		h.vitr(function(u){
+			h.eitr(u, function(_, v){
+				++count[1][u[0]][v[0]];
 			});
 		});
 
diff --git a/test/js/src/undirected/offline/algo/eulerian/oddgraph.js b/test/js/src/undirected/offline/algo/eulerian/oddgraph.js
@@ -48,8 +48,8 @@ var check = function(label, n, E){
 			ok(degree[v[1][0]] % 2, v[1][0] + ' odd');
 			ainside[v[1][0]] = 1;
 			if(degree[v[1][0]] % 2){
-				h.eitr(v, function(e){
-					deepEqual(e[1], d[v[1][0]][e[0][1][0]], 'd['+v[1][0]+']['+e[0][1][0]+'] check');
+				h.eitr(v, function(_, u, w){
+					deepEqual(w, d[v[1][0]][u[1][0]], 'd['+v[1][0]+']['+u[1][0]+'] check');
 				});
 			}
 		});
diff --git a/test/js/src/undirected/offline/algo/eulerian/simplegraph.js b/test/js/src/undirected/offline/algo/eulerian/simplegraph.js
@@ -28,7 +28,7 @@ var check = function(name, order, E){
 
 		
 
-		var d = gn.sqmat(2, order, [0, Infinity]);
+		var d = gn.sqmat(2, order, Infinity);
 	
 		simplegraph(g, order, d, h);
 
@@ -40,25 +40,23 @@ var check = function(name, order, E){
 		h.vitr(function(v){
 
 			i = v[1][0];
-			h.eitr(v, function(e){
-				var u = e[0];
+			h.eitr(v, function(_, u, w){
 				var j = u[1][0];
 				edgecounth[i][j]++;
-				edgevalh[i][j] = e[1];
+				edgevalh[i][j] = w;
 			});
 		});
 
 
 		g.vitr(function(v){
 
 			i = v[0];
-			g.eitr(v, function(e){
-				var u = e[0];
+			g.eitr(v, function(_, u, w){
 				var j = u[0];
 
 				if(i !== j){
 					edgecountg[i][j] = 1;
-					ok(edgevalh[i][j] <= e[1], 'check (' + i + ', ' + j + ')');
+					ok(edgevalh[i][j] <= w, 'check (' + i + ', ' + j + ')');
 				}
 
 			});
diff --git a/test/js/src/undirected/offline/algo/sp/floyd.js b/test/js/src/undirected/offline/algo/sp/floyd.js
@@ -40,8 +40,8 @@ var check = function(label, n, edges){
 			b = gn.sqmat(1, n, false);
 			dijkstra(g, n, v[i], p, dist[i], u, b);
 			dist[i][i] = Infinity;
-			g.eitr([i], function(e){
-				dist[i][i] = Math.min(dist[i][i], e[1]*2);
+			g.eitr([i], function(_, _, w){
+				dist[i][i] = Math.min(dist[i][i], w*2);
 			});
 		}
 
diff --git a/test/js/src/undirected/online/data/dense.js b/test/js/src/undirected/online/data/dense.js
@@ -22,10 +22,11 @@ test('dense', function(assert){
 	e[0][2] = g.eadd(v[0], v[3], 5);
 	e[0][3] = g.eadd(v[0], v[1], 456);
 	e[0][4] = g.eadd(v[0], v[0], 5);
-	e[1][1] = [e[0][3][1], e[0][3][0]];
+	e[1][1] = e[0][3];
 	e[4] = [];
 	e[4][0] = g.eadd(v[4], v[7], 5);
 
+
 	var k = 0;
 	g.vitr(function(j){
 		deepEqual(j, v[k], 'vitr ' + k);
@@ -39,7 +40,8 @@ test('dense', function(assert){
 		var m = r[l];
 		k = e[m].length;
 		g.eitr(v[m], function(x){
-			deepEqual(x, e[m][--k][0], 'eitr ' + m + ' ' + k);
+			--k;
+			deepEqual(x, e[m][k], 'eitr ' + m + ' ' + k);
 		});
 	};
 
@@ -54,7 +56,8 @@ test('dense', function(assert){
 		var m = r[l];
 		k = e[m].length;
 		g.eitr(v[m], function(x){
-			deepEqual(x, e[m][--k][0], 'eitr ' + m + ' ' + k);
+			--k;
+			deepEqual(x, e[m][k], 'eitr ' + m + ' ' + k);
 		});
 	};
 
diff --git a/test/js/src/undirected/online/data/gindex.js b/test/js/src/undirected/online/data/gindex.js
diff --git a/test/js/src/undirected/online/data/sparse.js b/test/js/src/undirected/online/data/sparse.js
