Revision 162e1bda custompackages/graphparser/src/centrality.h
custompackages/graphparser/src/centrality.h  

1  1 
// 
2  2 
// Created by quynh on 12/15/15. 
3 
// The code is mainly from boost/graph/betweenness_centrality. 

4 
// I modified the code to work with Traffic Matrix. 

3  5 
// 
4  6  
5  7 
#ifndef GRAPH_PARSER_CENTRALITY_H 
6  8 
#define GRAPH_PARSER_CENTRALITY_H 
7  9  
8  10 
#include <fstream> 
11 
#include <iostream> 

9  12 
#include <boost/graph/betweenness_centrality.hpp> 
10  13 
#include "common.h" 
11  14  
12 
void simpleBetweennessCentrality(const Graph &g, string fileSuffix); 

13 
void writeBetweennessCentrality(const Graph &g, std::vector<double> v_centrality_vec, string fileSuffix); 

15 
namespace boost { 

16  
17 
namespace detail { namespace graph { 

18  
19 
template<typename Graph, typename TrafficMatrix, 

20 
typename VertexDescriptor> 

21 
int get_traffic_matrix_value(const Graph& g, 

22 
TrafficMatrix traffic_matrix, 

23 
VertexDescriptor v1, 

24 
VertexDescriptor v2) { 

25 
string name_1 = g[v1].id; 

26 
string name_2 = g[v2].id; 

27 
std::pair<std::string, std::string> p; 

28 
if (name_1.compare(name_2) <= 0) 

29 
{ 

30 
p = std::pair<std::string, std::string>(name_1, name_2); 

31 
} 

32 
else { 

33 
p = std::pair<std::string, std::string>(name_2, name_1); 

34 
} 

35  
36 
// TODO: how to return the default value 1 for traffic_matrix. 

37 
// If we are using std::map, then find() will be sufficient. 

38 
// But we are using the PropertyMap from boost... 

39 
// I don't think that there will be the case that p doesn't belong to traffic_matrix 

40 
// But it might result in a bug if p does not exist in traffic_matrix 

41 
int value = boost::get(traffic_matrix, p); 

42 
return value; 

43 
} 

44  
45 
template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 

46 
typename TrafficMatrix, 

47 
typename IncomingMap, typename DistanceMap, 

48 
typename DependencyMap, typename PathCountMap, 

49 
typename VertexIndexMap, typename ShortestPaths> 

50 
void 

51 
brandes_betweenness_centrality_heuristic_impl(const Graph& g, 

52 
TrafficMatrix traffic_matrix, 

53 
CentralityMap centrality, // C_B 

54 
EdgeCentralityMap edge_centrality_map, 

55 
IncomingMap incoming, // P 

56 
DistanceMap distance, // d 

57 
DependencyMap dependency, // delta 

58 
PathCountMap path_count, // sigma 

59 
VertexIndexMap vertex_index, 

60 
ShortestPaths shortest_paths) 

61 
{ 

62 
std::cout << "Heuristic Betweenness Centrality Implementation\n"; 

63  
64 
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; 

65 
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 

66  
67 
// Initialize centrality 

68 
init_centrality_map(vertices(g), centrality); 

69 
init_centrality_map(edges(g), edge_centrality_map); 

70  
71 
std::stack<vertex_descriptor> ordered_vertices; 

72 
vertex_iterator s, s_end; 

73 
for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) { 

74 
// Initialize for this iteration 

75 
vertex_iterator w, w_end; 

76 
for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w) { 

77 
incoming[*w].clear(); 

78 
put(path_count, *w, 0); 

79 
put(dependency, *w, 0); 

80 
} 

81 
put(path_count, *s, 1); 

82  
83 
// Execute the shortest paths algorithm. This will be either 

84 
// Dijkstra's algorithm or a customized breadthfirst search, 

85 
// depending on whether the graph is weighted or unweighted. 

86 
shortest_paths(g, *s, ordered_vertices, incoming, distance, 

87 
path_count, vertex_index); 

88  
89 
while (!ordered_vertices.empty()) { 

90 
vertex_descriptor w = ordered_vertices.top(); 

91 
ordered_vertices.pop(); 

92  
93 
typedef typename property_traits<IncomingMap>::value_type 

94 
incoming_type; 

95 
typedef typename incoming_type::iterator incoming_iterator; 

96 
typedef typename property_traits<DependencyMap>::value_type 

97 
dependency_type; 

98  
99 
// get communication intensity from traffic_matrix 

100 
// dependency_type communication_intensity = dependency_type(1); 

101 
dependency_type communication_intensity = get_traffic_matrix_value(g, traffic_matrix, w, *s); 

102 
put(dependency, w, communication_intensity + get(dependency, w)); 

103  
104 
dependency_type factor = dependency_type(get(dependency, w)) 

105 
/ dependency_type(get(path_count, w)); 

106  
107 
for (incoming_iterator vw = incoming[w].begin(); 

108 
vw != incoming[w].end(); ++vw) { 

109 
vertex_descriptor v = source(*vw, g); 

110  
111 
dependency_type new_dependency_value = get(dependency, v) + ( 

112 
dependency_type(get(path_count, v)) * factor); 

113 
put(dependency, v, new_dependency_value); 

114 
update_centrality(edge_centrality_map, *vw, factor); 

115 
} 

116  
117 
if (w != *s) { 

118 
update_centrality(centrality, w, get(dependency, w)); 

119 
} 

120 
} 

121 
} 

122  
123 
typedef typename graph_traits<Graph>::directed_category directed_category; 

124 
const bool is_undirected = 

125 
is_convertible<directed_category*, undirected_tag*>::value; 

126 
if (is_undirected) { 

127 
divide_centrality_by_two(vertices(g), centrality); 

128 
divide_centrality_by_two(edges(g), edge_centrality_map); 

129 
} 

130 
} 

131  
132  
133  
134 
} } // end of namespace detail::graph 

