Revision d5b7a27f

View differences:

custompackages/graph-parser/src/Makefile
5 5
INCLUDES = -I/usr/local/boost/
6 6

  
7 7
# define the C source files
8
SRCS = main.cpp bi_connected_components.cpp centrality.cpp graph_manager.cpp parser.cpp sub_component.cpp utility.cpp
8
SRCS = main.cpp bi_connected_components.cpp graph_manager.cpp parser.cpp sub_component.cpp utility.cpp
9 9

  
10 10

  
11 11
# define the C object files
custompackages/graph-parser/src/bi_connected_components.cpp
8 8
/******************************
9 9
* Public functions
10 10
******************************/
11
BiConnectedComponents::BiConnectedComponents(GraphManager &gm, bool weighted_graph) : gm_(gm), weighted_graph_(weighted_graph) {
11
BiConnectedComponents::BiConnectedComponents(GraphManager &gm) : gm_(gm) {
12 12
    init();
13 13
}
14 14

  
......
41 41
    return bc_relative_score_;
42 42
}
43 43

  
44
bool BiConnectedComponents::weighted_graph() const {
45
    return weighted_graph_;
46
}
47

  
48
// Setter functions
49
void BiConnectedComponents::set_weighted_graph(bool rhs) {
50
    weighted_graph_ = rhs;
51
}
52

  
53 44
// AUTO RUN
54 45
void BiConnectedComponents::run() {
55 46
    /* Auto run all the necessary functions
56 47
    */
48
    cout << "Running FindBiConnectedComponents" << endl;
57 49
    FindBiConnectedComponents();
58 50

  
59
    cout << "\nArticulation points:\n";
60
    outops::operator<<(cout, all_art_points_id_);
61

  
62
    cout << "All Sub Components:\n\n";
63
    for (int i = 0; i < num_of_bcc_; ++i) {
64
        cout << "    " << i << endl;
65
        outops::operator<<(cout, BCCs[i].all_vertices_id());
66
    }
67

  
68 51
    // Calculate Link Weight + Link Weight Reversed
69 52
    cout << "Calculate Link Weight + Link Weight Reversed\n";
70 53
    CalculateLinkWeight();
......
78 61
    // Calculate Betweenness Centrality Heuristic
79 62
    cout << "Calculate Betweenness Centrality Heuristic\n";
80 63
    CalculateBetweennessCentralityHeuristic();
81

  
82
    // Calculate Betweenness Centrality
83
    cout << "Calculate Betweenness Centrality\n";
84
    CalculateBetweennessCentrality();
85 64
}
86 65

  
87 66
// SUB-COMPONENT
88 67
void BiConnectedComponents::FindBiConnectedComponents() {
89
    cout << "Running FindBiConnectedComponents" << endl;
90

  
91 68
    boost::biconnected_components(gm_.g_, component_map_,
92 69
                                  back_inserter(art_points_),
93 70
                                  boost::vertex_index_map(gm_.v_index_pmap()));
......
99 76

  
100 77
    // Process the result from boost::biconnected_components
101 78
    cout << "Create Sub Components\n";
102
    BCCs = Component_t(num_of_bcc_);
103 79
    CreateSubComponents();
104 80
}
105 81

  
......
191 167
}
192 168

  
193 169
// BETWEENNESS CENTRALITY - NORMAL CALCULATION
194
void BiConnectedComponents::CalculateBetweennessCentrality() {
170
void BiConnectedComponents::CalculateBetweennessCentrality(bool targets_inclusion) {
195 171
    initialize_betweenness_centrality();
196 172

  
197
    if (weighted_graph_) { // calculate BC for weighted graph
173
    if (gm_.weighted_graph()) { // calculate BC for weighted graph
174
        cout << "======= BCC - BC for weighted graph ======\n";
175

  
198 176
        typedef map<Edge, double> EdgeWeightStdMap;
199 177
        typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;
200 178
        EdgeIndexStdMap edge_weight_std_map;
......
203 181
        BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
204 182
            edge_weight_std_map[edge] = gm_.g_[edge].cost;
205 183
        }
206
        boost::brandes_betweenness_centrality(gm_.g_,
184
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
185
            targets_inclusion,
207 186
            boost::centrality_map(
208 187
                v_centrality_pmap_).vertex_index_map(
209 188
                gm_.v_index_pmap()).weight_map(
......
211 190
        );
212 191
    }
213 192
    else { // for unweighted graph
214
        boost::brandes_betweenness_centrality(gm_.g_,
193
        boost::brandes_betweenness_centrality_targets_inclusion(gm_.g_,
194
            targets_inclusion,
215 195
            boost::centrality_map(
216 196
                v_centrality_pmap_).vertex_index_map(
217 197
                gm_.v_index_pmap())
......
229 209
    }
230 210
}
231 211

  
212
void BiConnectedComponents::print_biconnected_components() {
213
    cout << "\nArticulation points:\n";
214
    outops::operator<<(cout, all_art_points_id_);
215

  
216
    cout << "All Sub Components:\n\n";
217
    for (int i = 0; i < num_of_bcc_; ++i) {
218
        cout << "    " << i << endl;
219
        outops::operator<<(cout, BCCs[i].all_vertices_id());
220
    }
221
}
222

  
232 223
void BiConnectedComponents::print_betweenness_centrality() {
233 224
    BGL_FORALL_VERTICES(v, gm_.g_, Graph) {
234 225
        double bc_score = boost::get(v_centrality_pmap_, v);
......
261 252
            int index = gm_.get_index_from_id(id);
262 253
            double bc_score = v_centrality_vec_.at(index);
263 254

  
264
            outFile << id << "\t" << bc_score << "\t" << heuristic_bc_score << endl;
255
            outFile << id << "\t" << setprecision(4) << fixed << bc_score << "\t" << heuristic_bc_score << endl;
265 256
        }
266 257
        // for (boost::tie(vi, ve) = boost::vertices(gm_.g_); vi != ve; ++vi) {
267 258
        //     string id = gm_.g_[*vi].id;
......
277 268
    cout << "\n\nBi-Connected Components\n\n";
278 269
    cout << gm_;
279 270

  
280
    cout << "\nArticulation points:\n";
281
    outops::operator<<(cout, all_art_points_id_);
282

  
283
    cout << "All Sub Components:\n\n";
284
    for (int i = 0; i < num_of_bcc_; ++i) {
285
        cout << "    " << i << endl;
286
        outops::operator<<(cout, BCCs[i].all_vertices_id());
287
    }
271
    print_biconnected_components();
288 272

  
289 273
    cout << "\nHeuristic Betweenness Centrality Score:\n";
290 274
    outops::operator<< <double>(cout, bc_score_);
......
294 278

  
295 279
    cout << "\nNormal Betweenness Centrality Score:\n";
296 280
    print_betweenness_centrality();
297

  
298
    cout << "Special debugging case\n";
299
    BCCs[71].print();
300 281
}
301 282

  
302 283
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
......
324 305
}
325 306

  
326 307
void BiConnectedComponents::CreateSubComponents() {
327
    cout << "Create Sub COmponent\n";
308
    for (int i = 0; i < num_of_bcc_; ++i) {
309
        BCCs.push_back(SubComponent(gm_.weighted_graph()));
310
    }
311

  
328 312
    // Generating subgraph for each sub-component
329 313
    BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
330 314
        Vertex source = boost::source(edge, gm_.g_);
......
371 355
                .vertex_id = vertex_id,
372 356
                .type = type,
373 357
            };
374
            cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
358
            // cout << "adding component_vertex_pair (" << i << " " << vertex_id << ")\n";
375 359
            Q.push(elem);
376 360
        }
377 361
    }
......
397 381
    }
