diff options
| -rw-r--r-- | src/brandes.cc | 12 | ||||
| -rw-r--r-- | src/dependency_calculator.h | 20 | ||||
| -rw-r--r-- | src/graph.h | 44 | ||||
| -rw-r--r-- | src/parse.h | 31 |
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); + } } }; |