m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-05 00:26:34 -0500
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-05 00:26:34 -0500
commit69be31ac880aa558f0cfe1313a999d85278e03f1 (patch)
tree52915227ac71416ba0e2eb7fe8a41bd9bea6d71b
parent02d18af55aaf50b57b3a57891dac74a9b1a36b60 (diff)
Switch to unordered maps and sets
-rw-r--r--src/brandes.cc2
-rw-r--r--src/dependency_calculator.h10
-rw-r--r--src/graph.h11
3 files changed, 12 insertions, 11 deletions
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..0f4d7ee 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -1,7 +1,8 @@
#ifndef GRAPH_H
#define GRAPH_H
-#include <map>
+#include <unordered_map>
+#include <unordered_set>
#include <vector>
class Graph {
@@ -22,7 +23,7 @@ public:
has_out_edges_.insert(from);
}
- const std::set<int> & get_vertices() const {
+ const std::unordered_set<int> & get_vertices() const {
return vertices_;
}
@@ -34,9 +35,9 @@ public:
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_set<int> vertices_;
+ std::unordered_map<int, std::vector<int>> graph_;
+ std::unordered_set<int> has_out_edges_;
};
#endif