Skip to content

Commit b9e3623

Browse files
author
duaraghav8@gmail
committed
Merge remote-tracking branch 'upstream/gh-pages'
2 parents 6624e8b + 90ae4ab commit b9e3623

File tree

10 files changed

+325
-85
lines changed

10 files changed

+325
-85
lines changed

‎algorithm/graph_search/bfs/shortest_path/code.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ var e; // e = start node
2727
do {
2828
e = Math.random() * G.length | 0;
2929
} while (s == e);
30-
var MAX_VALUE = 999;
30+
var MAX_VALUE = Infinity;
3131
tracer._pace(100);
3232
tracer._print('finding the shortest path from ' + s + ' to ' + e);
3333
tracer._sleep(1000);

‎algorithm/graph_search/dfs/shortest_path/code.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ var e; // e = end node
2525
do {
2626
e = Math.random() * G.length | 0;
2727
} while (s == e);
28-
var MAX_VALUE = 999;
28+
var MAX_VALUE = Infinity;
2929
var minWeight = MAX_VALUE;
3030
tracer._pace(100);
3131
tracer._print('finding the shortest path from ' + s + ' to ' + e);

‎algorithm/graph_search/dijkstra/shortest_path/code.js

+41-40
Original file line numberDiff line numberDiff line change
@@ -1,49 +1,50 @@
1-
function Dijkstra(start, end){
2-
tracer._sleep(333)
3-
var minIndex, minDistance;
4-
var S = []; // S[i] returns the distance from node v to node start
5-
var D = []; // D[i] indicates whether the i-th node is discovered or not
6-
for (var i = 0; i < G.length; i++){
7-
D.push(false);
8-
S[i] = 19990719 // Some big distance (infinity)
9-
}
10-
S[start] = 0; // Starting node is at distance 0 from itself
11-
for(var k = 0; k < G.length; k++){
12-
// Finding a node with the shortest distance from S[minIndex]
13-
minDistance = 19990719 // Some big distance (infinity)
14-
for(i = 0; i < G.length; i++){
15-
if(S[i] < minDistance && !D[i]){
16-
minDistance = S[i];
17-
minIndex = i;
18-
}
19-
}
20-
tracer._visit(minIndex,undefined);
21-
tracer._sleep(500);
22-
D[minIndex] = true;
23-
if(minDistance == 19990719){ // If the distance is big (infinity), there is no more paths
24-
tracer._print('there is no path from ' + s + ' to ' + e);
25-
return false;
26-
}
27-
// For every unvisited neighbour of current node, we check
28-
// whether the path to it is shorter if going over the current node
29-
for(i = 0; i < G.length; i++){
30-
if (G[minIndex][i] && !D[i] && ( S[i] > S[minIndex] + G[minIndex][i])){
31-
S[i] = S[minIndex] + G[minIndex][i];
32-
tracer._visit(i,minIndex,S[i]);
33-
tracer._sleep(500);
34-
tracer._leave(i,minIndex,S[i]);
35-
}
36-
}
37-
tracer._leave(minIndex,undefined);
38-
}
39-
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + S[e]);
1+
function Dijkstra(start, end) {
2+
tracer._sleep();
3+
var MAX_VALUE = Infinity;
4+
var minIndex, minDistance;
5+
var S = []; // S[i] returns the distance from node v to node start
6+
var D = []; // D[i] indicates whether the i-th node is discovered or not
7+
for (var i = 0; i < G.length; i++) {
8+
D.push(false);
9+
S[i] = MAX_VALUE;
10+
}
11+
S[start] = 0; // Starting node is at distance 0 from itself
12+
var k = G.length;
13+
while (k--) {
14+
// Finding a node with the shortest distance from S[minIndex]
15+
minDistance = MAX_VALUE;
16+
for (i = 0; i < G.length; i++) {
17+
if (S[i] < minDistance && !D[i]) {
18+
minDistance = S[i];
19+
minIndex = i;
20+
}
21+
}
22+
if (minDistance == MAX_VALUE) break; // If there is no edge from current node, jump out of loop
23+
D[minIndex] = true;
24+
tracer._visit(minIndex);
25+
// For every unvisited neighbour of current node, we check
26+
// whether the path to it is shorter if going over the current node
27+
for (i = 0; i < G.length; i++) {
28+
if (G[minIndex][i] && S[i] > S[minIndex] + G[minIndex][i]) {
29+
S[i] = S[minIndex] + G[minIndex][i];
30+
tracer._visit(i, minIndex, S[i]);
31+
tracer._leave(i, minIndex, S[i]);
32+
}
33+
}
34+
tracer._leave(minIndex);
35+
}
36+
if (S[end] == MAX_VALUE) {
37+
tracer._print('there is no path from ' + start + ' to ' + end);
38+
} else {
39+
tracer._print('the shortest path from ' + start + ' to ' + end + ' is ' + S[end]);
40+
}
4041
}
4142