398 382

  
399 383
    BCCs[comp_index].update_weight_map(vertex_id, link_weight);
400
    cout << "  update weight for comp " << comp_index << " | vertex " << vertex_id << " = " << link_weight << endl;
384
    // cout << "  update weight for comp " << comp_index << " | vertex " << vertex_id << " = " << link_weight << endl;
401 385
    find_unknown_weight_wrt_art_point(vertex_id);
402 386
}
403 387

  
custompackages/graph-parser/src/bi_connected_components.h
34 34

  
35 35
class BiConnectedComponents {
36 36
public:
37
    BiConnectedComponents(GraphManager &gm, bool weighted_graph = true);
37
    BiConnectedComponents(GraphManager &gm);
38 38
    void init();
39 39

  
40 40
    // Getter functions
......
43 43
    StringSet const& all_art_points_id() const;
44 44
    NameToDoubleMap const& bc_score() const;
45 45
    NameToDoubleMap const& bc_relative_score() const;
46
    bool weighted_graph() const;
47

  
48
    // Setter functions
49
    void set_weighted_graph(bool rhs);
50 46

  
51 47
    // Auto run
52 48
    void run();
......
65 61
    void CalculateBetweennessCentralityHeuristic();
66 62

  
67 63
    // BETWEENNESS CENTRALITY
68
    void CalculateBetweennessCentrality();
64
    void CalculateBetweennessCentrality(bool targets_inclusion = true);
69 65

  
70 66
    // HELPERS FOR OUTPUTTING RESULT
71 67
    void print_all_sub_components();
72

  
68
    void print_biconnected_components();
73 69
    void print_betweenness_centrality();
74 70
    void print_betweenness_centrality_heuristic();
75 71

  
......
80 76

  
81 77
    // Public variables
82 78
    GraphManager gm_;
83
    bool weighted_graph_;
84 79
    typedef vector<SubComponent> Component_t;
85 80
    typedef vector<SubComponent>::iterator ComponentIter_t;
86 81
    Component_t BCCs;
custompackages/graph-parser/src/centrality.h
128 128
      divide_centrality_by_two(edges(g), edge_centrality_map);
129 129
    }
