Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.81 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, EdgeIndexMap> 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
    set<string> const& all_art_points_id() const;
42
    int num_of_vertices() const;
43

    
44
    // SUB-COMPONENT
45
    void FindBiConnectedComponents();
46
    void CreateSubComponents();
47

    
48
    // LINK WEIGHT - calculation for all sub-components
49
    void CalculateLinkWeight();
50

    
51
    // TRAFFIC MATRIX - calculation for all sub-components
52
    void CalculateTrafficMatrix();
53

    
54
    // HELPERS
55
    int num_of_bcc();
56

    
57
    // HELPERS FOR OUTPUTTING RESULT
58
    void print();
59
    friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
60

    
61
    // Public variables
62
    GraphManager gm_;
63
    typedef vector<SubComponent> Component_t;
64
    typedef vector<SubComponent>::iterator ComponentIter_t;
65
    Component_t BCCs;
66

    
67
private:
68
    // LINK WEIGHT - calculation for all sub-components
69
    void initialize_weight();
70
    void initialize_queue();
71
    void process_component_vertex_pair(int comp_index, string vertex_id);
72
    void process_vertex_component_pair(int comp_index, string vertex_id);
73
    void find_unknown_weight_wrt_art_point(string vertex_id);
74
    void find_unknown_weight_wrt_component(int comp_index);
75

    
76
    // Private variables
77
    ComponentVec component_vec_;
78
    ComponentMap component_map_;
79
    vector<Vertex> art_points_;
80

    
81
    int num_of_bcc_ = -1;
82
    int num_of_vertices_ = -1;
83

    
84
    StringSet all_art_points_id_;
85

    
86
    std::queue<QueueElem> Q;
87

    
88
    // Old code
89
    void processArtPoints();
90
    void testProcessArtPoints();
91

    
92
    VertexVec get_normal_vertices_for_component(int comp_index);
93

    
94
    // Calculate Betweenness Centrality
95
    void findBetweennessCentrality();
96
    void printBetweennessCentrality();
97

    
98
    // Function used in debugging
99
    void _print_art_points();
100
    void _test_set_difference();
101

    
102
};
103

    
104

    
105
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H