From 69be31ac880aa558f0cfe1313a999d85278e03f1 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski 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 | 11 ++++++----- 3 files changed, 12 insertions(+), 11 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 betweenness; +std::unordered_map betweenness; std::queue 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 #include #include -#include +#include #include "graph.h" @@ -24,11 +24,11 @@ private: const Graph &graph_; // (V, E) int vertex_; // s std::stack stack_; // S - std::map> shortest_path_predecessors_; // P - std::map shortest_paths_; // sigma - std::map distance_; // d + std::unordered_map> shortest_path_predecessors_; // P + std::unordered_map shortest_paths_; // sigma + std::unordered_map distance_; // d std::queue queue_; // Q - std::map dependency_; // delta + std::unordered_map 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 +#include +#include #include class Graph { @@ -22,7 +23,7 @@ public: has_out_edges_.insert(from); } - const std::set & get_vertices() const { + const std::unordered_set & get_vertices() const { return vertices_; } @@ -34,9 +35,9 @@ public: return has_out_edges_.count(vertex) > 0; } private: - std::set vertices_; - std::map> graph_; - std::set has_out_edges_; + std::unordered_set vertices_; + std::unordered_map> graph_; + std::unordered_set has_out_edges_; }; #endif -- cgit v1.2.3