-
Notifications
You must be signed in to change notification settings - Fork 2
/
Components.h
115 lines (105 loc) · 3.82 KB
/
Components.h
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
// This code is part of the project "Ligra: A Lightweight Graph Processing
// Framework for Shared Memory", presented at Principles and Practice of
// Parallel Programming, 2013.
// Copyright (c) 2013 Julian Shun and Guy Blelloch
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights (to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#include "Map.cpp"
template <class ET>
inline bool writeMin(ET *a, ET b) {
ET c; bool r=0;
do c = *a;
while (c > b && !(r=atomic_compare_and_swap(a,c,b)));
return r;
}
#define newA(__E,__n) (__E*) malloc((__n)*sizeof(__E))
struct CC_Shortcut {
uint32_t* IDs, *prevIDs;
CC_Shortcut( uint32_t* _IDs, uint32_t* _prevIDs) :
IDs(_IDs), prevIDs(_prevIDs) {}
inline bool operator () ( uint32_t i) {
uint32_t l = IDs[IDs[i]];
if(IDs[i] != l) IDs[i] = l;
if(prevIDs[i] != IDs[i]) {
prevIDs[i] = IDs[i];
return 1; }
else return 0;
}
};
struct CC_Vertex_F {
uint32_t* IDs, *prevIDs;
CC_Vertex_F(uint32_t* _IDs, uint32_t* _prevIDs) :
IDs(_IDs), prevIDs(_prevIDs) {}
inline bool operator () (uint32_t i) {
prevIDs[i] = IDs[i];
return 1; }};
struct CC_F {
uint32_t* IDs, *prevIDs;
CC_F( uint32_t* _IDs, uint32_t* _prevIDs) :
IDs(_IDs), prevIDs(_prevIDs) {}
inline bool update( uint32_t s, uint32_t d){ //Update function writes min ID
uint32_t origID = IDs[d];
if(IDs[s] < origID) {
IDs[d] = min(origID,IDs[s]);
if(origID == prevIDs[d]) return 1;
} return 0; }
inline bool updateAtomic ( uint32_t s, uint32_t d) { //atomic Update
uint32_t origID = IDs[d];
return (writeMin(&IDs[d],IDs[s]) && origID == prevIDs[d]);
}
inline bool cond ([[maybe_unused]] uint32_t d) { return true; } //does nothing
};
uint32_t *CC_shortcut(OFM &G) {
long n = G.get_n();
uint32_t* IDs = newA( uint32_t,n), *prevIDs = newA( uint32_t,n);
//initialize unique IDs
parallel_for(long i=0;i<n;i++) {
IDs[i] = i;
prevIDs[i] = i;
}
VertexSubset *Active = new VertexSubset(0, n, true); //initial frontier contains all vertices
while(Active->get_n() > 0){ //iterate until IDS converge
edgeMap(G, *Active, CC_F(IDs,prevIDs), false);
delete Active;
Active = new VertexSubset(0,n,true, true);
vertexMap(*Active,CC_Shortcut(IDs,prevIDs));
Active->move_next_to_current();
}
delete Active;
free(prevIDs);
return IDs;
}
uint32_t *CC(OFM &G) {
long n = G.get_n();
uint32_t* IDs = newA( uint32_t,n), *prevIDs = newA( uint32_t,n);
//initialize unique IDs
parallel_for(long i=0;i<n;i++) {
IDs[i] = i;
}
VertexSubset *Active = new VertexSubset(0, n, true, true); //initial frontier contains all vertices
while(Active->get_n() > 0){ //iterate until IDS converge
vertexMap(*Active,CC_Vertex_F(IDs,prevIDs), false);
edgeMap(G, *Active, CC_F(IDs,prevIDs));
Active->move_next_to_current();
}
delete Active;
free(prevIDs);
return IDs;
}