-
Notifications
You must be signed in to change notification settings - Fork 0
/
louvain.hpp
executable file
·251 lines (202 loc) · 11.2 KB
/
louvain.hpp
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#ifndef __LOUVAIN_H
#define __LOUVAIN_H
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <mpi.h>
#include <omp.h>
#include "distgraph.hpp"
#include "coloring.hpp"
#ifdef RUNONGPU
// #include "louvain_cuda.cuh"
#include "GpuGraph.cuh"
using namespace CuVite;
#endif
#if defined(__CRAY_MIC_KNL) && defined(USE_AUTOHBW_MEMALLOC)
#include <hbw_allocator.h>
typedef std::vector<GraphElem, hbw::allocator<GraphElem> > CommunityVector;
typedef std::vector<GraphWeight, hbw::allocator<GraphWeight> > GraphWeightVector;
typedef std::vector<GraphElem, hbw::allocator<GraphElem> > GraphElemVector;
typedef std::unordered_map<GraphElem, GraphElem, std::hash<GraphElem>, std::equal_to<GraphElem>,
hbw::allocator< std::pair< const GraphElem, GraphElem > > > VertexCommMap;
typedef std::unordered_set<GraphElem, std::hash<GraphElem>, std::equal_to<GraphElem>,
hbw::allocator<GraphElem> > RemoteVertexList;
typedef std::vector<RemoteVertexList, hbw::allocator<RemoteVertexList> > PartnerArray;
typedef std::vector<Comm, hbw::allocator<Comm> > CommVector;
typedef std::map<GraphElem, Comm, std::less<GraphElem>,
hbw::allocator< std::pair< const GraphElem, Comm > > > CommMap;
typedef std::unordered_map<GraphElem, GraphElem, std::hash<GraphElem>, std::equal_to<GraphElem>,
hbw::allocator< std::pair< const GraphElem, GraphElem > > > ClusterLocalMap;
#else
typedef std::vector<GraphElem> CommunityVector;
typedef std::vector<GraphWeight> GraphWeightVector;
typedef std::vector<GraphElem> GraphElemVector;
typedef std::unordered_map<GraphElem, GraphElem> VertexCommMap;
typedef std::unordered_set<GraphElem> RemoteVertexList;
typedef std::vector<RemoteVertexList> PartnerArray;
typedef std::vector<Comm> CommVector;
typedef std::map<GraphElem, Comm> CommMap;
typedef std::unordered_map<GraphElem, GraphElem> ClusterLocalMap;
#endif
const int SizeTag = 1;
const int VertexTag = 2;
const int CommunityTag = 3;
const int CommunitySizeTag = 4;
const int CommunityDataTag = 5;
struct CommInfo {
GraphElem community;
GraphElem size;
GraphWeight degree;
};
// early termination cutoff for frozen
// vertices is 90%
#define ET_CUTOFF 90
// early termination cutoff for
// probabilistically freezing vertices
// is 20%
#define P_CUTOFF 0.02
typedef std::vector<CommInfo> CommInfoVector;
extern std::ofstream ofs;
static MPI_Datatype commType;
GraphWeight distLouvainMethod(const int me, const int nprocs, const DistGraph &dg,
size_t &ssz, size_t &rsz, std::vector<GraphElem> &ssizes,
std::vector<GraphElem> &rsizes, std::vector<GraphElem> &svdata,
std::vector<GraphElem> &rvdata, CommunityVector &cvect, const GraphWeight lower,
const GraphWeight thresh, int& iters);
#ifdef RUNONGPU
GraphWeight distLouvainMethod(const int me, const int nprocs, const DistGraph &dg,
size_t &ssz, size_t &rsz, std::vector<GraphElem> &ssizes,
std::vector<GraphElem> &rsizes, std::vector<GraphElem> &svdata,
std::vector<GraphElem> &rvdata, CommunityVector &cvect, const GraphWeight lower,
const GraphWeight thresh, int& iters, GpuGraph &gpu_graph);
#endif
GraphWeight distLouvainMethod(const int me, const int nprocs, const DistGraph &dg,
size_t &ssz, size_t &rsz, std::vector<GraphElem> &ssizes,
std::vector<GraphElem> &rsizes, std::vector<GraphElem> &svdata,
std::vector<GraphElem> &rvdata, CommunityVector &cvect, const GraphWeight lower,
const GraphWeight thresh, int& iters, bool ETLocalOrRemote);
GraphWeight distLouvainMethod(const int me, const int nprocs, const DistGraph &dg,
size_t &ssz, size_t &rsz, std::vector<GraphElem> &ssizes,
std::vector<GraphElem> &rsizes, std::vector<GraphElem> &svdata,
std::vector<GraphElem> &rvdata, CommunityVector &cvect, const GraphWeight lower,
const GraphWeight thresh, int& iters, GraphWeight ETDelta, bool ETLocalOrRemote);
GraphWeight distLouvainMethodWithColoring(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
CommunityVector &cvect, const GraphWeight lower, const GraphWeight thresh, int& iters);
GraphWeight distLouvainMethodWithColoring(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
CommunityVector &cvect, const GraphWeight lower, const GraphWeight thresh,
int& iters, bool ETLocalOrRemote);
GraphWeight distLouvainMethodWithColoring(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor,
size_t &ssz, size_t &rsz, std::vector<GraphElem> &ssizes,
std::vector<GraphElem> &rsizes, std::vector<GraphElem> &svdata,
std::vector<GraphElem> &rvdata, CommunityVector &cvect,
const GraphWeight lower, const GraphWeight thresh, int& iters, GraphWeight ETDelta,
bool ETLocalOrRemote);
GraphWeight distLouvainMethodVertexOrder(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
CommunityVector &cvect, const GraphWeight lower, const GraphWeight thresh, int& iters);
GraphWeight distLouvainMethodVertexOrder(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
CommunityVector &cvect, const GraphWeight lower, const GraphWeight thresh, int& iters,
bool ETLocalOrRemote);
GraphWeight distLouvainMethodVertexOrder(const int me, const int nprocs, const DistGraph &dg,
const long numColor, const ColorVector &vertexColor, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
CommunityVector &cvect, const GraphWeight lower, const GraphWeight thresh, int& iters,
GraphWeight ETDelta, bool ETLocalOrRemote);
static void distInitLouvain(const DistGraph &dg, CommunityVector &pastComm,
CommunityVector &currComm, GraphWeightVector &vDegree,
GraphWeightVector &clusterWeight, CommVector &localCinfo,
CommVector &localCupdate, GraphWeight &constantForSecondTerm,
const int me);
static void distExecuteLouvainIteration(const GraphElem i, const DistGraph &dg,
const CommunityVector &currComm, CommunityVector &targetComm,
const GraphWeightVector &vDegree, CommVector &localCinfo, CommVector &localCupdate,
const VertexCommMap &remoteComm, const CommMap &remoteCinfo, CommMap &remoteCupdate,
const GraphWeight constantForSecondTerm, GraphWeightVector &clusterWeight, const int me);
static void distSumVertexDegree(const Graph &g, GraphWeightVector &vDegree, CommVector &localCinfo);
static GraphWeight distCalcConstantForSecondTerm(const GraphWeightVector &vDegree);
static GraphElem distGetMaxIndex(const ClusterLocalMap &clmap, const GraphWeightVector &counter,
const GraphWeight selfLoop, const CommVector &localCinfo, const CommMap &remoteCinfo,
const GraphWeight vDegree, const GraphElem currSize, const GraphElem currDegree,
const GraphElem currComm, const GraphElem base, const GraphElem bound, const GraphWeight constant);
static GraphWeight distBuildLocalMapCounter(const GraphElem e0, const GraphElem e1,
ClusterLocalMap &clmap, GraphWeightVector &counter, const Graph &g, const CommunityVector &currComm,
const VertexCommMap &remoteComm, const GraphElem vertex, const GraphElem base, const GraphElem bound);
static GraphWeight distComputeModularity(const Graph &g, CommVector &localCinfo,
const GraphWeightVector &clusterWeight,
const GraphWeight constantForSecondTerm, const int me);
#ifdef RUNONGPU
static GraphWeight distComputeModularity(const Graph &g, CommVector &localCinfo,
const GraphWeightVector &clusterWeight,
const GraphWeight constantForSecondTerm, const int me, GpuGraph &gpu_graph);
#endif
static void distUpdateLocalCinfo(CommVector &localCinfo, const CommVector &localCupdate);
static void distCleanCWandCU(const GraphElem nv, GraphWeightVector &clusterWeight,
CommVector &localCupdate);
static void distInitComm(CommunityVector &pastComm, CommunityVector &currComm,
const GraphElem base);
static void updateRemoteCommunities(const DistGraph &dg, CommVector &localCinfo,
const CommMap &remoteCupdate,
const int me, const int nprocs);
static void fillRemoteCommunities(const DistGraph &dg, const int me,
const int nprocs, const size_t &ssz, const size_t &rsz,
const std::vector<GraphElem> &ssizes, const std::vector<GraphElem> &rsizes,
const std::vector<GraphElem> &svdata, const std::vector<GraphElem> &rvdata,
const CommunityVector &currComm, const CommVector &localCinfo,
CommMap &remoteCinfo, VertexCommMap &remoteComm, CommMap &remoteCupdate);
static void exchangeVertexReqs(const DistGraph &dg, size_t &ssz, size_t &rsz,
std::vector<GraphElem> &ssizes, std::vector<GraphElem> &rsizes,
std::vector<GraphElem> &svdata, std::vector<GraphElem> &rvdata,
const int me, const int nprocs);
void createCommunityMPIType();
void destroyCommunityMPIType();
// load ground truth file (vertex id --- community id) into a vector
// Ground Truth file is expected to be of the format generated
// by LFR-gen by Fortunato, et al.
// https://sites.google.com/site/santofortunato/inthepress2
void loadGroundTruthFile(std::vector<GraphElem>& commGroundTruth,
std::string const& groundTruthFileName,
bool isGroundTruthZeroBased = true);
// gather current community info to root
void gatherAllComm(int root, int me, int nprocs,
std::vector<GraphElem>& commAll,
const CommunityVector& localComm);
#ifdef RUNONGPU
// function to transfer data to GPU memory
int gpu_for_louvain_iteration(
const GraphElem nv, const DistGraph &dg,
CommunityVector &currComm,
CommunityVector &targetComm,
GraphWeightVector &vDegree,
CommVector &localCinfo,
CommVector &localCupdate,
VertexCommMap &remoteComm,
const CommMap &remoteCinfo,
CommMap &remoteCupdate,
const double constantForSecondTerm,
GraphWeightVector &clusterWeight,
int me, int numIters, GpuGraph &gpu_graph);
void gpu_reduce_mod(CommVector &localCinfo, const GraphWeightVector &clusterWeight,
GpuGraph &gpu_graph, GraphWeight le_la_xx[], const GraphElem nv);
void set_gpuDevices(int *me);
#endif
#endif