135  
136 
template<typename Graph, 

137 
typename TrafficMatrix, 

138 
typename CentralityMap, typename EdgeCentralityMap, 

139 
typename IncomingMap, typename DistanceMap, 

140 
typename DependencyMap, typename PathCountMap, 

141 
typename VertexIndexMap> 

142 
void 

143 
brandes_betweenness_centrality_heuristic(const Graph& g, 

144 
TrafficMatrix traffic_matrix, 

145 
CentralityMap centrality, // C_B 

146 
EdgeCentralityMap edge_centrality_map, 

147 
IncomingMap incoming, // P 

148 
DistanceMap distance, // d 

149 
DependencyMap dependency, // delta 

150 
PathCountMap path_count, // sigma 

151 
VertexIndexMap vertex_index 

152 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 

153 
{ 

154 
detail::graph::brandes_unweighted_shortest_paths shortest_paths; 

155  
156 
detail::graph::brandes_betweenness_centrality_heuristic_impl(g, 

157 
traffic_matrix, 

158 
centrality, 

159 
edge_centrality_map, 

160 
incoming, distance, 

161 
dependency, path_count, 

162 
vertex_index, 

163 
shortest_paths); 

164 
} 

165  
166 
template<typename Graph, 

167 
typename TrafficMatrix, 

168 
typename CentralityMap, typename EdgeCentralityMap, 

169 
typename IncomingMap, typename DistanceMap, 

170 
typename DependencyMap, typename PathCountMap, 

171 
typename VertexIndexMap, typename WeightMap> 

172 
void 

173 
brandes_betweenness_centrality_heuristic(const Graph& g, 

174 
TrafficMatrix traffic_matrix, 

175 
CentralityMap centrality, // C_B 

176 
EdgeCentralityMap edge_centrality_map, 

177 
IncomingMap incoming, // P 

178 
DistanceMap distance, // d 

179 
DependencyMap dependency, // delta 

180 
PathCountMap path_count, // sigma 

181 
VertexIndexMap vertex_index, 

182 
WeightMap weight_map 

183 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 

184 
{ 

185 
detail::graph::brandes_dijkstra_shortest_paths<WeightMap> 

186 
shortest_paths(weight_map); 

187  
188 
detail::graph::brandes_betweenness_centrality_heuristic_impl(g, 

189 
traffic_matrix, 

190 
centrality, 

191 
edge_centrality_map, 

192 
incoming, distance, 

193 
dependency, path_count, 

194 
vertex_index, 

195 
shortest_paths); 

196 
} 

197  
198 
namespace detail { namespace graph { 

199 
template<typename Graph, 

200 
typename TrafficMatrix, 

201 
typename CentralityMap, typename EdgeCentralityMap, 

202 
typename WeightMap, typename VertexIndexMap> 

203 
void 

204 
brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g, 

205 
TrafficMatrix traffic_matrix, 

206 
CentralityMap centrality, 

207 
EdgeCentralityMap edge_centrality_map, 

208 
WeightMap weight_map, 

209 
VertexIndexMap vertex_index) 

210 
{ 

211 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type; 

212 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; 

213 
typedef typename mpl::if_c<(is_same<CentralityMap, 

214 
dummy_property_map>::value), 

215 
EdgeCentralityMap, 

216 
CentralityMap>::type a_centrality_map; 

217 
typedef typename property_traits<a_centrality_map>::value_type 

218 
centrality_type; 

219  
220 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 

221  
222 
std::vector<std::vector<edge_descriptor> > incoming(V); 

223 
std::vector<centrality_type> distance(V); 

224 
std::vector<centrality_type> dependency(V); 

225 
std::vector<degree_size_type> path_count(V); 

226  
227 
brandes_betweenness_centrality_heuristic( 

228 
g, 

229 
traffic_matrix, 

230 
centrality, edge_centrality_map, 

231 
make_iterator_property_map(incoming.begin(), vertex_index), 

232 
make_iterator_property_map(distance.begin(), vertex_index), 

233 
make_iterator_property_map(dependency.begin(), vertex_index), 

234 
make_iterator_property_map(path_count.begin(), vertex_index), 

235 
vertex_index, 

236 
weight_map); 

237 
} 

238  
239  
240 
template<typename Graph, 

241 
typename TrafficMatrix, 

242 
typename CentralityMap, typename EdgeCentralityMap, 

243 
typename VertexIndexMap> 

244 
void 

245 
brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g, 

246 
TrafficMatrix traffic_matrix, 

247 
CentralityMap centrality, 

248 
EdgeCentralityMap edge_centrality_map, 

249 
VertexIndexMap vertex_index) 

250 
{ 

251 
typedef typename graph_traits<Graph>::degree_size_type degree_size_type; 

252 
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; 

253 
typedef typename mpl::if_c<(is_same<CentralityMap, 

254 
dummy_property_map>::value), 

255 
EdgeCentralityMap, 

256 
CentralityMap>::type a_centrality_map; 

257 
typedef typename property_traits<a_centrality_map>::value_type 

258 
centrality_type; 

259  
260 
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g); 

261  
262 
std::vector<std::vector<edge_descriptor> > incoming(V); 

263 
std::vector<centrality_type> distance(V); 

264 
std::vector<centrality_type> dependency(V); 

265 
std::vector<degree_size_type> path_count(V); 

266  
267 
brandes_betweenness_centrality_heuristic( 

268 
g, 

269 
traffic_matrix, 

270 
centrality, edge_centrality_map, 

271 
make_iterator_property_map(incoming.begin(), vertex_index), 

272 
make_iterator_property_map(distance.begin(), vertex_index), 

273 
make_iterator_property_map(dependency.begin(), vertex_index), 

274 
make_iterator_property_map(path_count.begin(), vertex_index), 

275 
vertex_index); 

276 
} 

277  
278 
template<typename WeightMap> 

279 
struct brandes_betweenness_centrality_heuristic_dispatch1 

280 
{ 

281 
template<typename Graph, 

282 
typename TrafficMatrix, 

283 
typename CentralityMap, 

284 
typename EdgeCentralityMap, typename VertexIndexMap> 

285 
static void 

286 
run(const Graph& g, 

287 
TrafficMatrix traffic_matrix, 

288 
CentralityMap centrality, 

289 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 

290 
WeightMap weight_map) 

291 
{ 

292 
brandes_betweenness_centrality_heuristic_dispatch2(g, 

293 
traffic_matrix, 

294 
centrality, edge_centrality_map, 

295 
weight_map, vertex_index); 

296 
} 

297 
}; 

298  
299 
template<> 

300 
struct brandes_betweenness_centrality_heuristic_dispatch1<param_not_found> 

301 
{ 

302 
template<typename Graph, 

303 
typename TrafficMatrix, 

304 
typename CentralityMap, 

305 
typename EdgeCentralityMap, typename VertexIndexMap> 

306 
static void 

307 
run(const Graph& g, 

308 
TrafficMatrix traffic_matrix, 

309 
CentralityMap centrality, 

310 
EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index, 

311 
param_not_found) 

312 
{ 

313 
brandes_betweenness_centrality_heuristic_dispatch2(g, 

314 
traffic_matrix, 

315 
centrality, edge_centrality_map, 

316 
vertex_index); 

317 
} 

318 
}; 

319  
320 
} } // end namespace detail::graph 

321  
322 
template<typename Graph, typename TrafficMatrix, typename Param, typename Tag, typename Rest> 

323 
void 

324 
brandes_betweenness_centrality_heuristic(const Graph& g, 

325 
TrafficMatrix traffic_matrix, 

326 
const bgl_named_params<Param,Tag,Rest>& params 

327 
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag)) 

328 
{ 

329 
typedef bgl_named_params<Param,Tag,Rest> named_params; 

330  
331 
typedef typename get_param_type<edge_weight_t, named_params>::type ew; 

332 
detail::graph::brandes_betweenness_centrality_heuristic_dispatch1<ew>::run( 

333 
g, 

334 
traffic_matrix, 

335 
choose_param(get_param(params, vertex_centrality), 

336 
dummy_property_map()), 

337 
choose_param(get_param(params, edge_centrality), 

338 
dummy_property_map()), 

339 
choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 

340 
get_param(params, edge_weight)); 

341 
} 

342  
343 
} // end namespace boost 

14  344  
15  345 
#endif //GRAPH_PARSER_CENTRALITY_H 
Also available in: Unified diff