Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.88 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
    // BETWEENNESS CENTRALITY
55
    void CalculateBetweennessCentrality();
56

    
57
    // HELPERS
58
    int num_of_bcc();
59

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

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

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

    
79
    // Private variables
80
    ComponentVec component_vec_;
81
    ComponentMap component_map_;
82
    vector<Vertex> art_points_;
83

    
84
    int num_of_bcc_ = -1;
85
    int num_of_vertices_ = -1;
86

    
87
    StringSet all_art_points_id_;
88

    
89
    std::queue<QueueElem> Q;
90

    
91
    // Old code
92
    void processArtPoints();
93
    void testProcessArtPoints();
94

    
95
    VertexVec get_normal_vertices_for_component(int comp_index);
96

    
97
    // Calculate Betweenness Centrality
98
    void findBetweennessCentrality();
99
    void printBetweennessCentrality();
100

    
101
    // Function used in debugging
102
    void _print_art_points();
103
    void _test_set_difference();
104

    
105
};
106

    
107

    
108
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H