Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / centrality.h @ d5b7a27f

History | View | Annotate | Download (26.9 KB)

1
//
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.
5
//
6

    
7
#ifndef GRAPH_PARSER_CENTRALITY_H
8
#define GRAPH_PARSER_CENTRALITY_H
9

    
10
#include <fstream>
11
#include <iostream>
12
#include <boost/graph/betweenness_centrality.hpp>
13
#include "common.h"
14

    
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
} } // end of namespace detail::graph
132

    
133
template<typename Graph,
134
         typename TrafficMatrix,
135
         typename CentralityMap, typename EdgeCentralityMap,
136
         typename IncomingMap, typename DistanceMap,
137
         typename DependencyMap, typename PathCountMap,
138
         typename VertexIndexMap>
139
void
140
brandes_betweenness_centrality_heuristic(const Graph& g,
141
                               TrafficMatrix traffic_matrix,
142
                               CentralityMap centrality,     // C_B
143
                               EdgeCentralityMap edge_centrality_map,
144
                               IncomingMap incoming, // P
145
                               DistanceMap distance,         // d
146
                               DependencyMap dependency,     // delta
147
                               PathCountMap path_count,      // sigma
148
                               VertexIndexMap vertex_index
149
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
150
{
151
  detail::graph::brandes_unweighted_shortest_paths shortest_paths;
152

    
153
  detail::graph::brandes_betweenness_centrality_heuristic_impl(g,
154
                                                     traffic_matrix,
155
                                                     centrality,
156
                                                     edge_centrality_map,
157
                                                     incoming, distance,
158
                                                     dependency, path_count,
159
                                                     vertex_index,
160
                                                     shortest_paths);
161
}
162

    
163
template<typename Graph,
164
         typename TrafficMatrix,
165
         typename CentralityMap, typename EdgeCentralityMap,
166
         typename IncomingMap, typename DistanceMap,
167
         typename DependencyMap, typename PathCountMap,
168
         typename VertexIndexMap, typename WeightMap>
169
void
170
brandes_betweenness_centrality_heuristic(const Graph& g,
171
                               TrafficMatrix traffic_matrix,
172
                               CentralityMap centrality,     // C_B
173
                               EdgeCentralityMap edge_centrality_map,
174
                               IncomingMap incoming, // P
175
                               DistanceMap distance,         // d
176
                               DependencyMap dependency,     // delta
177
                               PathCountMap path_count,      // sigma
178
                               VertexIndexMap vertex_index,
179
                               WeightMap weight_map
180
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
181
{
182
  detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
183
    shortest_paths(weight_map);
184

    
185
  detail::graph::brandes_betweenness_centrality_heuristic_impl(g,
186
                                                     traffic_matrix,
187
                                                     centrality,
188
                                                     edge_centrality_map,
189
                                                     incoming, distance,
190
                                                     dependency, path_count,
191
                                                     vertex_index,
192
                                                     shortest_paths);
193
}
194

    
195
namespace detail { namespace graph {
196
  template<typename Graph,
197
           typename TrafficMatrix,
198
           typename CentralityMap, typename EdgeCentralityMap,
199
           typename WeightMap, typename VertexIndexMap>
200
  void
201
  brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
202
                                           TrafficMatrix traffic_matrix,
203
                                           CentralityMap centrality,
204
                                           EdgeCentralityMap edge_centrality_map,
205
                                           WeightMap weight_map,
206
                                           VertexIndexMap vertex_index)
207
  {
208
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
209
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
210
    typedef typename mpl::if_c<(is_same<CentralityMap,
211
                                        dummy_property_map>::value),
212
                                         EdgeCentralityMap,
213
                               CentralityMap>::type a_centrality_map;
214
    typedef typename property_traits<a_centrality_map>::value_type
215
      centrality_type;
216

    
217
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
218

    
219
    std::vector<std::vector<edge_descriptor> > incoming(V);
220
    std::vector<centrality_type> distance(V);
221
    std::vector<centrality_type> dependency(V);
222
    std::vector<degree_size_type> path_count(V);
223

    
224
    brandes_betweenness_centrality_heuristic(
225
      g,
226
      traffic_matrix,
227
      centrality, edge_centrality_map,
228
      make_iterator_property_map(incoming.begin(), vertex_index),
229
      make_iterator_property_map(distance.begin(), vertex_index),
230
      make_iterator_property_map(dependency.begin(), vertex_index),
231
      make_iterator_property_map(path_count.begin(), vertex_index),
232
      vertex_index,
233
      weight_map);
234
  }
235

    
236

    
237
  template<typename Graph,
238
           typename TrafficMatrix,
239
           typename CentralityMap, typename EdgeCentralityMap,
240
           typename VertexIndexMap>
241
  void
242
  brandes_betweenness_centrality_heuristic_dispatch2(const Graph& g,
243
                                           TrafficMatrix traffic_matrix,
244
                                           CentralityMap centrality,
245
                                           EdgeCentralityMap edge_centrality_map,
246
                                           VertexIndexMap vertex_index)
247
  {
248
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
249
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
250
    typedef typename mpl::if_c<(is_same<CentralityMap,
251
                                        dummy_property_map>::value),
252
                                         EdgeCentralityMap,
253
                               CentralityMap>::type a_centrality_map;
254
    typedef typename property_traits<a_centrality_map>::value_type
255
      centrality_type;
256

    
257
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
258

    
259
    std::vector<std::vector<edge_descriptor> > incoming(V);
260
    std::vector<centrality_type> distance(V);
261
    std::vector<centrality_type> dependency(V);
262
    std::vector<degree_size_type> path_count(V);
263

    
264
    brandes_betweenness_centrality_heuristic(
265
      g,
266
      traffic_matrix,
267
      centrality, edge_centrality_map,
268
      make_iterator_property_map(incoming.begin(), vertex_index),
269
      make_iterator_property_map(distance.begin(), vertex_index),
270
      make_iterator_property_map(dependency.begin(), vertex_index),
271
      make_iterator_property_map(path_count.begin(), vertex_index),
272
      vertex_index);
273
  }
274

    
275
  template<typename WeightMap>
276
  struct brandes_betweenness_centrality_heuristic_dispatch1
277
  {
278
    template<typename Graph,
279
             typename TrafficMatrix,
280
             typename CentralityMap,
281
             typename EdgeCentralityMap, typename VertexIndexMap>
282
    static void
283
    run(const Graph& g,
284
        TrafficMatrix traffic_matrix,
285
        CentralityMap centrality,
286
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
287
        WeightMap weight_map)
288
    {
289
      brandes_betweenness_centrality_heuristic_dispatch2(g,
290
                                               traffic_matrix,
291
                                               centrality, edge_centrality_map,
292
                                               weight_map, vertex_index);
293
    }
294
  };
295

    
296
  template<>
297
  struct brandes_betweenness_centrality_heuristic_dispatch1<param_not_found>
298
  {
299
    template<typename Graph,
300
             typename TrafficMatrix,
301
             typename CentralityMap,
302
             typename EdgeCentralityMap, typename VertexIndexMap>
303
    static void
304
    run(const Graph& g,
305
        TrafficMatrix traffic_matrix,
306
        CentralityMap centrality,
307
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
308
        param_not_found)
309
    {
310
      brandes_betweenness_centrality_heuristic_dispatch2(g,
311
                                               traffic_matrix,
312
                                               centrality, edge_centrality_map,
313
                                               vertex_index);
314
    }
315
  };
316

    
317
} } // end namespace detail::graph
318

    
319
template<typename Graph, typename TrafficMatrix, typename Param, typename Tag, typename Rest>
320
void
321
brandes_betweenness_centrality_heuristic(const Graph& g,
322
                               TrafficMatrix traffic_matrix,
323
                               const bgl_named_params<Param,Tag,Rest>& params
324
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
325
{
326
  typedef bgl_named_params<Param,Tag,Rest> named_params;
327

    
328
  typedef typename get_param_type<edge_weight_t, named_params>::type ew;
329
  detail::graph::brandes_betweenness_centrality_heuristic_dispatch1<ew>::run(
330
    g,
331
    traffic_matrix,
332
    choose_param(get_param(params, vertex_centrality),
333
                 dummy_property_map()),
334
    choose_param(get_param(params, edge_centrality),
335
                 dummy_property_map()),
336
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
337
    get_param(params, edge_weight));
338
}
339

    
340
//////////////////////////////////////
341
// BGL Modification: TARGETS INCLUSION
342
//////////////////////////////////////
343

    
344
namespace detail { namespace graph {
345
  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
346
         typename IncomingMap, typename DistanceMap,
347
         typename DependencyMap, typename PathCountMap,
348
         typename VertexIndexMap, typename ShortestPaths>
349

    
350
  void
351
  brandes_betweenness_centrality_targets_inclusion_impl(const Graph& g,
352
                                        bool targets_inclusion,
353
                                        CentralityMap centrality,     // C_B
354
                                        EdgeCentralityMap edge_centrality_map,
355
                                        IncomingMap incoming, // P
356
                                        DistanceMap distance,         // d
357
                                        DependencyMap dependency,     // delta
358
                                        PathCountMap path_count,      // sigma
359
                                        VertexIndexMap vertex_index,
360
                                        ShortestPaths shortest_paths)
361
  {
362
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
363
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
364

    
365
    cout << "@@@ Targets Inclusion @@@\n";
366

    
367
    // Initialize centrality
368
    init_centrality_map(vertices(g), centrality);
369
    init_centrality_map(edges(g), edge_centrality_map);
370

    
371
    std::stack<vertex_descriptor> ordered_vertices;
372
    vertex_iterator s, s_end;
373
    for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s) {
374
      // Initialize for this iteration
375
      vertex_iterator w, w_end;
376
      for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w) {
377
        incoming[*w].clear();
378
        put(path_count, *w, 0);
379
        put(dependency, *w, 0);
380
      }
381
      put(path_count, *s, 1);
382

    
383
      // Execute the shortest paths algorithm. This will be either
384
      // Dijkstra's algorithm or a customized breadth-first search,
385
      // depending on whether the graph is weighted or unweighted.
386
      shortest_paths(g, *s, ordered_vertices, incoming, distance,
387
                     path_count, vertex_index);
388

    
389
      while (!ordered_vertices.empty()) {
390
        vertex_descriptor w = ordered_vertices.top();
391
        ordered_vertices.pop();
392

    
393
        typedef typename property_traits<IncomingMap>::value_type
394
          incoming_type;
395
        typedef typename incoming_type::iterator incoming_iterator;
396
        typedef typename property_traits<DependencyMap>::value_type
397
          dependency_type;
398

    
399
        for (incoming_iterator vw = incoming[w].begin();
400
             vw != incoming[w].end(); ++vw) {
401
          vertex_descriptor v = source(*vw, g);
402
          dependency_type factor = dependency_type(get(path_count, v))
403
            / dependency_type(get(path_count, w));
404
          factor *= (dependency_type(1) + get(dependency, w));
405
          put(dependency, v, get(dependency, v) + factor);
406
          update_centrality(edge_centrality_map, *vw, factor);
407
        }
408

    
409
        if (w != *s) {
410
          if (targets_inclusion) {
411
            update_centrality(centrality, w, get(dependency, w) + dependency_type(1));
412
          }
413
          else {
414
            update_centrality(centrality, w, get(dependency, w));
415
          }
416
        }
417
      }
418
    }
419

    
420
    typedef typename graph_traits<Graph>::directed_category directed_category;
421
    const bool is_undirected =
422
      is_convertible<directed_category*, undirected_tag*>::value;
423
    if (is_undirected) {
424
      divide_centrality_by_two(vertices(g), centrality);
425
      divide_centrality_by_two(edges(g), edge_centrality_map);
426
    }
427
  }
428

    
429
} } // end namespace detail::graph
430

    
431
template<typename Graph,
432
         typename CentralityMap, typename EdgeCentralityMap,
