root / custompackages / graph-parser / src / bi_connected_components.h @ d5b7a27f
History | View | Annotate | Download (3.91 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<int> ComponentVec; // use int instead of edges_size_type because I want to set default value to be -1 |
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 |
NameToDoubleMap const& bc_relative_score() const; |
46 |
|
47 |
// Auto run
|
48 |
void run();
|
49 |
|
50 |
// SUB-COMPONENT
|
51 |
void FindBiConnectedComponents();
|
52 |
|
53 |
// LINK WEIGHT - calculation for all sub-components
|
54 |
void CalculateLinkWeight();
|
55 |
void CalculateLinkWeightReversed();
|
56 |
|
57 |
// TRAFFIC MATRIX - calculation for all sub-components
|
58 |
void CalculateTrafficMatrix();
|
59 |
|
60 |
// BETWEENNESS CENTRALITY HEURISTIC
|
61 |
void CalculateBetweennessCentralityHeuristic();
|
62 |
|
63 |
// BETWEENNESS CENTRALITY
|
64 |
void CalculateBetweennessCentrality(bool targets_inclusion = true); |
65 |
|
66 |
// HELPERS FOR OUTPUTTING RESULT
|
67 |
void print_all_sub_components();
|
68 |
void print_biconnected_components();
|
69 |
void print_betweenness_centrality();
|
70 |
void print_betweenness_centrality_heuristic();
|
71 |
|
72 |
void write_all_betweenness_centrality(string filepath);
|
73 |
|
74 |
void print();
|
75 |
friend std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs);
|
76 |
|
77 |
// Public variables
|
78 |
GraphManager gm_; |
79 |
typedef vector<SubComponent> Component_t;
|
80 |
typedef vector<SubComponent>::iterator ComponentIter_t;
|
81 |
Component_t BCCs; |
82 |
|
83 |
private:
|
84 |
// SUB-COMPONENT
|
85 |
void reset_num_of_bcc();
|
86 |
void CreateSubComponents();
|
87 |
|
88 |
// 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 |
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 |
|
105 |
// Private variables
|
106 |
ComponentVec component_vec_; |
107 |
ComponentMap component_map_; |
108 |
vector<Vertex> art_points_; |
109 |
StringSet all_art_points_id_; |
110 |
|
111 |
int num_of_bcc_ = -1; |
112 |
int num_of_vertices_ = -1; |
113 |
|
114 |
std::queue<QueueElem> Q; |
115 |
|
116 |
// bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
|
117 |
// Betweenness Centrality Heuristic
|
118 |
NameToDoubleMap bc_score_; |
119 |
NameToDoubleMap bc_relative_score_; |
120 |
NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
|
121 |
NameToDoubleMap bc_inter_; |
122 |
|
123 |
// Betweenness Centrality - standard calculation
|
124 |
CentralityVec v_centrality_vec_; |
125 |
CentralityPMap v_centrality_pmap_; |
126 |
}; |
127 |
|
128 |
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H |