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

4 files changed, 72 insertions, 35 deletions

diff --git a/src/brandes.cc b/src/brandes.cc
index 7d12ec6..c4c14cd 100644
--- a/src/brandes.cc
+++ b/src/brandes.cc
@@ -14,7 +14,7 @@ std::string input_file;
 std::string output_file;
 
 Graph graph;
-std::unordered_map<int, double> betweenness;
+std::vector<double> betweenness;
 std::queue<int> vertices_to_process;
 
 std::vector<std::thread> threads_list;
@@ -40,8 +40,8 @@ void parse_input() {
 }
 
 void init() {
-    for (int vertex : graph.get_vertices()) {
-        betweenness[vertex] = 0;
+    for (int vertex = 0; vertex < graph.get_number_vertices(); vertex++) {
+        betweenness.push_back(0);
         vertices_to_process.push(vertex);
     }
 }
@@ -58,7 +58,7 @@ int next_vertex() {
 
 void update_betweenness(int vertex, DependencyCalculator& dc) {
     std::lock_guard<std::mutex> lock(betweenness_mutex);
-    for (int v : graph.get_vertices()) {
+    for (int v = 0; v < graph.get_number_vertices(); v++) {
         if (v != vertex ) {
             betweenness[v] += dc.get_dependency(v);
         }
@@ -88,9 +88,9 @@ void join_threads() {
 void print_betweenness() {
     std::ofstream fout(output_file);
 
-    for (int vertex : graph.get_vertices()) {
+    for (int vertex = 0; vertex < graph.get_number_vertices(); vertex++) {
         if (graph.has_out_edges(vertex)) {
-            fout << vertex << " " << betweenness[vertex] << std::endl;
+            fout << graph.get_real_vertex(vertex) << " " << betweenness[vertex] << std::endl;
         }
     }
 }
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;
diff --git a/src/graph.h b/src/graph.h
index f313cae..85c66e7 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -8,44 +8,60 @@
 
 class Graph {
 public:
-    Graph() : vertices_(), graph_() {}
+    Graph() : vertices_(), graph_(), number_vertices_(0) {}
 
     void add_vertex(int vertex) {
         if (vertices_.find(vertex) == vertices_.end()) {
             vertices_.insert(vertex);
             orderable_vertices_.push_back(vertex);
-            graph_[vertex] = std::vector<int>();
+            graph_.push_back(std::vector<int>());
+            has_out_edges_.push_back(false);
+            number_vertices_++;
         }
     }
 
     void add_edge(int from, int to) {
-        add_vertex(from);
-        add_vertex(to);
-        graph_[from].push_back(to);
-        has_out_edges_.insert(from);
+        graph_[mapped_to_[from]].push_back(mapped_to_[to]);
+        has_out_edges_[mapped_to_[from]] = true;
     }
 
-    void sort_vertices() {
-        std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+    void done_with_vertices() {
+        sort_vertices_();
+        map_vertices_();
     }
 
-    const std::vector<int>& get_vertices() const {
-        return orderable_vertices_;
+    int get_number_vertices() const {
+        return number_vertices_;
     }
 
     const std::vector<int>& get_neighbors(int vertex) const {
-        return graph_.find(vertex)->second;
+        return graph_[vertex];
     }
 
     bool has_out_edges(int vertex) const {
-        return has_out_edges_.find(vertex) != has_out_edges_.end();
+        return has_out_edges_[vertex];
     }
 
+    int get_real_vertex(int vertex) const {
+        return orderable_vertices_[vertex];
+    }
 private:
     std::unordered_set<int> vertices_;
     std::vector<int> orderable_vertices_;
-    std::unordered_map<int, std::vector<int>> graph_;
-    std::unordered_set<int> has_out_edges_;
+    std::vector<std::vector<int>> graph_;
+    std::vector<bool> has_out_edges_;
+    std::unordered_map<int, int> mapped_to_;
+    int number_vertices_;
+
+    void sort_vertices_() {
+        std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+    }
+
+    void map_vertices_() {
+        for (int i = 0; i < number_vertices_; i++) {
+            mapped_to_[orderable_vertices_[i]] = i;
+        }
+    }
 };
 
 #endif
diff --git a/src/parse.h b/src/parse.h
index 31fa7c6..095232a 100644
--- a/src/parse.h
+++ b/src/parse.h
@@ -11,10 +11,10 @@ class Parser {
 public:
     Parser(std::string filename) : graph_(), input_file_(filename) {
         std::string edge;
-        while (std::getline(input_file_, edge)) {
-            parse_edge_(edge);
-        }
-        graph_.sort_vertices();
+        read_file_();
+        add_vertices_();
+        graph_.done_with_vertices();
+        add_edges_();
     }
 
     const Graph& get_graph() {
@@ -23,6 +23,14 @@ public:
 private:
     Graph graph_;
     std::ifstream input_file_;
+    std::vector<std::pair<int, int>> edges_;
+
+    void read_file_() {
+        std::string edge;
+        while (std::getline(input_file_, edge)) {
+            parse_edge_(edge);
+        }
+    }
 
     void parse_edge_(std::string edge) {
         std::stringstream sstream(edge);
@@ -30,7 +38,20 @@ private:
         int from, to;
         sstream >> from >> to;
 
-        graph_.add_edge(from, to);
+        edges_.push_back(std::pair<int, int>(from, to));
+    }
+
+    void add_vertices_() {
+        for (auto edge : edges_) {
+            graph_.add_vertex(edge.first);
+            graph_.add_vertex(edge.second);
+        }
+    }
+
+    void add_edges_() {
+        for (auto edge : edges_) {
+            graph_.add_edge(edge.first, edge.second);
+        }
     }
 };