Skip to content

Commit fcdf78e

Browse files
64json64json
committed
tree
1 parent d656bed commit fcdf78e

File tree

11 files changed

+126
-35
lines changed

11 files changed

+126
-35
lines changed

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

+16
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
function BFS(s) { // s = start node
2+
var Q = [];
3+
tracer._visit(s);
4+
Q.push(s); // add start node to queue
5+
while (Q.length > 0) {
6+
var node = Q.shift(); // dequeue
7+
for (var i = 0; i < G[node].length; i++) {
8+
if (G[node][i]) { // if current node has the i-th node as a child
9+
tracer._visit(i, node);
10+
Q.push(i); // add child node to queue
11+
}
12+
}
13+
}
14+
}
15+
16+
BFS(0);

‎algorithm/graph_search/bfs/basic/data.js

+15
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
var tracer = new GraphTracer();
2+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
3+
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
4+
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
5+
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
6+
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
7+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
8+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
10+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
13+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
14+
];
15+
tracer.setTreeData(G, 0);

‎algorithm/graph_search/bfs/config.json

+22
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
{
2+
"def": "Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.",
3+
"apps": [
4+
"Copying garbage collection, Cheney's algorithm",
5+
"Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search)",
6+
"Testing a graph for bipartiteness",
7+
"(Reverse) Cuthill–McKee mesh numbering",
8+
"Ford–Fulkerson method for computing the maximum flow in a flow network",
9+
"Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.",
10+
"Construction of the failure function of the Aho-Corasick pattern matcher."
11+
],
12+
"cpx": {
13+
"time": "O(|E|)",
14+
"space": "O(|V|)"
15+
},
16+
"refs": [
17+
"https://en.wikipedia.org/wiki/Breadth-first_search"
18+
],
19+
"files": {
20+
"basic": "Searching a tree"
21+
}
22+
}

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

+3-15
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,10 @@
1-
var D; // D[i] indicates whether the i-th node is discovered or not
2-
31
function DFS(node, parent) { // node = current node, parent = previous node
4-
D[node] = true; // label current node as discovered
52
tracer._visit(node, parent);
63
for (var i = 0; i < G[node].length; i++) {
7-
if (G[node][i]) { // if the path from current node to the i-th node exists
8-
if (!D[i]) { // if the i-th node is not labeled as discovered
9-
DFS(i, node); // recursively call DFS
10-
}
4+
if (G[node][i]) { // if current node has the i-th node as a child
5+
DFS(i, node); // recursively call DFS
116
}
127
}
13-
tracer._leave(node, parent);
148
}
159

16-
for (var i = 0; i < G.length; i++) { // start from every node
17-
tracer._print('start from ' + i);
18-
D = [];
19-
for (var j = 0; j < G.length; j++) D[j] = false;
20-
DFS(i);
21-
tracer._clear();
22-
}
10+
DFS(0);

‎algorithm/graph_search/dfs/basic/data.js

+14-9
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,15 @@
11
var tracer = new GraphTracer();
2-
/*var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
3-
[0, 1, 1, 1, 0],
4-
[0, 0, 1, 1, 1],
5-
[0, 0, 0, 0, 0],
6-
[0, 0, 0, 0, 1],
7-
[0, 0, 0, 0, 0]
8-
];*/
9-
var G = tracer.createRandomData(5, .3);
10-
tracer.setData(G);
2+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
3+
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
4+
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
5+
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
6+
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
7+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
8+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
10+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
13+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
14+
];
15+
tracer.setTreeData(G, 0);

‎algorithm/graph_search/dfs/config.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,8 @@
2121
"https://en.wikipedia.org/wiki/Depth-first_search"
2222
],
2323
"files": {
24-
"basic": "Visiting all connected nodes without making any circuit",
25-
"all_paths": "Going through all paths without making any circuit",
24+
"basic": "Searching a tree",
25+
"all_paths": "Going through all possible paths without making any circuit",
2626
"weighted_graph": "DFS of Weighted Graph",
2727
"shortest_path": "Finding the shortest path"
2828
}

‎css/stylesheet.css

