add implementation for dfs and bfs for experiment

ASbeletsky · ASbeletsky · commit 5bc66890811e · 2018-01-04T00:30:49.000+02:00
diff --git a/algorithm/graph_search/bfs/graph_search/pure-code.js b/algorithm/graph_search/bfs/graph_search/pure-code.js
@@ -0,0 +1,36 @@
+var random = (min, max) => {
+    return (Math.random() * (max - min + 1) | 0) + min;
+};
+
+var s = random(0, G.length - 1); // s = start node
+var e; // e = start node
+do {
+    e = random(0, G.length - 1);
+} while (s === e);
+var MAX_VALUE = Infinity;
+
+function BFS() {
+    var W = []; // W[i] indicates the length of the shortest path from start node to the i-th node
+    var Q = [];
+    var i;
+    for (i = 0; i < G.length; i++) {
+        W.push(MAX_VALUE);
+    }
+    W[s] = 0;
+    Q.push(s); // add start node to queue
+    while (Q.length > 0) {
+        var node = Q.shift(); // dequeue
+        for (i = 0; i < G[node].length; i++) {
+            if (G[node][i]) { // if the edge from current node to the i-th node exists
+                if (W[i] > W[node] + G[node][i]) { // if current path is shorter than the previously shortest path
+                    W[i] = W[node] + G[node][i]; // update the length of the shortest path
+                    Q.push(i); // add child node to queue
+                }
+            }
+        }
+    }
+    return W[e];
+}
+
+var minWeight = BFS(s);
+
diff --git a/algorithm/graph_search/dfs/graph_search/pure-code.js b/algorithm/graph_search/dfs/graph_search/pure-code.js
@@ -0,0 +1,34 @@
+var random = (min, max) => {
+    return (Math.random() * (max - min + 1) | 0) + min;
+};
+
+var s = random(0, G.length - 1); // s = start node
+var e; // e = end node
+do {
+    e = random(0, G.length - 1);
+} while (s === e);
+var MAX_VALUE = Infinity;
+var minWeight = MAX_VALUE;
+var D = []; // D[i] indicates whether the i-th node is discovered or not
+for (var i = 0; i < G.length; i++) D.push(false);
+
+function DFS(node, parent, weight) { // node = current node, parent = previous node
+    if (minWeight < weight) return;
+    if (node === e) {
+        if (minWeight > weight) {
+            minWeight = weight;
+        }
+        return;
+    }
+    D[node] = true; // label current node as discovered
+    for (var i = 0; i < G[node].length; i++) {
+        if (G[node][i]) { // if the path from current node to the i-th node exists
+            if (!D[i]) { // if the i-th node is not labeled as discovered
+                DFS(i, node, weight + G[node][i]); // recursively call DFS
+            }
+        }
+    }
+    D[node] = false; // label current node as undiscovered
+}
+
+DFS(s, undefined, 0);
diff --git a/js/experiment/components/ExecutionTime3dChart.js b/js/experiment/components/ExecutionTime3dChart.js
@@ -52,7 +52,7 @@ class ExecutionTime3dChart extends React.Component {
 
 function mapStateToProps(state) {
     return {
-        calculationsPerformed: state.timeMeasure.length > 10,
+        calculationsPerformed: state.timeMeasure.length > 2,
         algorithms: state.algorithms,
         timeMeasure: state.timeMeasure.sort(arrayUtils.sortBy("graphSize"))
     };
