diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/brandes.cc | 18 | ||||
| -rw-r--r-- | src/dependency_calculator.h | 9 | ||||
| -rw-r--r-- | src/graph.h | 6 | ||||
| -rw-r--r-- | src/parse.h | 8 |
4 files changed, 22 insertions, 19 deletions
diff --git a/src/brandes.cc b/src/brandes.cc index 5060a9d..7d12ec6 100644 --- a/src/brandes.cc +++ b/src/brandes.cc @@ -1,13 +1,13 @@ -#include <algorithm> #include <fstream> #include <iostream> -#include <thread> -#include <queue> #include <mutex> +#include <queue> +#include <string> +#include <thread> -#include "parse.h" -#include "graph.h" #include "dependency_calculator.h" +#include "graph.h" +#include "parse.h" int threads; std::string input_file; @@ -16,9 +16,10 @@ std::string output_file; Graph graph; std::unordered_map<int, double> betweenness; std::queue<int> vertices_to_process; + +std::vector<std::thread> threads_list; std::mutex queue_mutex; std::mutex betweenness_mutex; -std::vector<std::thread> threads_list; void parse_args(int argc, char *argv[]) { if (argc < 4) { @@ -50,13 +51,12 @@ int next_vertex() { if (vertices_to_process.empty()) { return -1; } - int vertex; - vertex = vertices_to_process.front(); + int vertex = vertices_to_process.front(); vertices_to_process.pop(); return vertex; } -void update_betweenness(int vertex, DependencyCalculator & dc) { +void update_betweenness(int vertex, DependencyCalculator& dc) { std::lock_guard<std::mutex> lock(betweenness_mutex); for (int v : graph.get_vertices()) { if (v != vertex ) { diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h index be6aeb7..93a751e 100644 --- a/src/dependency_calculator.h +++ b/src/dependency_calculator.h @@ -1,16 +1,16 @@ #ifndef DEPENDENCY_CALCULATOR_H #define DEPENDENCY_CALCULATOR_H -#include <stack> #include <queue> -#include <vector> +#include <stack> #include <unordered_map> +#include <vector> #include "graph.h" class DependencyCalculator { public: - DependencyCalculator(const Graph &graph, int vertex) : graph_(graph), + DependencyCalculator(const Graph& graph, int vertex) : graph_(graph), vertex_(vertex) { init_(); find_shortest_paths_(); @@ -21,7 +21,7 @@ public: return dependency_.find(vertex)->second; } private: - const Graph &graph_; // (V, E) + const Graph& graph_; // (V, E) int vertex_; // s std::stack<int> stack_; // S std::unordered_map<int, std::vector<int>> shortest_path_predecessors_; // P @@ -67,6 +67,7 @@ private: while (!stack_.empty()) { int vertex = stack_.top(); stack_.pop(); + for (int predecessor : shortest_path_predecessors_[vertex]) { double shortest_path_ratio = (double) shortest_paths_[predecessor] / diff --git a/src/graph.h b/src/graph.h index 47dce16..317024e 100644 --- a/src/graph.h +++ b/src/graph.h @@ -29,16 +29,16 @@ public: std::sort(orderable_vertices_.begin(), orderable_vertices_.end()); } - const std::vector<int> & get_vertices() const { + const std::vector<int>& get_vertices() const { return orderable_vertices_; } - const std::vector<int> & get_neighbors(int vertex) const { + const std::vector<int>& get_neighbors(int vertex) const { return graph_.find(vertex)->second; } bool has_out_edges(int vertex) const { - return has_out_edges_.count(vertex) > 0; + return has_out_edges_.find(vertex) == has_out_edges_.end(); } private: diff --git a/src/parse.h b/src/parse.h index 1d37083..31fa7c6 100644 --- a/src/parse.h +++ b/src/parse.h @@ -2,9 +2,9 @@ #define PARSE_H #include <fstream> -#include <set> #include <sstream> #include <string> + #include "graph.h" class Parser { @@ -17,7 +17,7 @@ public: graph_.sort_vertices(); } - const Graph & get_graph() { + const Graph& get_graph() { return graph_; } private: @@ -25,9 +25,11 @@ private: std::ifstream input_file_; void parse_edge_(std::string edge) { - int from, to; std::stringstream sstream(edge); + + int from, to; sstream >> from >> to; + graph_.add_edge(from, to); } }; |