Skip to content

Commit cd98310

Browse files
64json64json
committed
add WeightedGraphTracer module
1 parent eecf242 commit cd98310

File tree

11 files changed

+481
-197
lines changed

11 files changed

+481
-197
lines changed

‎algorithm/graph_search/dfs/config.json

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
],
2323
"files": {
2424
"sample1": "Visiting all connected nodes without making any circuit",
25-
"sample2": "Going through all paths without making any circuit"
25+
"sample2": "Going through all paths without making any circuit",
26+
"sample3": "DFS of Weighted Graph"
2627
}
2728
}

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

Lines changed: 14 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,22 @@
11
var D; // D[i] indicates whether the i-th node is discovered or not
22

3-
function DFS(v, p) { // v = current node, p = previous node
4-
tracer.visit(v, p);
5-
D[v] = true; // label v as discovered
6-
G[v].forEach(function (w) { // G[v] contains edges starting from v
7-
if (!D[w]) { // if w is not labeled as discovered
8-
DFS(w, v); // recursively call DFS
3+
function DFS(node, parent) { // node = current node, parent = previous node
4+
D[node] = true; // label current node as discovered
5+
tracer._visit(node, parent);
6+
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+
}
911
}
10-
});
11-
tracer.leave(v, p);
12+
}
13+
tracer._leave(node, parent);
1214
}
1315

1416
for (var i = 0; i < G.length; i++) { // start from every node
15-
tracer.print('start from ' + i);
16-
D = new Array(G.length);
17+
tracer._print('start from ' + i);
18+
D = [];
19+
for (var j = 0; j < G.length; j++) D[j] = false;
1720
DFS(i);
18-
tracer.clear();
21+
tracer._clear();
1922
}

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

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
var tracer = new GraphTracer();
2-
var G = [
3-
[3, 4], // connected nodes from node 0
4-
[2, 4],
5-
[1],
6-
[1],
7-
[2]
8-
];
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);
910
tracer.setData(G);

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

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,23 @@
11
var D; // D[i] indicates whether the i-th node is discovered or not
22

3-
function DFS(v, p) { // v = current node, p = previous node
4-
tracer.visit(v, p);
5-
D[v] = true; // label v as discovered
6-
G[v].forEach(function (w) { // G[v] contains edges starting from v
7-
if (!D[w]) { // if w is not labeled as discovered
8-
DFS(w, v); // recursively call DFS
3+
function DFS(node, parent) { // node = current node, parent = previous node
4+
D[node] = true; // label current node as discovered
5+
tracer._visit(node, parent);
6+
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+
}
911
}
10-
});
11-
D[v] = false; // label v as undiscovered
12-
tracer.leave(v, p);
12+
}
13+
D[node] = false; // label current node as undiscovered
14+
tracer._leave(node, parent);
1315
}
1416

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

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

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
var tracer = new GraphTracer();
2-
var G = [
3-
[1,2,3,4], // connected nodes from node 0
4-
[0,2,3,4],
5-
[0,1,3,4],
6-
[0,1,2,4],
7-
[0,1,2,3]
8-
];
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, .75);
910
tracer.setData(G);

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

Lines changed: 28 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,36 @@
11
var D; // D[i] indicates whether the i-th node is discovered or not
2+
var W; // W[i] indicates the weight of the i-th node
23

3-
function DFS(v, p) { // v = current node, p = previous node
4-
tracer.visit(v, p);
5-
D[v] = true; // label v as discovered
6-
G[v].forEach(function (w) { // G[v] contains edges starting from v
7-
if (!D[w]) { // if w is not labeled as discovered
8-
DFS(w, v); // recursively call DFS
4+
function getWeight(v, p) {
5+
if (p === undefined) return 0;
6+
return W[p] + G[p][v]; // the sum of the weights of previous node and the path
7+
}
8+
9+
function DFS(node, parent) { // node = current node, parent = previous node
10+
D[node] = true; // label current node as discovered
11+
W[node] = getWeight(node, parent); // update the weight of the node
12+
tracer._visit(node, parent, W[node]);
13+
for (var i = 0; i < G[node].length; i++) {
14+
if (G[node][i]) { // if the path from current node to the i-th node exists
15+
if (!D[i]) { // if the i-th node is not labeled as discovered
16+
DFS(i, node); // recursively call DFS
17+
}
918
}
10-
});
11-
tracer.leave(v, p);
19+
}
20+
D[node] = false; // label current node as undiscovered
21+
W[node] = 0; // reset the weight of the node
22+
tracer._leave(node, parent, W[node]);
1223
}
1324

25+
tracer._pace(1000);
1426
for (var i = 0; i < G.length; i++) { // start from every node
15-
tracer.print('start from ' + i);
16-
D = new Array(G.length);
27+
tracer._print('start from ' + i);
28+
D = [];
29+
W = [];
30+
for (var j = 0; j < G.length; j++) {
31+
D[j] = false;
32+
W[j] = 0;
33+
}
1734
DFS(i);
18-
tracer.clear();
35+
tracer._clear();
1936
}

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

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
var tracer = new WeightedGraphTracer();
2-
var G = [
3-
{3: 1, 4: 2}, // connected nodes from node 0
4-
{2: 1, 4: 3},
5-
{1: 4},
6-
{1: 1},
7-
{2: 2}
8-
];
2+
/*var G = [ // G[i][j] indicates the weight of the path from the i-th node to the j-th node
3+
[0, 3, 0, 1, 0],
4+
[5, 0, 1, 2, 4],
5+
[1, 0, 0, 2, 0],
6+
[0, 2, 0, 0, 1],
7+
[0, 1, 3, 0, 0]
8+
];*/
9+
var G = tracer.createRandomData(5, .5);
910
tracer.setData(G);

‎index.html

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,7 @@ <h3>Reference</h3>
8484
<script src="js/ace/ace.js"></script>
8585
<script src="js/tracer.js"></script>
8686
<script src="js/module/graph.js"></script>
87+
<script src="js/module/weighted_graph.js"></script>
8788
<script src="js/script.js"></script>
8889
</body>
8990
</html>

0 commit comments

Comments
 (0)