Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.07 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"
12
#include "utility.h"
13
#include "sub_component.h"
14

    
15

    
16
typedef std::vector<edges_size_type> ComponentVec;
17
typedef boost::iterator_property_map<ComponentVec::iterator, EdgeIndexMap> ComponentMap;
18

    
19
typedef map<Vertex, vector<int> > ArtPointComponentStdMap;
20
typedef boost::associative_property_map<ArtPointComponentStdMap> ArtPointComponentMap;
21

    
22
typedef std::map<int, vector<Vertex> > ComponentArtPointStdMap;
23
typedef boost::associative_property_map<ComponentArtPointStdMap> ComponentArtPointMap;
24

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

    
28

    
29

    
30
typedef struct {
31
    int component_index;
32
    Vertex art_point;
33
    string type;
34
} QueueElem;
35

    
36
class BiConnectedComponents {
37
private:
38
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
39
    StdEdgeIndexMap e_index_std_map;
40
    EdgeIndexMap e_index_map;
41

    
42
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
43
    StdVertexIndexMap v_index_std_map;
44

    
45
    int num_of_bcc = -1;
46

    
47
    std::queue<QueueElem> Q;
48

    
49
public:
50
    typedef vector<SubComponent> Component_t;
51
    typedef vector<SubComponent>::iterator ComponentIter_t;
52

    
53
    Graph g;
54

    
55
    VertexIndexMap v_index_map;
56
    ComponentVec component_vec;
57
    ComponentMap component_map;
58

    
59
    vector<Vertex> art_points;
60

    
61
    Bcc_t bcc_vertices;
62
    Component_t BCCs;
63

    
64
    ArtPointComponentStdMap art_point_component_std_map;
65
    ArtPointComponentMap art_point_component_map;
66

    
67
    ComponentArtPointStdMap component_art_point_std_map;
68
    ComponentArtPointMap component_art_point_map;
69

    
70

    
71
    BiConnectedComponents(const Graph &g);
72
    void init();
73
    void findBiConnectedComponents();
74
    void createSubComponents();
75
    void print();
76

    
77
    int num_bcc();
78
    void verticesInBCC();
79
    void testVerticesInBCC();
80

    
81
    bool hasVertex(Vertex v, int comp_index);
82
    void processArtPoints();
83
    void testProcessArtPoints();
84

    
85
    VertexVec get_art_points_for_component(int comp_index);
86
    vector<int> get_components_for_art_point(Vertex vertex);
87

    
88
    VertexVec get_normal_vertices_for_component(int comp_index);
89

    
90
    int num_of_vertices_in_component(int comp_index);
91

    
92
    // Calculate link weight (component tree weight)
93
    void compute_weight();
94
    void _initialize_weight();
95
    void _initialize_queue();
96
    void _find_unknown_weight_wrt_art_point(Vertex art_point);
97
    void _find_unknown_weight_wrt_component(int comp_index);
98
    void _find_unknown_weight_for_component(int comp_index, VertexVec& unknown_weight_vertices);
99
    bool _verify_weight(int comp_index, Vertex art_point, int weight);
100
    void print_weight();
101

    
102
    // Calculate Betweenness Centrality
103
    void findBetweennessCentrality();
104
    void printBetweennessCentrality();
105

    
106
    // Function used in debugging
107
    void _print_art_points();
108
    void _test_set_difference();
109

    
110
};
111

    
112

    
113
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H