Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.91 KB)

1
//
2
// Created by quynh on 1/9/16.
3
//
4

    
5
#ifndef GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
6
#define GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
7

    
8
#include <boost/graph/biconnected_components.hpp>
9
#include <queue>
10
#include "common.h"
11
#include "parser.h" // ? check to remove
12
#include "utility.h"
13
#include "sub_component.h"
14
#include "graph_manager.h"
15

    
16

    
17
typedef std::vector<int> ComponentVec; // use int instead of edges_size_type because I want to set default value to be -1
18
typedef boost::iterator_property_map<ComponentVec::iterator, EdgeIndexPMap> ComponentMap;
19

    
20
typedef map<string, vector<int> > VertexIdToComponentStdMap;
21
typedef boost::associative_property_map<VertexIdToComponentStdMap> VertexIdToComponentMap;
22

    
23
typedef std::map<int, vector<string> > ComponentToVertexIdStdMap;
24
typedef boost::associative_property_map<ComponentToVertexIdStdMap> ComponentToVertexIdMap;
25

    
26
typedef vector<vector<Vertex> > Bcc_t;
27
typedef vector<vector<Vertex> >::iterator BccIter_t;
28

    
29
typedef struct {
30
    int component_index;
31
    string vertex_id;
32
    string type;
33
} QueueElem;
34

    
35
class BiConnectedComponents {
36
public:
37
    BiConnectedComponents(GraphManager &gm);
38
    void init();
39

    
40
    // Getter functions
41
    int const num_of_bcc();
42
    int const num_of_vertices() const;
43
    StringSet const& all_art_points_id() const;
44
    NameToDoubleMap const& bc_score() const;
45
    NameToDoubleMap const& bc_relative_score() const;
46

    
47
    // Auto run
48
    void run();
49

    
50
    // SUB-COMPONENT
51
    void FindBiConnectedComponents();
52

    
53
    // LINK WEIGHT - calculation for all sub-components
54
    void CalculateLinkWeight();
55
    void CalculateLinkWeightReversed();
56

    
57
    // TRAFFIC MATRIX - calculation for all sub-components
58
    void CalculateTrafficMatrix();
59

    
60
    // BETWEENNESS CENTRALITY HEURISTIC
61
    void CalculateBetweennessCentralityHeuristic();
62

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

    
66
    // HELPERS FOR OUTPUTTING RESULT
67
    void print_all_sub_components();
68
    void print_biconnected_components();
69
    void print_betweenness_centrality();
70
    void print_betweenness_centrality_heuristic();
71

    
72
    void write_all_betweenness_centrality(string filepath);
73

    
74
    void print();
75
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
76

    
77
    // Public variables
78
    GraphManager gm_;
79
    typedef vector<SubComponent> Component_t;
80
    typedef vector<SubComponent>::iterator ComponentIter_t;
81
    Component_t BCCs;
82

    
83
private:
84
    // SUB-COMPONENT
85
    void reset_num_of_bcc();
86
    void CreateSubComponents();
87

    
88
    // LINK WEIGHT - calculation for all sub-components
89
    void initialize_weight();
90
    void initialize_queue();
91
    void process_component_vertex_pair(int comp_index, string vertex_id);
92
    void process_vertex_component_pair(int comp_index, string vertex_id);
93
    void find_unknown_weight_wrt_art_point(string vertex_id);
94
    void find_unknown_weight_wrt_component(int comp_index);
95
    bool verify_link_weight();
96

    
97
    // BETWEENNESS CENTRALITY HEURISTIC
98
    void initialize_betweenness_centrality_heuristic();
99
    void calculate_bc_inter();
100
    void finalize_betweenness_centrality_heuristic();
101

    
102
    // BETWEENNESS CENTRALITY
103
    void initialize_betweenness_centrality();
104

    
105
    // Private variables
106
    ComponentVec component_vec_;
107
    ComponentMap component_map_;
108
    vector<Vertex> art_points_;
109
    StringSet all_art_points_id_;
110

    
111
    int num_of_bcc_ = -1;
112
    int num_of_vertices_ = -1;
113

    
114
    std::queue<QueueElem> Q;
115

    
116
    // bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
117
    // Betweenness Centrality Heuristic
118
    NameToDoubleMap bc_score_;
119
    NameToDoubleMap bc_relative_score_;
120
    NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
121
    NameToDoubleMap bc_inter_;
122

    
123
    // Betweenness Centrality - standard calculation
124
    CentralityVec v_centrality_vec_;
125
    CentralityPMap v_centrality_pmap_;
126
};
127

    
128
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H