blob: 2d81610c1215405c5d0c1517231d5062bb253b91 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <fstream>
#include <iostream>
#include <mutex>
#include <queue>
#include <string>
#include <thread>
#include "dependency_calculator.h"
#include "graph.h"
#include "parse.h"
int threads;
std::string input_file;
std::string output_file;
Graph graph;
std::vector<double> betweenness;
std::queue<int> vertices_to_process;
std::vector<std::thread> threads_list;
std::mutex queue_mutex;
std::mutex betweenness_mutex;
void parse_args(int argc, char *argv[]) {
if (argc < 4) {
std::cerr
<< "USAGE: ./brandes <number-threads> <input-file> <output-file>"
<< std::endl;
exit(1);
}
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 = 0; vertex < graph.get_number_vertices(); vertex++) {
betweenness.push_back(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 = 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 = 0; v < graph.get_number_vertices(); v++) {
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 = 0; vertex < graph.get_number_vertices(); vertex++) {
if (graph.has_out_edges(vertex)) {
fout << graph.get_real_vertex(vertex) << " "
<< betweenness[vertex] << std::endl;
}
}
}
int main(int argc, char *argv[]) {
parse_args(argc, argv);
parse_input();
init();
launch_threads();
join_threads();
print_betweenness();
return 0;
}
|