Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / centrality.h @ 33e5ad95

History | View | Annotate | Download (27.2 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); // denoted as h in the paper
102
        put(dependency, w, communication_intensity + get(dependency, w));
103

    
104
        update_centrality(centrality, *s, communication_intensity); // the number of times s is a source
105

    
106
        dependency_type factor = dependency_type(get(dependency, w))
107
          / dependency_type(get(path_count, w));
108

    
109
        for (incoming_iterator vw = incoming[w].begin();
110
             vw != incoming[w].end(); ++vw) {
111
          vertex_descriptor v = source(*vw, g);
112

    
113
          dependency_type new_dependency_value = get(dependency, v) + (
114
            dependency_type(get(path_count, v)) * factor);
115
          put(dependency, v, new_dependency_value);
116
          update_centrality(edge_centrality_map, *vw, factor);
117
        }
118

    
119
        if (w != *s) {
120
          update_centrality(centrality, w, get(dependency, w));
121
        }
122
      }
123
    }
124

    
125
    typedef typename graph_traits<Graph>::directed_category directed_category;
126
    const bool is_undirected =
127
      is_convertible<directed_category*, undirected_tag*>::value;
128
    if (is_undirected) {
129
      divide_centrality_by_two(vertices(g), centrality);
130
      divide_centrality_by_two(edges(g), edge_centrality_map);
131
    }
132
  }
133
} } // end of namespace detail::graph
134

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

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

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

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

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

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

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

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

    
238

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

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

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

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

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

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

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

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

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

    
342
//////////////////////////////////////
343
// BGL Modification: TARGETS INCLUSION
344
//////////////////////////////////////
345

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

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

    
367
    cout << "@@@ Targets Inclusion @@@\n";
368

    
369
    // Initialize centrality
370
    init_centrality_map(vertices(g), centrality);
371
    init_centrality_map(edges(g), edge_centrality_map);
372

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

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

    
391
      // cout << ordered_vertices.size() << endl;
392
      update_centrality(centrality, *s, ordered_vertices.size() - 1); // number of times *s is a source
393

    
394
      while (!ordered_vertices.empty()) {
395
        vertex_descriptor w = ordered_vertices.top();
396
        ordered_vertices.pop();
397

    
398
        typedef typename property_traits<IncomingMap>::value_type
399
          incoming_type;
400
        typedef typename incoming_type::iterator incoming_iterator;
401
        typedef typename property_traits<DependencyMap>::value_type
402
          dependency_type;
403

    
404
        for (incoming_iterator vw = incoming[w].begin();
405
             vw != incoming[w].end(); ++vw) {
406
          vertex_descriptor v = source(*vw, g);
407
          dependency_type factor = dependency_type(get(path_count, v))
408
            / dependency_type(get(path_count, w));
409
          factor *= (dependency_type(1) + get(dependency, w));
410
          put(dependency, v, get(dependency, v) + factor);
411
          update_centrality(edge_centrality_map, *vw, factor);
412
        }
413

    
414
        if (w != *s) {
415
          if (endpoints_inclusion) {
416
            update_centrality(centrality, w, get(dependency, w) + dependency_type(1));
417
          }
418
          else {
419
            update_centrality(centrality, w, get(dependency, w));
420
          }
421
        }
422
      }
423
    }
424

    
425
    typedef typename graph_traits<Graph>::directed_category directed_category;
426
    const bool is_undirected =
427
      is_convertible<directed_category*, undirected_tag*>::value;
428
    if (is_undirected) {
429
      divide_centrality_by_two(vertices(g), centrality);
430
      divide_centrality_by_two(edges(g), edge_centrality_map);
431
    }
432
  }
433

    
434
} } // end namespace detail::graph
435

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

    
455
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g,
456
                                                     endpoints_inclusion,
457
                                                     centrality,
458
                                                     edge_centrality_map,
459
                                                     incoming, distance,
460
                                                     dependency, path_count,
461
                                                     vertex_index,
462
                                                     shortest_paths);
463
}
464

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

    
486
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_impl(g,
487
                                                     endpoints_inclusion,
488
                                                     centrality,
489
                                                     edge_centrality_map,
490
                                                     incoming, distance,
491
                                                     dependency, path_count,
492
                                                     vertex_index,
493
                                                     shortest_paths);
494
}
495

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

    
517
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
518

    
519
    std::vector<std::vector<edge_descriptor> > incoming(V);
520
    std::vector<centrality_type> distance(V);
521
    std::vector<centrality_type> dependency(V);
