From 98844eccedfb84fac46c83d59a1298cce491f77b 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 | 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 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..f687ff3 100644 --- a/src/graph.h +++ b/src/graph.h @@ -1,7 +1,9 @@ #ifndef GRAPH_H #define GRAPH_H -#include +#include +#include +#include #include class Graph { @@ -33,10 +35,11 @@ public: bool has_out_edges(int vertex) const { return has_out_edges_.count(vertex) > 0; } + private: std::set vertices_; - std::map> graph_; - std::set has_out_edges_; + std::unordered_map> graph_; + std::unordered_set has_out_edges_; }; #endif -- cgit v1.2.3