Parallel-Connected-Components/par-scc-v2.cpp at main · Random-Bee/Parallel-Connected-Components · GitHub

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
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

int N, M;
vector<vector<int>> adj;

atomic<int>* comps;

int num_t;

atomic<int> comp(0);

void scc(int tid) {
    int i;
    int start = tid*(N/num_t), end = (tid == num_t-1) ? N : (tid+1)*(N/num_t);

    int expected = -1;
    for(i=start; i<end; i++) {
        int curr = atomic_fetch_add(&comp, 1);
        int expected = 1e9;
        if(atomic_compare_exchange_strong(&comps[i], &expected, curr)) {
            queue<int> q;
            q.push(i);
            bool smaller_cid = false;
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(auto v: adj[u]) {
                    expected = 1e9;
                    while(1) {
                        bool fl = atomic_compare_exchange_strong(&comps[v], &expected, curr);
                        if(fl) {
                            q.push(v);
                            break;
                        }
                        else {
                            if(comps[v] < curr) {
                                smaller_cid = true;
                                break;
                            }
                            else if(comps[v] == curr) {
                                break;
                            }
                            else {
                                expected = comps[v];
                            }
                        }
                    }
                    if(smaller_cid) break;
                }
            }
        }
    }
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int i, j;

    FILE* f_in = fopen(argv[1], "r");

    fscanf(f_in, "%d %d", &N, &M);

    adj.resize(N);

    for(i=0; i<M; i++) {
        int x, y;
        fscanf(f_in, "%d %d", &x, &y);
        // x--; y--; /////////////////////////////////////////////
        if(x>=N || y>=N) continue;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    fclose(f_in);

    cin >> num_t;

    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    comps = new atomic<int>[N];

    for(i=0; i<N; i++) comps[i] = 1e9;

    vector<thread> th;
    for(i=0; i<num_t; i++) {
        th.push_back(thread(scc, i));
    }

    for(i=0; i<num_t; i++) {
        th[i].join();
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(t2 - t1).count();

    FILE* f_out = fopen("par2-out.txt", "w");

    int num_c = 0;
    for(i=0; i<N; i++) {
        fprintf(f_out, "%d\n", comps[i].load());
        num_c = max(num_c, comps[i].load()+1);
    }
    fprintf(f_out, "\n");
    fprintf(f_out, "%d\n", num_c);

    fclose(f_out);

    cout << duration << "\n";

    return 0;
}