4243
var s = Math.random() * G.length | 0; // s = start node
4344
var e; // e = end node
4445
do {
4546
e = Math.random() * G.length | 0;
4647
} while (s == e);
47-
tracer._pace(100);
48+
tracer._pace(500);
4849
tracer._print('finding the shortest path from ' + s + ' to ' + e);
4950
Dijkstra(s, e);

‎algorithm/graph_search/floyd_warshall/shortest_paths/code.js

+29-28
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,35 @@
1-
function FloydWarshall(){
2-
// Finds the shortest path between all nodes
3-
var S = new Array(G.length);
4-
for (var i = 0; i < G.length; i++) S[i] = new Array(G.length)
5-
for (i = 0; i < G.length; i++){
6-
tracer._visit(i)
7-
for (var j = 0; j < G.length; j++){
8-
// Distance to self is always 0
9-
if (i==j) S[i][i] = 0;
10-
// Distance between connected nodes is their weight
11-
else if (G[i][j] > 0){
12-
S[i][j] = G[i][j];
13-
tracer._visit(j,i,S[i][j]);
14-
tracer._leave(j,i,S[i][j]);
15-
}// Else we don't know the distnace and we set it to a big value (infinity)
16-
else S[i][j] = 19990719;
1+
function FloydWarshall() {
2+
// Finds the shortest path between all nodes
3+
var S = new Array(G.length);
4+
for (var i = 0; i < G.length; i++) S[i] = new Array(G.length)
5+
for (i = 0; i < G.length; i++) {
6+
tracer._visit(i)
7+
for (var j = 0; j < G.length; j++) {
8+
// Distance to self is always 0
9+
if (i == j) S[i][i] = 0;
10+
// Distance between connected nodes is their weight
11+
else if (G[i][j] > 0) {
12+
S[i][j] = G[i][j];
13+
tracer._visit(j, i, S[i][j]);
14+
tracer._leave(j, i, S[i][j]);
15+
}// Else we don't know the distance and we set it to infinity
16+
else S[i][j] = MAX_VALUE;
17+
}
18+
tracer._leave(i)
1719
}
18-
tracer._leave(i)
19-
}
20-
// If there is a shorter path using k, use it instead
21-
for (var k = 0; k < G.length; k++)
22-
for (i = 0; i < G.length; i++)
20+
// If there is a shorter path using k, use it instead
21+
for (var k = 0; k < G.length; k++)
22+
for (i = 0; i < G.length; i++)
23+
for (j = 0; j < G.length; j++)
24+
if (S[i][j] > S[i][k] + S[k][j])
25+
S[i][j] = S[i][k] + S[k][j];
26+
for (i = 0; i < G.length; i++)
2327
for (j = 0; j < G.length; j++)
24-
if (S[i][j] > S[i][k] + S[k][j])
25-
S[i][j] = S[i][k] + S[k][j];
26-
for (i = 0; i < G.length; i++)
27-
for (j = 0; j < G.length; j++)
28-
if(S[i][j] == 19990719) tracer._print('there is no path from ' + i + ' to ' + j);
29-
else tracer._print('the shortest path from ' + i +
30-
' to ' + j + ' is ' + S[i][j]);
28+
if (S[i][j] == MAX_VALUE) tracer._print('there is no path from ' + i + ' to ' + j);
29+
else tracer._print('the shortest path from ' + i +
30+
' to ' + j + ' is ' + S[i][j]);
3131
}
32+
var MAX_VALUE = Infinity;
3233
tracer._pace(200);
3334
tracer._print('finding the shortest paths from and to all nodes');
3435
FloydWarshall();

‎algorithm/sorting/merge/basic/code.js

+1-1
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ mergeSort.merge = function(start, middle, end) {
5959
i++;
6060
}
6161

62-
tempArray = [];
62+
var tempArray = [];
6363
for (i = start; i < end; i++) tempArray.push(D[i]);
6464
tracer._print('merged array = [' + tempArray.join(', ') + ']');
6565
};

‎index.html

+2
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,9 @@ <h3>Reference</h3>
109109
<script src="js/ace/ace.js"></script>
110110
<script src="js/module/tracer.js"></script>
111111
<script src="js/module/directed_graph.js"></script>
112+
<script src="js/module/undirected_graph.js"></script>
112113
<script src="js/module/weighted_directed_graph.js"></script>
114+
<script src="js/module/weighted_undirected_graph.js"></script>
113115
<script src="js/module/array2d.js"></script>
114116
<script src="js/module/array1d.js"></script>
115117
<script src="js/script.js"></script>

‎js/module/directed_graph.js

+8-7
Original file line numberDiff line numberDiff line change
@@ -68,8 +68,7 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
6868
root = root || 0;
6969
var maxDepth = -1;
7070

71-
var chk = [];
72-
for (var i = 0; i < G.length; i++) chk.push(false);
71+
var chk = new Array(G.length);
7372
var getDepth = function (node, depth) {
7473
if (chk[node]) throw "the given graph is not a tree because it forms a circuit";
7574
chk[node] = true;
@@ -233,6 +232,7 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
233232
color = defaultEdgeColor;
234233
break;
235234
}
235+
236236
return color;
237237
},
238238
drawLabel: function (node, context, settings) {
@@ -306,10 +306,10 @@ DirectedGraphTracer.prototype = $.extend(true, Object.create(Tracer.prototype),
306306
drawOnHover: function (node, context, settings, next) {
307307
var tracer = this;
308308

309+
context.setLineDash([5, 5]);
309310
var nodeIdx = node.id.substring(1);
310311
graph.edges().forEach(function (edge) {
311312
var ends = edge.id.substring(1).split("_");
312-
context.setLineDash([5, 5]);
313313
if (ends[0] == nodeIdx) {
314314
var color = '#0ff';
315315
var source = node;
@@ -331,12 +331,13 @@ var DirectedGraph = {
331331
random: function (N, ratio) {
332332
if (!N) N = 5;
333333
if (!ratio) ratio = .3;
334-
var G = [];
334+
var G = new Array(N);
335335
for (var i = 0; i < N; i++) {
336-
G.push([]);
336+
G[i] = new Array(N);
337337
for (var j = 0; j < N; j++) {
338-
if (i == j) G[i].push(0);
339-
else G[i].push((Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0);
338+
if (i != j) {
339+
G[i][j] = (Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0;
340+
}
340341
}
341342
}
342343
return G;

‎js/module/undirected_graph.js

+133
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
function UndirectedGraphTracer(module) {
2+
if (DirectedGraphTracer.call(this, module || UndirectedGraphTracer)) {
3+
UndirectedGraphTracer.prototype.init.call(this);
4+
return true;
5+
}
6+
return false;
7+
}
8+
9+
UndirectedGraphTracer.prototype = $.extend(true, Object.create(DirectedGraphTracer.prototype), {
10+
constructor: UndirectedGraphTracer,
11+
init: function () {
12+
var tracer = this;
13+
14+
s.settings({
15+
defaultEdgeType: 'def'
16+
});
17+
sigma.canvas.edges.def = function (edge, source, target, context, settings) {
18+
var color = tracer.getColor(edge, source, target, settings);
19+
tracer.drawEdge(edge, source, target, color, context, settings);
20+
};
21+
},
22+
_setData: function (G) {
23+
if (Tracer.prototype._setData.call(this, arguments)) return true;
24+
25+
graph.clear();
26+
var nodes = [];
27+
var edges = [];
28+
var unitAngle = 2 * Math.PI / G.length;
29+
var currentAngle = 0;
30+
for (var i = 0; i < G.length; i++) {
31+
currentAngle += unitAngle;
32+
nodes.push({
33+
id: this.n(i),
34+
label: '' + i,
35+
x: .5 + Math.sin(currentAngle) / 2,
36+
y: .5 + Math.cos(currentAngle) / 2,
37+
size: 1,
38+
color: this.color.default
39+
});
40+
}
41+
for (var i = 0; i < G.length; i++) {
42+
for (var j = 0; j <= i; j++) {
43+
if (G[i][j] || G[j][i]) {
44+
edges.push({
45+
id: this.e(i, j),
46+
source: this.n(i),
47+
target: this.n(j),
48+
color: this.color.default,
49+
size: 1
50+
});
51+
}
52+
}
53+
}
54+
55+
graph.read({
56+
nodes: nodes,
57+
edges: edges
58+
});
59+
s.camera.goTo({
60+
x: 0,
61+
y: 0,
62+
angle: 0,
63+
ratio: 1
64+
});
65+
this.refresh();
66+
67+
return false;
68+
},
69+
e: function (v1, v2) {
70+
if (v1 > v2) {
71+
var temp = v1;
72+
v1 = v2;
73+
v2 = temp;
74+
}
75+
return 'e' + v1 + '_' + v2;
76+
},
77+
drawOnHover: function (node, context, settings, next) {
78+
var tracer = this;
79+
80+
context.setLineDash([5, 5]);
81+
var nodeIdx = node.id.substring(1);
82+
graph.edges().forEach(function (edge) {
83+
var ends = edge.id.substring(1).split("_");
84+
if (ends[0] == nodeIdx) {
85+
var color = '#0ff';
86+
var source = node;
87+
var target = graph.nodes('n' + ends[1]);
88+
tracer.drawEdge(edge, source, target, color, context, settings);
89+
if (next) next(edge, source, target, color, context, settings);
90+
} else if (ends[1] == nodeIdx) {
91+
var color = '#0ff';
92+
var source = graph.nodes('n' + ends[0]);
93+
var target = node;
94+
tracer.drawEdge(edge, source, target, color, context, settings);
95+
if (next) next(edge, source, target, color, context, settings);
96+
}
97+
});
98+
},
99+
drawEdge: function (edge, source, target, color, context, settings) {
100+
var prefix = settings('prefix') || '',
101+
size = edge[prefix + 'size'] || 1;
102+
103+
context.strokeStyle = color;
104+
context.lineWidth = size;
105+
context.beginPath();
106+
context.moveTo(
107+
source[prefix + 'x'],
108+
source[prefix + 'y']
109+
);
110+
context.lineTo(
111+
target[prefix + 'x'],
112+
target[prefix + 'y']
113+
);
114+
context.stroke();
115+
}
116+
});
117+
118+
var UndirectedGraph = {
119+
random: function (N, ratio) {
120+
if (!N) N = 5;
121+
if (!ratio) ratio = .3;
122+
var G = new Array(N);
123+
for (var i = 0; i < N; i++) G[i] = new Array(N);
124+
for (var i = 0; i < N; i++) {
125+
for (var j = 0; j < N; j++) {
126+
if (i > j) {
127+
G[i][j] = G[j][i] = (Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0;
128+
}
129+
}
130+
}
131+
return G;
132+
}
133+
};

‎js/module/weighted_directed_graph.js

+4-7
Original file line numberDiff line numberDiff line change
@@ -215,15 +215,12 @@ var WeightedDirectedGraph = {
215215
if (!ratio) ratio = .3;
216216
if (!min) min = 1;
217217
if (!max) max = 5;
218-
var G = [];
218+
var G = new Array(N);
219219
for (var i = 0; i < N; i++) {
220-
G.push([]);
220+
G[i] = new Array(N);
221221
for (var j = 0; j < N; j++) {
222-
if (i == j) G[i].push(0);
223-
else if ((Math.random() * (1 / ratio) | 0) == 0) {
224-
G[i].push((Math.random() * (max - min + 1) | 0) + min);
225-
} else {
226-
G[i].push(0);
222+
if (i != j && (Math.random() * (1 / ratio) | 0) == 0) {
223+
G[i][j] = (Math.random() * (max - min + 1) | 0) + min;
227224
}
228225
}
229226
}

0 commit comments

Comments
 (0)