522
    std::vector<degree_size_type> path_count(V);
523

    
524
    brandes_betweenness_centrality_endpoints_inclusion(
525
      g,
526
      endpoints_inclusion,
527
      centrality, edge_centrality_map,
528
      make_iterator_property_map(incoming.begin(), vertex_index),
529
      make_iterator_property_map(distance.begin(), vertex_index),
530
      make_iterator_property_map(dependency.begin(), vertex_index),
531
      make_iterator_property_map(path_count.begin(), vertex_index),
532
      vertex_index,
533
      weight_map);
534
  }
535

    
536

    
537
  template<typename Graph,
538
           typename CentralityMap, typename EdgeCentralityMap,
539
           typename VertexIndexMap>
540
  void
541
  brandes_betweenness_centrality_endpoints_inclusion_dispatch2(const Graph& g,
542
                                           bool endpoints_inclusion,
543
                                           CentralityMap centrality,
544
                                           EdgeCentralityMap edge_centrality_map,
545
                                           VertexIndexMap vertex_index)
546
  {
547
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
548
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
549
    typedef typename mpl::if_c<(is_same<CentralityMap,
550
                                        dummy_property_map>::value),
551
                                         EdgeCentralityMap,
552
                               CentralityMap>::type a_centrality_map;
553
    typedef typename property_traits<a_centrality_map>::value_type
554
      centrality_type;
555

    
556
    typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
557

    
558
    std::vector<std::vector<edge_descriptor> > incoming(V);
559
    std::vector<centrality_type> distance(V);
560
    std::vector<centrality_type> dependency(V);
561
    std::vector<degree_size_type> path_count(V);
562

    
563
    brandes_betweenness_centrality_endpoints_inclusion(
564
      g,
565
      endpoints_inclusion,
566
      centrality, edge_centrality_map,
567
      make_iterator_property_map(incoming.begin(), vertex_index),
568
      make_iterator_property_map(distance.begin(), vertex_index),
569
      make_iterator_property_map(dependency.begin(), vertex_index),
570
      make_iterator_property_map(path_count.begin(), vertex_index),
571
      vertex_index);
572
  }
573

    
574
  template<typename WeightMap>
575
  struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1
576
  {
577
    template<typename Graph,
578
             typename CentralityMap,
579
             typename EdgeCentralityMap, typename VertexIndexMap>
580
    static void
581
    run(const Graph& g,
582
        bool endpoints_inclusion,
583
        CentralityMap centrality,
584
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
585
        WeightMap weight_map)
586
    {
587
      brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g,
588
                                               endpoints_inclusion,
589
                                               centrality, edge_centrality_map,
590
                                               weight_map, vertex_index);
591
    }
592
  };
593

    
594
  template<>
595
  struct brandes_betweenness_centrality_endpoints_inclusion_dispatch1<param_not_found>
596
  {
597
    template<typename Graph,
598
             typename CentralityMap,
599
             typename EdgeCentralityMap, typename VertexIndexMap>
600
    static void
601
    run(const Graph& g,
602
        bool endpoints_inclusion,
603
        CentralityMap centrality,
604
        EdgeCentralityMap edge_centrality_map, VertexIndexMap vertex_index,
605
        param_not_found)
606
    {
607
      brandes_betweenness_centrality_endpoints_inclusion_dispatch2(g,
608
                                               endpoints_inclusion,
609
                                               centrality, edge_centrality_map,
610
                                               vertex_index);
611
    }
612
  };
613

    
614
} } // end namespace detail::graph
615

    
616
template<typename Graph, typename Param, typename Tag, typename Rest>
617
void
618
brandes_betweenness_centrality_endpoints_inclusion(const Graph& g,
619
                               bool endpoints_inclusion,
620
                               const bgl_named_params<Param,Tag,Rest>& params
621
                               BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
622
{
623
  typedef bgl_named_params<Param,Tag,Rest> named_params;
624

    
625
  typedef typename get_param_type<edge_weight_t, named_params>::type ew;
626
  detail::graph::brandes_betweenness_centrality_endpoints_inclusion_dispatch1<ew>::run(
627
    g,
628
    endpoints_inclusion,
629
    choose_param(get_param(params, vertex_centrality),
630
                 dummy_property_map()),
631
    choose_param(get_param(params, edge_centrality),
632
                 dummy_property_map()),
633
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
634
    get_param(params, edge_weight));
635
}
636

    
637
} // end namespace boost
638

    
639

    
640
#endif //GRAPH_PARSER_CENTRALITY_H