Revision 437fd680 custompackages/graph-parser/src/bi_connected_components.cpp

View differences:

custompackages/graph-parser/src/bi_connected_components.cpp
19 19
    num_of_vertices_ = boost::num_vertices(gm_.g_);
20 20

  
21 21
    component_vec_ = ComponentVec(boost::num_edges(gm_.g_), 0);
22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_map());
22
    component_map_ = ComponentMap(component_vec_.begin(), gm_.e_index_pmap());
23 23
}
24 24

  
25 25
/* GETTER */
26
int const BiConnectedComponents::num_of_bcc() {
27
    if (num_of_bcc_ == -1) { // calculate it
28
        // +1 to counteract for the zero-indexing
29
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
30
    }
31

  
32
    return num_of_bcc_;
33
}
34

  
35
int const BiConnectedComponents::num_of_vertices() const {
36
    return num_of_vertices_;
37
}
38

  
26 39
StringSet const& BiConnectedComponents::all_art_points_id() const {
27 40
    return all_art_points_id_;
28 41
}
29 42

  
43
NameToDoubleMap const& BiConnectedComponents::bc_score() const {
44
    return bc_score_;
45
}
46

  
30 47
/* SUB-COMPONENT */
31 48
void BiConnectedComponents::FindBiConnectedComponents() {
32 49
    cout << "Running FindBiConnectedComponents" << endl;
33 50

  
34 51
    boost::biconnected_components(gm_.g_, component_map_,
35 52
                                  back_inserter(art_points_),
36
                                  boost::vertex_index_map(gm_.v_index_map()));
53
                                  boost::vertex_index_map(gm_.v_index_pmap()));
37 54

  
38 55
    // Set some variables
39 56
    graphext::id_of_some_vertices(gm_.g_, art_points_, all_art_points_id_);
......
54 71
    cout << "Calculate Betweenness Centrality\n";
55 72
    CalculateBetweennessCentrality();
56 73

  
74
    // Print all the sub components
57 75
    print();
58 76
}
59 77

  
......
104 122

  
105 123
/* BETWEENNESS CENTRALITY */
106 124
void BiConnectedComponents::CalculateBetweennessCentrality() {
125
    cout << "BETWEENNESS CENTRALITY\n";
126

  
127
    initialize_betweenness_centrality();
128

  
107 129
    for (int i = 0; i < num_of_bcc_; ++i) {
130
        cout << "BC for component " << i << endl;
108 131
        BCCs[i].CalculateBetweennessCentrality();
109 132
    }
133

  
134
    double score;
135
    // Sum the BC for each sub-component
136
    for (int i = 0; i < num_of_bcc_; ++i) {
137
        // For non articulation points
138
        for (string id: BCCs[i].non_art_points_id()) {
139
            score = BCCs[i].get_betweenness_centrality(id);
140
            cout << "id = " << id << ", score = " << score << endl;
141
            bc_score_[id] = score;
142
        }
143

  
144
        // For articulation points
145
        for (string id: BCCs[i].art_points_id()) {
146
            score = BCCs[i].get_betweenness_centrality(id);
147
            bc_sum_art_points_[id] += score;
148
        }
149
    }
150

  
151
    // Update the BC score for articulation points
152
    for (string id : all_art_points_id_) {
153
        bc_score_[id] = bc_sum_art_points_[id];
154

  
155
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
156
        // bc_score_[id] = bc_sum_art_points_[id] - bc_inter_[id];
157
    }
158

  
159
    cout << "DONE WITH BETWEENNESS CENTRALITY\n";
110 160
}
111 161

  
112
/* HELPERS */
113
int BiConnectedComponents::num_of_bcc() {
114
    if (num_of_bcc_ == -1) { // calculate it
115
        // +1 to counteract for the zero-indexing
116
        num_of_bcc_ = *std::max_element(component_vec_.begin(), component_vec_.end()) + 1;
162
void BiConnectedComponents::initialize_betweenness_centrality() {
163
    // Initialize bc_inter_ to be 0
164
    for (string id: all_art_points_id_) {
165
        bc_inter_[id] = 0;
117 166
    }
118 167

  
119
    return num_of_bcc_;
168
    StringSet all_vertices_id;
169
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id);
170

  
171
    // Initialize bc_sum_, bc_score_ to be 0
172
    for (string id: all_vertices_id) {
173
        bc_sum_art_points_[id] = 0;
174
        bc_score_[id] = 0;
175
    }
176
}
177

  
178
void BiConnectedComponents::calculate_bc_inter() {
179
    for (int i = 0; i < num_of_bcc_; ++i) {
180
        for (string id : BCCs[i].art_points_id()) {
181
            bc_inter_[id] += BCCs[i].get_weight_map(id) * BCCs[i].get_weight_reversed_map(id);
182
        }
183
    }
120 184
}
121 185

  
122 186
/* HELPERS FOR OUTPUTTING RESULT */
187

  
123 188
void BiConnectedComponents::print() {
124 189
    for (int i = 0; i < num_of_bcc(); ++i) {
125
        cout << BCCs[i] << endl;
190
        // cout << BCCs[i]; // Since I call another print() function inside, I cannot use cout
191
        BCCs[i].print();
126 192
    }
127 193
}
128 194

  
129 195
std::ostream& operator<<(std::ostream& os, const BiConnectedComponents& rhs) {
196
    cout << "MARK\n";
130 197
    cout << "\n\nBi-Connected Components\n\n";
131 198
    cout << rhs.gm_;
132 199

  
133 200
    cout << "\nArticulation points:\n";
134 201
    outops::operator<<(cout, rhs.all_art_points_id());
202

  
203
    cout << "\nBetweenness Centrality Score:\n";
204
    outops::operator<< <double>(cout, rhs.bc_score());
135 205
    return os;
136 206

  
137 207
    // TODO: output the result of BCC

Also available in: Unified diff