From f0b144e5999441e5bf328991ef9fe2268d112687 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 4 Jan 2017 23:09:53 -0500 Subject: Implement concurrent Brandes's algorithm --- src/brandes.cc | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 92 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/brandes.cc b/src/brandes.cc index 809ccd4..776b263 100644 --- a/src/brandes.cc +++ b/src/brandes.cc @@ -1,24 +1,110 @@ +#include #include #include +#include +#include +#include #include "parse.h" #include "graph.h" +#include "dependency_calculator.h" -int main(int argc, char *argv[]) { +int threads; +std::string input_file; +std::string output_file; + +Graph graph; +std::map betweenness; +std::queue vertices_to_process; +std::mutex queue_mutex; +std::mutex betweenness_mutex; +std::vector threads_list; + +void parse_args(int argc, char *argv[]) { if (argc < 4) { std::cerr << "USAGE: ./brandes " << std::endl; - return 1; + exit(1); } - int threads = std::stoi(argv[1]); - std::string input_file = argv[2]; - std::string output_file = argv[3]; + threads = std::stoi(argv[1]); + input_file = argv[2]; + output_file = argv[3]; +} +void parse_input() { Parser parser(input_file); + graph = parser.get_graph(); +} + +void init() { + for (int vertex : graph.get_vertices()) { + betweenness[vertex] = 0; + vertices_to_process.push(vertex); + } +} + +int next_vertex() { + std::lock_guard lock(queue_mutex); + if (vertices_to_process.empty()) { + return -1; + } + int vertex; + vertex = vertices_to_process.front(); + vertices_to_process.pop(); + return vertex; +} + +void update_betweenness(int vertex, DependencyCalculator & dc) { + std::lock_guard lock(betweenness_mutex); + for (int v : graph.get_vertices()) { + if (v != vertex ) { + betweenness[v] += dc.get_dependency(v); + } + } +} + +void launch_threads() { + for (int i = 0; i < threads; i++) { + threads_list.emplace_back([&] () { + int vertex = next_vertex(); + while(vertex != -1) { + DependencyCalculator dc(graph, vertex); + update_betweenness(vertex, dc); + + vertex = next_vertex(); + } + }); + } +} + +void join_threads() { + for (std::thread& thread : threads_list) { + thread.join(); + } +} + +void print_betweenness() { + std::ofstream fout(output_file); + + for (int vertex : graph.get_vertices()) { + if (graph.has_out_edges(vertex)) { + fout << vertex << " " << betweenness[vertex] << std::endl; + } + } +} + +int main(int argc, char *argv[]) { + parse_args(argc, argv); + parse_input(); + + init(); + + launch_threads(); + join_threads(); - const Graph &graph = parser.get_graph(); + print_betweenness(); return 0; } -- cgit v1.2.3