130 130
  }
131

  
132

  
133

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

  
136 133
template<typename Graph,
......
340 337
    get_param(params, edge_weight));
341 338
}
342 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

  
343 632
} // end namespace boost
344 633

  
634

  
345 635
#endif //GRAPH_PARSER_CENTRALITY_H
custompackages/graph-parser/src/graph_manager.cpp
1 1
#include "graph_manager.h"
2 2

  
3 3
// CONSTRUCTOR
4
GraphManager::GraphManager() {
4
GraphManager::GraphManager(bool weighted_graph) : weighted_graph_(weighted_graph) {
5 5
    v_index_pmap_ = VertexIndexPMap(v_index_std_map_);
6 6
    e_index_pmap_ = EdgeIndexPMap(e_index_std_map_);
7 7
}
8 8

  
9 9
GraphManager::GraphManager(const GraphManager& other) {
10
    cout << "\n\n*******COPY CONSTRUCTOR******\n\n";
10
    // cout << "\n*******COPY CONSTRUCTOR******\n";
11 11
    g_ = other.g_;
12
    weighted_graph_ = other.weighted_graph_;
12 13
    ResetVerticesAndEdgesIndexMap();
13 14
}
14 15

  
15
GraphManager& GraphManager::operator=(GraphManager& rhs) {
16
    cout << "\n\n*******ASSIGNMENT OPERATOR******\n\n";
16
GraphManager& GraphManager::operator=(const GraphManager& rhs) {
17
    // cout << "\n*******ASSIGNMENT OPERATOR******\n";
17 18
    g_ = rhs.g_;
19
    weighted_graph_ = rhs.weighted_graph_;
18 20
    ResetVerticesAndEdgesIndexMap();
19 21

  
20 22
    return *this;
......
32 34
    return v_id_index_map_;
33 35
}
34 36

  
37
bool GraphManager::weighted_graph() const {
38
    return weighted_graph_;
39
}
40

  
35 41
// UPDATE GRAPHS
36 42
void GraphManager::AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep) {
37 43
    // cout << "add edge GM " << vp1.label << " - " << vp2.label << endl;
......
110 116
    bool connected = graphext::is_connected(g_, v_index_pmap_);
111 117
    cout << "Connected = " << connected << endl;
112 118

  
119
    cout << "Is this a weighted graph?\n";
120
    cout << "is weighted = " << weighted_graph_ << endl;
121

  
113 122
    cout << "v_id_index_map:\n";
114 123
    outops::operator<< <int>(cout, v_id_index_map_);
115 124
}
custompackages/graph-parser/src/graph_manager.h
15 15
    typedef std::map<std::string, Vertex> NameVertexMap;
16 16

  
17 17
    // CONSTRUCTOR
18
    GraphManager(); // constructor
18
    GraphManager(bool weighted_graph=true); // constructor
19 19
    GraphManager(const GraphManager& other); // copy constructor
20
    GraphManager& operator=(GraphManager& rhs); // assignment operator
20
    GraphManager& operator=(const GraphManager& rhs); // assignment operator
21 21
    // check out more here: http://www.cplusplus.com/articles/y8hv0pDG/
22 22

  
23 23
    // GETTERS
24 24
    const VertexIndexPMap& v_index_pmap() const;
25 25
    const EdgeIndexPMap& e_index_pmap() const;
26 26
    NameToIntMap const& v_id_index_map() const;
27
    bool weighted_graph() const;
27 28

  
28 29
    // UPDATE GRAPH
29 30
    void AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep);