433
         typename IncomingMap, typename DistanceMap,
434
         typename DependencyMap, typename PathCountMap,
435
         typename VertexIndexMap>
436
void
437
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
438
                               bool targets_inclusion,
439
                               CentralityMap centrality,     // C_B
440
                               EdgeCentralityMap edge_centrality_map,
441
                               IncomingMap incoming, // P
442
                               DistanceMap distance,         // d
443
                               DependencyMap dependency,     // delta
444
                               PathCountMap path_count,      // sigma
445
                               VertexIndexMap vertex_index
446
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
447
{
448
  detail::graph::brandes_unweighted_shortest_paths shortest_paths;
449

    
450
  detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g,
451
                                                     targets_inclusion,
452
                                                     centrality,
453
                                                     edge_centrality_map,
454
                                                     incoming, distance,
455
                                                     dependency, path_count,
456
                                                     vertex_index,
457
                                                     shortest_paths);
458
}
459

    
460
template<typename Graph,
461
         typename CentralityMap, typename EdgeCentralityMap,
462
         typename IncomingMap, typename DistanceMap,
463
         typename DependencyMap, typename PathCountMap,
464
         typename VertexIndexMap, typename WeightMap>
465
void
466
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
467
                               bool targets_inclusion,
468
                               CentralityMap centrality,     // C_B