+2-2
Original file line numberDiff line numberDiff line change
@@ -188,14 +188,14 @@ section {
188188

189189
.data_container {
190190
top: 60px;
191-
bottom: 70%;
191+
bottom: 60%;
192192
left: 0;
193193
right: 0;
194194
}
195195

196196
.code_container {
197197
left: 0;
198-
top: 30%;
198+
top: 40%;
199199
right: 0;
200200
bottom: 0;
201201
}

‎js/module/graph.js

+46-1
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ GraphTracer.prototype.clear = function () {
2626
GraphTracer.prototype.createRandomData = function (N, ratio) {
2727
Tracer.prototype.createRandomData.call(this, arguments);
2828

29+
if (!N) N = 5;
2930
if (!ratio) ratio = .3;
3031
var G = [];
3132
for (var i = 0; i < N; i++) {
@@ -39,9 +40,51 @@ GraphTracer.prototype.createRandomData = function (N, ratio) {
3940
return G;
4041
};
4142

43+
GraphTracer.prototype.setTreeData = function (G, root) {
44+
root = root || 0;
45+
var maxDepth = -1;
46+
47+
var chk = [];
48+
for (var i = 0; i < G.length; i++) chk.push(false);
49+
var getDepth = function (node, depth) {
50+
if (chk[node]) throw "the given graph is not a tree because it forms a circuit";
51+
chk[node] = true;
52+
if (maxDepth < depth) maxDepth = depth;
53+
for (var i = 0; i < G[node].length; i++) {
54+
if (G[node][i]) getDepth(i, depth + 1);
55+
}
56+
};
57+
getDepth(root, 1);
58+
59+
if (this.setData(G, root)) return true;
60+
61+
var place = function (node, x, y) {
62+
var temp = graph.nodes(n(node));
63+
temp.x = x;
64+
temp.y = y;
65+
};
66+
67+
var wgap = 1 / (maxDepth - 1);
68+
var dfs = function (node, depth, top, bottom) {
69+
place(node, depth * wgap, (top + bottom) / 2);
70+
var children = 0;
71+
for (var i = 0; i < G[node].length; i++) {
72+
if (G[node][i]) children++;
73+
}
74+
var vgap = (bottom - top) / children;
75+
var cnt = 0;
76+
for (var i = 0; i < G[node].length; i++) {
77+
if (G[node][i]) dfs(i, depth + 1, top + vgap * cnt, top + vgap * ++cnt);
78+
}
79+
};
80+
dfs(root, 0, 0, 1);
81+
82+
this.refresh();
83+
};
84+
4285
// Override
4386
GraphTracer.prototype.setData = function (G) {
44-
if (Tracer.prototype.setData.call(this, arguments)) return;
87+
if (Tracer.prototype.setData.call(this, arguments)) return true;
4588

4689
graph.clear();
4790
var nodes = [];
@@ -82,6 +125,8 @@ GraphTracer.prototype.setData = function (G) {
82125
ratio: 1
83126
});
84127
this.refresh();
128+
129+
return false;
85130
};
86131

87132
GraphTracer.prototype._clear = function () {

‎js/module/weighted_graph.js

+1
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ WeightedGraphTracer.prototype.clear = function () {
2020
WeightedGraphTracer.prototype.createRandomData = function (N, ratio, min, max) {
2121
Tracer.prototype.createRandomData.call(this, arguments);
2222

23+
if (!N) N = 5;
2324
if (!ratio) ratio = .3;
2425
if (!min) min = 1;
2526
if (!max) max = 5;

‎js/script.js

+3-2
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,9 @@ dataEditor.on('change', function () {
2020
});
2121

2222
var loadFile = function (category, algorithm, file, explanation) {
23+
lastData = null;
2324
$('#explanation').html(explanation);
24-
dataEditor.setValue('var G = [];', -1);
25+
dataEditor.setValue('');
2526
codeEditor.setValue('');
2627

2728
var dir = './algorithm/' + category + '/' + algorithm + '/' + file + '/';
@@ -49,7 +50,7 @@ var loadAlgorithm = function (category, algorithm) {
4950
$('#desc_ref').empty();
5051
$('.files_bar').empty();
5152
$('#explanation').html('');
52-
dataEditor.setValue('var G = [];', -1);
53+
dataEditor.setValue('');
5354
codeEditor.setValue('');
5455

5556
var dir = './algorithm/' + category + '/' + algorithm + '/';

‎js/tracer.js

+2-4
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
var timer = null;
2-
var lastModule = null, lastData = null;
2+
var lastData = null;
33
var stepLimit = 1e6;
44

55
var Tracer = function (module) {
@@ -9,7 +9,6 @@ var Tracer = function (module) {
99
this.traceOptions = null;
1010
this.traceIndex = -1;
1111
this.stepCnt = 0;
12-
lastData = null;
1312
};
1413

1514
Tracer.prototype.resize = function () {
@@ -31,8 +30,7 @@ Tracer.prototype.createRandomData = function (arguments) {
3130

3231
Tracer.prototype.setData = function (arguments) {
3332
var data = JSON.stringify(arguments);
34-
if (lastModule == this.module && lastData == data) return true;
35-
lastModule = this.module;
33+
if (lastData == data) return true;
3634
lastData = data;
3735
return false;
3836
};

0 commit comments

Comments
 (0)