m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/src/brandes.cc
blob: 5060a9d9e5453f08f71b5697af3305acce69eea3 (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
#include <algorithm>
#include <fstream>
#include <iostream>
#include <thread>
#include <queue>
#include <mutex>

#include "parse.h"
#include "graph.h"
#include "dependency_calculator.h"

int threads;
std::string input_file;
std::string output_file;

Graph graph;
std::unordered_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;
        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 : 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();

    print_betweenness();

    return 0;
}