-
Notifications
You must be signed in to change notification settings - Fork 10
/
louvain.hpp
210 lines (166 loc) · 9.8 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
#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"
#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);
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);
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);
#endif