Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / bi_connected_components.h @ 437fd680

History | View | Annotate | Download (2.95 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<edges_size_type> ComponentVec;
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

    
46
    // SUB-COMPONENT
47
    void FindBiConnectedComponents();
48
    void CreateSubComponents();
49

    
50
    // LINK WEIGHT - calculation for all sub-components
51
    void CalculateLinkWeight();
52

    
53
    // TRAFFIC MATRIX - calculation for all sub-components
54
    void CalculateTrafficMatrix();
55

    
56
    // BETWEENNESS CENTRALITY
57
    void CalculateBetweennessCentrality();
58
    void initialize_betweenness_centrality();
59
    void calculate_bc_inter();
60
    void finalize_betweenness_centrality();
61

    
62
    // HELPERS FOR OUTPUTTING RESULT
63
    void print();
64
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
65

    
66
    // Public variables
67
    GraphManager gm_;
68
    typedef vector<SubComponent> Component_t;
69
    typedef vector<SubComponent>::iterator ComponentIter_t;
70
    Component_t BCCs;
71

    
72
private:
73
    // LINK WEIGHT - calculation for all sub-components
74
    void initialize_weight();
75
    void initialize_queue();
76
    void process_component_vertex_pair(int comp_index, string vertex_id);
77
    void process_vertex_component_pair(int comp_index, string vertex_id);
78
    void find_unknown_weight_wrt_art_point(string vertex_id);
79
    void find_unknown_weight_wrt_component(int comp_index);
80

    
81
    // Private variables
82
    ComponentVec component_vec_;
83
    ComponentMap component_map_;
84
    vector<Vertex> art_points_;
85
    StringSet all_art_points_id_;
86

    
87
    int num_of_bcc_ = -1;
88
    int num_of_vertices_ = -1;
89

    
90
    std::queue<QueueElem> Q;
91

    
92
    // bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
93
    NameToDoubleMap bc_score_;
94
    NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
95
    NameToDoubleMap bc_inter_;
96
};
97

    
98
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H