From ed0ac6791435c36e8374b218454ebfa7485f0845 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com>
Date: Fri, 6 Jan 2017 15:57:28 -0500
Subject: Optimalize by using vectors over maps and sets

- Can iterate over vertices with for (int v = 0; v < number_vertices;
v++) loop
- This required internally remapping the vertices from their actual
names to 0, 1, ..., number_vertices - 1.
- Use Graph::get_real_vertex(vertex) to get original value
---
 src/dependency_calculator.h | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

(limited to 'src/dependency_calculator.h')

diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h
index 93a751e..c24f5ef 100644
--- a/src/dependency_calculator.h
+++ b/src/dependency_calculator.h
@@ -18,24 +18,24 @@ public:
     }
 
     double get_dependency(int vertex) const {
-        return dependency_.find(vertex)->second;
+        return dependency_[vertex];
     }
 private:
     const Graph& graph_; // (V, E)
     int vertex_; // s
     std::stack<int> stack_; // S
-    std::unordered_map<int, std::vector<int>> shortest_path_predecessors_; // P
-    std::unordered_map<int, int> shortest_paths_; // sigma
-    std::unordered_map<int, int> distance_; // d
+    std::vector<std::vector<int>> shortest_path_predecessors_; // P
+    std::vector<int> shortest_paths_; // sigma
+    std::vector<int> distance_; // d
     std::queue<int> queue_; // Q
-    std::unordered_map<int, double> dependency_; // delta
+    std::vector<double> dependency_; // delta
 
     void init_() {
-        for (int vertex : graph_.get_vertices()) {
-            shortest_path_predecessors_[vertex] = std::vector<int>();
-            shortest_paths_[vertex] = 0;
-            distance_[vertex] = -1;
-            dependency_[vertex] = 0;
+        for (int vertex = 0; vertex < graph_.get_number_vertices(); vertex++) {
+            shortest_path_predecessors_.emplace_back();
+            shortest_paths_.push_back(0);
+            distance_.push_back(-1);
+            dependency_.push_back(0);
         }
 
         shortest_paths_[vertex_] = 1;
-- 
cgit v1.2.3