From 98844eccedfb84fac46c83d59a1298cce491f77b Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com>
Date: Thu, 5 Jan 2017 00:26:34 -0500
Subject: Switch to unordered maps and sets

---
 src/brandes.cc              |  2 +-
 src/dependency_calculator.h | 10 +++++-----
 src/graph.h                 |  9 ++++++---
 3 files changed, 12 insertions(+), 9 deletions(-)

(limited to 'src')

diff --git a/src/brandes.cc b/src/brandes.cc
index 776b263..5060a9d 100644
--- a/src/brandes.cc
+++ b/src/brandes.cc
@@ -14,7 +14,7 @@ std::string input_file;
 std::string output_file;
 
 Graph graph;
-std::map<int, double> betweenness;
+std::unordered_map<int, double> betweenness;
 std::queue<int> vertices_to_process;
 std::mutex queue_mutex;
 std::mutex betweenness_mutex;
diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h
index 1c77991..be6aeb7 100644
--- a/src/dependency_calculator.h
+++ b/src/dependency_calculator.h
@@ -4,7 +4,7 @@
 #include <stack>
 #include <queue>
 #include <vector>
-#include <map>
+#include <unordered_map>
 
 #include "graph.h"
 
@@ -24,11 +24,11 @@ private:
     const Graph &graph_; // (V, E)
     int vertex_; // s
     std::stack<int> stack_; // S
-    std::map<int, std::vector<int>> shortest_path_predecessors_; // P
-    std::map<int, int> shortest_paths_; // sigma
-    std::map<int, int> distance_; // d
+    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::queue<int> queue_; // Q
-    std::map<int, double> dependency_; // delta
+    std::unordered_map<int, double> dependency_; // delta
 
     void init_() {
         for (int vertex : graph_.get_vertices()) {
diff --git a/src/graph.h b/src/graph.h
index 7d0ae08..f687ff3 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -1,7 +1,9 @@
 #ifndef GRAPH_H
 #define GRAPH_H
 
-#include <map>
+#include <algorithm>
+#include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 class Graph {
@@ -33,10 +35,11 @@ public:
     bool has_out_edges(int vertex) const {
         return has_out_edges_.count(vertex) > 0;
     }
+
 private:
     std::set<int> vertices_;
-    std::map<int, std::vector<int>> graph_;
-    std::set<int> has_out_edges_;
+    std::unordered_map<int, std::vector<int>> graph_;
+    std::unordered_set<int> has_out_edges_;
 };
 
 #endif
-- 
cgit v1.2.3


From 1eae1a29340986fa5b8fca99bd797806891a511f Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com>
Date: Thu, 5 Jan 2017 12:31:48 -0500
Subject: Return vertices in a vector

---
 src/graph.h | 12 +++++++++---
 src/parse.h |  1 +
 2 files changed, 10 insertions(+), 3 deletions(-)

(limited to 'src')

diff --git a/src/graph.h b/src/graph.h
index f687ff3..47dce16 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -13,6 +13,7 @@ public:
     void add_vertex(int vertex) {
         if (vertices_.find(vertex) == vertices_.end()) {
             vertices_.insert(vertex);
+            orderable_vertices_.push_back(vertex);
             graph_[vertex] = std::vector<int>();
         }
     }
@@ -24,8 +25,12 @@ public:
         has_out_edges_.insert(from);
     }
 
-    const std::set<int> & get_vertices() const {
-        return vertices_;
+    void sort_vertices() {
+        std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+    }
+
+    const std::vector<int> & get_vertices() const {
+        return orderable_vertices_;
     }
 
     const std::vector<int> & get_neighbors(int vertex) const {
@@ -37,7 +42,8 @@ public:
     }
 
 private:
-    std::set<int> vertices_;
+    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_;
 };
diff --git a/src/parse.h b/src/parse.h
index cb6e3c6..1d37083 100644
--- a/src/parse.h
+++ b/src/parse.h
@@ -14,6 +14,7 @@ public:
         while (std::getline(input_file_, edge)) {
             parse_edge_(edge);
         }
+        graph_.sort_vertices();
     }
 
     const Graph & get_graph() {
-- 
cgit v1.2.3