Revision 162e1bda custompackages/graph-parser/src/centrality.h

View differences:

custompackages/graph-parser/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 breadth-first 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