Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.91 KB)

1 ee0dd796 Quynh PX Nguyen
//
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 cb770240 Quynh PX Nguyen
#include "parser.h" // ? check to remove
12 ee0dd796 Quynh PX Nguyen
#include "utility.h"
13
#include "sub_component.h"
14 cb770240 Quynh PX Nguyen
#include "graph_manager.h"
15 ee0dd796 Quynh PX Nguyen
16
17 e263e3c7 Quynh PX Nguyen
typedef std::vector<int> ComponentVec; // use int instead of edges_size_type because I want to set default value to be -1
18 437fd680 Quynh PX Nguyen
typedef boost::iterator_property_map<ComponentVec::iterator, EdgeIndexPMap> ComponentMap;
19 ee0dd796 Quynh PX Nguyen
20 cb770240 Quynh PX Nguyen
typedef map<string, vector<int> > VertexIdToComponentStdMap;
21
typedef boost::associative_property_map<VertexIdToComponentStdMap> VertexIdToComponentMap;
22 ee0dd796 Quynh PX Nguyen
23 cb770240 Quynh PX Nguyen
typedef std::map<int, vector<string> > ComponentToVertexIdStdMap;
24
typedef boost::associative_property_map<ComponentToVertexIdStdMap> ComponentToVertexIdMap;
25 ee0dd796 Quynh PX Nguyen
26
typedef vector<vector<Vertex> > Bcc_t;
27
typedef vector<vector<Vertex> >::iterator BccIter_t;
28
29
typedef struct {
30
    int component_index;
31 cb770240 Quynh PX Nguyen
    string vertex_id;
32 ee0dd796 Quynh PX Nguyen
    string type;
33
} QueueElem;
34
35
class BiConnectedComponents {
36 cb770240 Quynh PX Nguyen
public:
37 d5b7a27f Quynh PX Nguyen
    BiConnectedComponents(GraphManager &gm);
38 cb770240 Quynh PX Nguyen
    void init();
39 ee0dd796 Quynh PX Nguyen
40 cb770240 Quynh PX Nguyen
    // Getter functions
41 437fd680 Quynh PX Nguyen
    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 162e1bda Quynh PX Nguyen
    NameToDoubleMap const& bc_relative_score() const;
46
47
    // Auto run
48
    void run();
49 ee0dd796 Quynh PX Nguyen
50 cb770240 Quynh PX Nguyen
    // SUB-COMPONENT
51
    void FindBiConnectedComponents();
52 ee0dd796 Quynh PX Nguyen
53 cb770240 Quynh PX Nguyen
    // LINK WEIGHT - calculation for all sub-components
54
    void CalculateLinkWeight();
55 162e1bda Quynh PX Nguyen
    void CalculateLinkWeightReversed();
56 ee0dd796 Quynh PX Nguyen
57 cb770240 Quynh PX Nguyen
    // TRAFFIC MATRIX - calculation for all sub-components
58
    void CalculateTrafficMatrix();
59 ee0dd796 Quynh PX Nguyen
60 162e1bda Quynh PX Nguyen
    // BETWEENNESS CENTRALITY HEURISTIC
61
    void CalculateBetweennessCentralityHeuristic();
62
63 20756421 Quynh PX Nguyen
    // BETWEENNESS CENTRALITY
64 d5b7a27f Quynh PX Nguyen
    void CalculateBetweennessCentrality(bool targets_inclusion = true);
65 ee0dd796 Quynh PX Nguyen
66 cb770240 Quynh PX Nguyen
    // HELPERS FOR OUTPUTTING RESULT
67 162e1bda Quynh PX Nguyen
    void print_all_sub_components();
68 d5b7a27f Quynh PX Nguyen
    void print_biconnected_components();
69 162e1bda Quynh PX Nguyen
    void print_betweenness_centrality();
70
    void print_betweenness_centrality_heuristic();
71
72
    void write_all_betweenness_centrality(string filepath);
73
74 cb770240 Quynh PX Nguyen
    void print();
75
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
76 ee0dd796 Quynh PX Nguyen
77 cb770240 Quynh PX Nguyen
    // Public variables
78
    GraphManager gm_;
79
    typedef vector<SubComponent> Component_t;
80
    typedef vector<SubComponent>::iterator ComponentIter_t;
81 ee0dd796 Quynh PX Nguyen
    Component_t BCCs;
82
83 cb770240 Quynh PX Nguyen
private:
84 162e1bda Quynh PX Nguyen
    // SUB-COMPONENT
85 e263e3c7 Quynh PX Nguyen
    void reset_num_of_bcc();
86 162e1bda Quynh PX Nguyen
    void CreateSubComponents();
87
88 cb770240 Quynh PX Nguyen
    // 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 162e1bda Quynh PX Nguyen
    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 ee0dd796 Quynh PX Nguyen
105 cb770240 Quynh PX Nguyen
    // Private variables
106
    ComponentVec component_vec_;
107
    ComponentMap component_map_;
108
    vector<Vertex> art_points_;
109 437fd680 Quynh PX Nguyen
    StringSet all_art_points_id_;
110 ee0dd796 Quynh PX Nguyen
111 cb770240 Quynh PX Nguyen
    int num_of_bcc_ = -1;
112
    int num_of_vertices_ = -1;
113 ee0dd796 Quynh PX Nguyen
114 cb770240 Quynh PX Nguyen
    std::queue<QueueElem> Q;
115 ee0dd796 Quynh PX Nguyen
116 437fd680 Quynh PX Nguyen
    // bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
117 162e1bda Quynh PX Nguyen
    // Betweenness Centrality Heuristic
118 437fd680 Quynh PX Nguyen
    NameToDoubleMap bc_score_;
119 162e1bda Quynh PX Nguyen
    NameToDoubleMap bc_relative_score_;
120 437fd680 Quynh PX Nguyen
    NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
121
    NameToDoubleMap bc_inter_;
122 162e1bda Quynh PX Nguyen
123
    // Betweenness Centrality - standard calculation
124
    CentralityVec v_centrality_vec_;
125
    CentralityPMap v_centrality_pmap_;
126 ee0dd796 Quynh PX Nguyen
};
127
128
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H