......
54 55
    void update_e_index_pmap(Edge new_edge);
55 56

  
56 57
    // VARIABLES
58
    bool weighted_graph_;
59

  
57 60
    NameVertexMap v_id_vertex_map_;
58 61
    NameToIntMap v_id_index_map_;
59 62

  
custompackages/graph-parser/src/main.cpp
22 22
    gm.print();
23 23
}
24 24

  
25
void default_run() {
25
void default_run(bool is_weighted_graph, bool targets_inclusion) {
26 26
    // input_files = [(filepath, input_type)]
27 27
    // input_type = 1 ==> edges file
28 28
    // input_type = 2 ==> simple json file
29 29
    // input_type = 3 ==> complex json file
30 30

  
31 31
    std::list< std::tuple<string, int> > input_files;
32
    // input_files.push_back(std::make_tuple("../input/ninux_unweighted_connected.edges", 1));
33
    // input_files.push_back(std::make_tuple("../input/simple.edges", 1));
34
    // input_files.push_back(std::make_tuple("../input/ninux_30_1.edges", 1));
35
    // input_files.push_back(std::make_tuple("../input/olsr-netjson.json", 2));
32
    input_files.push_back(std::make_tuple("../input/simple.edges", 1));
33
    input_files.push_back(std::make_tuple("../input/ninux_unweighted_connected.edges", 1));
34
    input_files.push_back(std::make_tuple("../input/ninux_30_1.edges", 1));
35
    input_files.push_back(std::make_tuple("../input/olsr-netjson.json", 2));
36 36
    input_files.push_back(std::make_tuple("../input/jsoninfo_topo.json", 3));
37 37

  
38 38
    for (auto input : input_files) {
39 39
        string filepath = std::get<0>(input);
40 40
        int input_type = std::get<1>(input);
41
        GraphManager gm;
41

  
42
        GraphManager gm(is_weighted_graph);
43

  
42 44
        if (input_type == 1) {
43 45
            readEdgeFileGraphManager(filepath, gm);
44 46
        }
......
51 53

  
52 54
        gm.print();
53 55

  
54
        BiConnectedComponents bcc = BiConnectedComponents(gm, false);
56
        BiConnectedComponents bcc = BiConnectedComponents(gm);
55 57
        bcc.run();
58

  
59
        // Calculate Betweenness Centrality
60
        cout << "Calculate Betweenness Centrality\n";
61
        bcc.CalculateBetweennessCentrality(targets_inclusion);
56 62
        // bcc.print();
57
        string filename = helper::get_file_name(filepath);
58
        string out_filepath = "../output/" + filename + ".out";;
63

  
64
        string filename;
65
        string ext;
66
        helper::get_file_name_and_extension(filepath, filename, ext);
67

  
68
        string out_filepath = "../output/" + filename;
69
        if (is_weighted_graph) {
70
            out_filepath += "_weighted.out";
71
        }
72
        else {
73
            out_filepath += "_unweighted.out";
74
        }
59 75
        bcc.write_all_betweenness_centrality(out_filepath);
60 76
    }
61 77
}
......
67 83
    testHeuristic(simpleGraphfilepath);
68 84
}
69 85

  
70
int main(int, char *[]) {
71
    default_run();
86
int main(int argc, char * argv[]) {
87
    bool is_weighted_graph = true;
88
    bool targets_inclusion = true;
89

  
90
    if (argc >= 2) {
91
        string argument(argv[1]);
92
        if (argument.compare("false") == 0) {
93
            is_weighted_graph = false;
94
        }
95

  
96
        if (argc > 2) {
97
           argument = string(argv[2]);
98
            if (argument.compare("false") == 0) {
99
                targets_inclusion = false;
100
            }
101
        }
102
    }
103

  
104
    default_run(is_weighted_graph, targets_inclusion);
72 105

  
106
    cout << "is weighted graph  = " << is_weighted_graph << endl;
73 107
    return 0;
74 108
}
custompackages/graph-parser/src/plot_BC_comparison.gp
2 2
set terminal postscript eps
3 3

  
4 4
if (!exists("FILENAME")) FILENAME='simple.edges.out'
5
INPUT_FILEPATH = sprintf("../output/%s", FILENAME)
6
set output sprintf("../output/visualization/%s_unweighted.eps", FILENAME)
7
set title "Centrality for edge_list"
5
if (!exists("SUFFIX")) SUFFIX=''
6

  
7
INPUT_FILEPATH = sprintf("../output/%s.out", FILENAME)
8
set output sprintf("../output/visualization/%s.eps", FILENAME)
9

  
10
set title sprintf("Centrality for %s", FILENAME) noenhanced # to display underscore instead of subscript
8 11
set xlabel "Router (each integer corresponds to one router)"
9 12
set ylabel "Betweenness Centrality"
10 13

  
11
plot INPUT_FILEPATH using 2 title 'brandes unweighted (no inclusion of endpoints)' pointtype 7 pointsize 0.7, \
12
     INPUT_FILEPATH using 3 title 'heuristic (not substracted by bc\_inter)' pointtype 5 pointsize 1
14
plot INPUT_FILEPATH using 2 title sprintf('brandes %s (targets inclusion)', SUFFIX) pointtype 5 pointsize 1, \
15
     INPUT_FILEPATH using 3 title sprintf('heuristic %s (not substracted by bc\_inter)', SUFFIX) pointtype 7 pointsize 0.7
custompackages/graph-parser/src/script.sh
1
## TUTORIAL:
2
## The script take 2 command-line arguments:
3
## $1: specify whether to calculate betweenness centrality as an unweighted graph (false) or weighted graph (true). This argument is for both Heuristic BC and Brandes BC
4
## $2: specify whether to include targets when calculating betweenness centrality (for the Brandes BC)
5

  
6
## If no argument is supplied, then the default is "./script.sh true true"
7

  
8
#########
9
## YOU CAN MODIFY THIS PART
10
#########
11
# Change the variables to run the Betweenness Centrality for weighted or unweighted graph.
12
if [ -z "$1" ] # No argument supplied
13
then
14
    WEIGHTED_GRAPH="true"; # 2 possible values: [true | false]
15
else
16
    WEIGHTED_GRAPH="$1";
17
fi
18

  
19
if [ -z "$2" ] # No argument supplied
20
then
21
   TARGETS_INCLUSION="true"; # 2 possible values: [true | false]
22
else
23
    TARGETS_INCLUSION="$1";
24
fi
25

  
26
#########
27
## TRY TO AVOID MODIFYING ANYTHING BELOW THIS LINE
28
#########
1 29
make
2
../bin/main
3

  
4
# visualization
5
echo "Start plotting";
6
gnuplot -e "FILENAME='simple.edges.out'" plot_BC_comparison.gp
7
gnuplot -e "FILENAME='ninux_unweighted_connected.edges.out'" plot_BC_comparison.gp
8
gnuplot -e "FILENAME='ninux_30_1.edges.out'" plot_BC_comparison.gp
9
gnuplot -e "FILENAME='jsoninfo_topo.json.out'" plot_BC_comparison.gp
10
gnuplot -e "FILENAME='olsr-netjson.json.out'" plot_BC_comparison.gp
11
echo "Done with plotting"
30

  
31
## Remove all the previous output
32
# rm ../output/*.out
33

  
34
## Running the script
35
../bin/main $WEIGHTED_GRAPH $TARGETS_INCLUSION
36

  
37
## Plotting the results
38
if [ $WEIGHTED_GRAPH = "true" ]
39
then
40
    SUFFIX="weighted"; # the suffix used in the filename
41
else
42
    SUFFIX="unweighted";
43
fi
44

  
45
## declare an array variables
46
declare -a arr=("simple" "ninux_unweighted_connected" "ninux_30_1" "jsoninfo_topo" "olsr-netjson")
47

  
48
# loop through the array and format the option for gnuplot
49
# gnuplot -e "FILENAME='simple'; SUFFIX='$SUFFIX'" plot_BC_comparison.gp
50
for i in "${arr[@]}"
51
do
52
    option="FILENAME='"$i"_"$SUFFIX"'; SUFFIX='$SUFFIX'";
53
    gnuplot -e "$option" plot_BC_comparison.gp
54
done
custompackages/graph-parser/src/sub_component.cpp
4 4

  
5 5
#include "sub_component.h"
6 6

  
7
SubComponent::SubComponent() {
8
    // do nothing
7
SubComponent::SubComponent(bool weighted_graph) {
8
    // cout << "===> Start SubComponent() constructor, weighted =" << weighted_graph << endl;
9
    gm_ = GraphManager(weighted_graph);
10
    // cout << "<=== Finish SubComponent() constructor\n";
9 11
}
10 12

  
11 13
/* GETTERS & SETTERS & UPDATERS */
......
24 26
StringSet const& SubComponent::non_art_points_id() const {
25 27
    return non_art_points_id_;
26 28
}
29

  
27 30
NameToIntMap const& SubComponent::weight_map() const {
28 31
    // Returns the whole weight_map_, for all the vertices
29 32
    // This one is different from get_weight_map(name)
......
190 193
void SubComponent::CalculateBetweennessCentralityHeuristic() {
191 194
    initialize_betweenness_centrality();
192 195

  
193
    boost::brandes_betweenness_centrality_heuristic(gm_.g_,
194
        traffic_matrix_pmap_,
195
        boost::centrality_map(
196
            v_centrality_pmap_).vertex_index_map(
197
            gm_.v_index_pmap())
198
    );
196
    if (gm_.weighted_graph()) {
197
        cout << "---- Sub Component BC for weighted graph -----\n";
198

  
199
        typedef map<Edge, double> EdgeWeightStdMap;
200
        typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;
201
        EdgeIndexStdMap edge_weight_std_map;
202
        EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map);
203

  
204
        BGL_FORALL_EDGES(edge, gm_.g_, Graph) {
205
            edge_weight_std_map[edge] = gm_.g_[edge].cost;
206
        }
207

  
208
        boost::brandes_betweenness_centrality_heuristic(gm_.g_,
209
            traffic_matrix_pmap_,
210
            boost::centrality_map(
211
                v_centrality_pmap_).vertex_index_map(
212
                gm_.v_index_pmap()).weight_map(
213
                edge_weight_pmap)
214
        );
215
    }
216
    else {
217
        cout << "---- Sub Component BC for unweighted graph -----\n";
218
        boost::brandes_betweenness_centrality_heuristic(gm_.g_,
219
            traffic_matrix_pmap_,
220
            boost::centrality_map(
221
                v_centrality_pmap_).vertex_index_map(
222
                gm_.v_index_pmap())
223
        );
224
    }
199 225
}
200 226

  
201 227
void SubComponent::initialize_betweenness_centrality() {
custompackages/graph-parser/src/sub_component.h
20 20
    typedef std::vector<double> CentralityVec;
21 21
    typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexPMap> CentralityPMap;
22 22

  
23
    SubComponent();
23
    SubComponent(bool weighted_graph = false);
24 24

  
25 25
    // Getter & Setter
26 26
    GraphManager const& gm() const;
custompackages/graph-parser/src/utility.cpp
182 182

  
183 183
// GENERAL HELPERS
184 184
namespace helper {
185
    string get_file_name(const string& s) {
186
       char sep = '/';
187

  
188
    #ifdef _WIN32
189
       sep = '\\';
190
    #endif
191

  
192
       size_t i = s.rfind(sep, s.length());
193
       if (i != string::npos) {
194
          return(s.substr(i+1, s.length() - i));
195
       }
196

  
197
       return("");
185
    void get_file_name_and_extension(string path, string& name, string& ext) {
186
        size_t sep = path.find_last_of("\\/");
187
        if (sep != std::string::npos)
188
            path = path.substr(sep + 1, path.size() - sep - 1);
189

  
190
        size_t dot = path.find_last_of(".");
191
        if (dot != std::string::npos)
192
        {
193
            name = path.substr(0, dot);
194
            ext  = path.substr(dot, path.size() - dot);
195
        }
196
        else
197
        {
198
            name = path;
199
            ext  = "";
200
        }
198 201
    }
199 202
}
custompackages/graph-parser/src/utility.h
81 81

  
82 82
namespace helper {
83 83
    // I do not want to use boost::filesystem, due to additional library must be included
84
    string get_file_name(const string& s);
84
    void get_file_name_and_extension(string s, string& name, string& ext);
85 85
}
86 86

  
87 87
template <typename Pair>

Also available in: Unified diff