m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-04 23:09:53 -0500
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-04 23:09:53 -0500
commitf0b144e5999441e5bf328991ef9fe2268d112687 (patch)
tree24d9c9c6cb00b42195fada1ade979debc2607c9a /src
parent6b7244cfc47c4106fe769b4191416b389838a133 (diff)
Implement concurrent Brandes's algorithm
Diffstat (limited to 'src')
-rw-r--r--src/brandes.cc98
1 files changed, 92 insertions, 6 deletions
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 <algorithm>
#include <fstream>
#include <iostream>
+#include <thread>
+#include <queue>
+#include <mutex>
#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<int, double> betweenness;
+std::queue<int> vertices_to_process;
+std::mutex queue_mutex;
+std::mutex betweenness_mutex;
+std::vector<std::thread> threads_list;
+
+void parse_args(int argc, char *argv[]) {
if (argc < 4) {
std::cerr
<< "USAGE: ./brandes <number-threads> <input-file> <output-file>"
<< 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<std::mutex> 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<std::mutex> 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;
}