469
                               EdgeCentralityMap edge_centrality_map,
470
                               IncomingMap incoming, // P
471
                               DistanceMap distance,         // d
472
                               DependencyMap dependency,     // delta
473
                               PathCountMap path_count,      // sigma
474
                               VertexIndexMap vertex_index,
475
                               WeightMap weight_map
476
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
477
{
478
  detail::graph::brandes_dijkstra_shortest_paths<WeightMap>
479
    shortest_paths(weight_map);
480

    
481
  detail::graph::brandes_betweenness_centrality_targets_inclusion_impl(g,
482
                                                     targets_inclusion,
483
                                                     centrality,
484
                                                     edge_centrality_map,
485
                                                     incoming, distance,
486
                                                     dependency, path_count,
487
                                                     vertex_index,
488
                                                     shortest_paths);
489
}
490

    
491
namespace detail { namespace graph {
492
  template<typename Graph,
493
           typename CentralityMap, typename EdgeCentralityMap,
494
           typename WeightMap, typename VertexIndexMap>
495
  void
496
  brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,
497
                                           bool targets_inclusion,
498
                                           CentralityMap centrality,
499
                                           EdgeCentralityMap edge_centrality_map,
500
                                           WeightMap weight_map,
501
                                           VertexIndexMap vertex_index)
502
  {
503
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
504
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
505
    typedef typename mpl::if_c<(is_same<CentralityMap,
506
                                        dummy_property_map>::value),
507
                                         EdgeCentralityMap,
508
                               CentralityMap>::type a_centrality_map;
509
    typedef typename property_traits<a_centrality_map>::value_type
510
      centrality_type;
511

    
512
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
513

    
514
    std::vector<std::vector<edge_descriptor> > incoming(V);
515
    std::vector<centrality_type> distance(V);
516
    std::vector<centrality_type> dependency(V);
517
    std::vector<degree_size_type> path_count(V);
518

    
519
    brandes_betweenness_centrality_targets_inclusion(
520
      g,
521
      targets_inclusion,
522
      centrality, edge_centrality_map,
523
      make_iterator_property_map(incoming.begin(), vertex_index),
524
      make_iterator_property_map(distance.begin(), vertex_index),
525
      make_iterator_property_map(dependency.begin(), vertex_index),
526
      make_iterator_property_map(path_count.begin(), vertex_index),
527
      vertex_index,
528
      weight_map);
529
  }
530

    
531

    
532
  template<typename Graph,
533
           typename CentralityMap, typename EdgeCentralityMap,
534
           typename VertexIndexMap>
535
  void
536
  brandes_betweenness_centrality_targets_inclusion_dispatch2(const Graph& g,
537
                                           bool targets_inclusion,
538
                                           CentralityMap centrality,
539
                                           EdgeCentralityMap edge_centrality_map,
540
                                           VertexIndexMap vertex_index)
541
  {
542
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
543
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
544
    typedef typename mpl::if_c<(is_same<CentralityMap,
545
                                        dummy_property_map>::value),
546
                                         EdgeCentralityMap,
547
                               CentralityMap>::type a_centrality_map;
548
    typedef typename property_traits<a_centrality_map>::value_type
549
      centrality_type;
550

    
551
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
552

    
553
    std::vector<std::vector<edge_descriptor> > incoming(V);
554
    std::vector<centrality_type> distance(V);
555
    std::vector<centrality_type> dependency(V);
556
    std::vector<degree_size_type> path_count(V);
557

    
558
    brandes_betweenness_centrality_targets_inclusion(
559
      g,
560
      targets_inclusion,
561
      centrality, edge_centrality_map,
562
      make_iterator_property_map(incoming.begin(), vertex_index),
563
      make_iterator_property_map(distance.begin(), vertex_index),
564
      make_iterator_property_map(dependency.begin(), vertex_index),
565
      make_iterator_property_map(path_count.begin(), vertex_index),
566
      vertex_index);
567
  }
568

    
569
  template<typename WeightMap>
570
  struct brandes_betweenness_centrality_targets_inclusion_dispatch1
571
  {
572
    template<typename Graph,
573
             typename CentralityMap,
574
             typename EdgeCentralityMap, typename VertexIndexMap>
575
    static void
576
    run(const Graph& g,
577
        bool targets_inclusion,
578
        CentralityMap centrality,
579
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
580
        WeightMap weight_map)
581
    {
582
      brandes_betweenness_centrality_targets_inclusion_dispatch2(g,
583
                                               targets_inclusion,
584
                                               centrality, edge_centrality_map,
585
                                               weight_map, vertex_index);
586
    }
587
  };
588

    
589
  template<>
590
  struct brandes_betweenness_centrality_targets_inclusion_dispatch1<param_not_found>
591
  {
592
    template<typename Graph,
593
             typename CentralityMap,
594
             typename EdgeCentralityMap, typename VertexIndexMap>
595
    static void
596
    run(const Graph& g,
597
        bool targets_inclusion,
598
        CentralityMap centrality,
599
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
600
        param_not_found)
601
    {
602
      brandes_betweenness_centrality_targets_inclusion_dispatch2(g,
603
                                               targets_inclusion,
604
                                               centrality, edge_centrality_map,
605
                                               vertex_index);
606
    }
607
  };
608

    
609
} } // end namespace detail::graph
610

    
611
template<typename Graph, typename Param, typename Tag, typename Rest>
612
void
613
brandes_betweenness_centrality_targets_inclusion(const Graph& g,
614
                               bool targets_inclusion,
615
                               const bgl_named_params<Param,Tag,Rest>& params
616
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
617
{
618
  typedef bgl_named_params<Param,Tag,Rest> named_params;
619

    
620
  typedef typename get_param_type<edge_weight_t, named_params>::type ew;
621
  detail::graph::brandes_betweenness_centrality_targets_inclusion_dispatch1<ew>::run(
622
    g,
623
    targets_inclusion,
624
    choose_param(get_param(params, vertex_centrality),
625
                 dummy_property_map()),
626
    choose_param(get_param(params, edge_centrality),
627
                 dummy_property_map()),
628
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
629
    get_param(params, edge_weight));
630
}
631

    
632
} // end namespace boost
633

    
634

    
635
#endif //GRAPH_PARSER_CENTRALITY_H