Revision 437fd680

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
custompackages/graph-parser/src/bi_connected_components.h
15 15

  
16 16

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

  
20 20
typedef map<string, vector<int> > VertexIdToComponentStdMap;
21 21
typedef boost::associative_property_map<VertexIdToComponentStdMap> VertexIdToComponentMap;
......
38 38
    void init();
39 39

  
40 40
    // Getter functions
41
    set<string> const& all_art_points_id() const;
42
    int num_of_vertices() const;
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;
43 45

  
44 46
    // SUB-COMPONENT
45 47
    void FindBiConnectedComponents();
......
53 55

  
54 56
    // BETWEENNESS CENTRALITY
55 57
    void CalculateBetweennessCentrality();
56

  
57
    // HELPERS
58
    int num_of_bcc();
58
    void initialize_betweenness_centrality();
59
    void calculate_bc_inter();
60
    void finalize_betweenness_centrality();
59 61

  
60 62
    // HELPERS FOR OUTPUTTING RESULT
61 63
    void print();
......
80 82
    ComponentVec component_vec_;
81 83
    ComponentMap component_map_;
82 84
    vector<Vertex> art_points_;
85
    StringSet all_art_points_id_;
83 86

  
84 87
    int num_of_bcc_ = -1;
85 88
    int num_of_vertices_ = -1;
86 89

  
87
    StringSet all_art_points_id_;
88

  
89 90
    std::queue<QueueElem> Q;
90 91

  
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

  
92
    // bc_score_ will be updated gradually, first with the score for non art points, and then the score for art points
93
    NameToDoubleMap bc_score_;
94
    NameToDoubleMap bc_sum_art_points_; // summing all the bc score for articulation points
95
    NameToDoubleMap bc_inter_;
105 96
};
106 97

  
107

  
108 98
#endif //GRAPH_PARSER_BI_CONNECTED_COMPONENTS_H
custompackages/graph-parser/src/common.h
57 57

  
58 58
typedef map<Vertex, size_t> VertexIndexStdMap;
59 59
// This property map is an adaptor that converts any type that is a model of Unique Associative Container such as std::map into a mutable Lvalue Property Map.
60
typedef boost::associative_property_map<VertexIndexStdMap> VertexIndexMap;
60
typedef boost::associative_property_map<VertexIndexStdMap> VertexIndexPMap;
61 61

  
62 62
typedef map<Edge, size_t> EdgeIndexStdMap;
63
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeIndexMap;
63
typedef boost::associative_property_map<EdgeIndexStdMap> EdgeIndexPMap;
64 64

  
65 65
typedef std::vector<Vertex> VertexVec;
66 66
typedef std::vector<Vertex>::iterator VertexVecIter;
......
69 69
typedef std::map<Vertex, int>::iterator VertexMapIter;
70 70

  
71 71
typedef std::map<std::string, int> NameToIntMap;
72
typedef std::map<std::string, double> NameToDoubleMap;
72 73

  
73 74
typedef std::vector<std::string> StringVec;
74 75
typedef std::vector<std::string>::iterator StringVecIter;
......
77 78
typedef std::set<std::string>::iterator StringSetIter;
78 79

  
79 80
typedef std::vector<double> CentralityVec;
80
typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
81
typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexPMap> CentralityPMap;
81 82

  
82 83
#endif //GRAPH_PARSER_COMMON_H
83 84

  
custompackages/graph-parser/src/graph_manager.cpp
1 1
#include "graph_manager.h"
2 2

  
3
// CONSTRUCTOR
3 4
GraphManager::GraphManager() {
4
    v_index_map_ = VertexIndexMap(v_index_std_map_);
5
    e_index_map_ = EdgeIndexMap(e_index_std_map_);
5
    v_index_pmap_ = VertexIndexPMap(v_index_std_map_);
6
    e_index_pmap_ = EdgeIndexPMap(e_index_std_map_);
6 7
}
7 8

  
8 9
GraphManager::GraphManager(const GraphManager& other) {
9 10
    cout << "\n\n*******COPY CONSTRUCTOR******\n\n";
10 11
    g_ = other.g_;
11
    reset_v_id_vertex_map();
12
    reset_v_index_map();
13
    reset_e_index_map();
12
    ResetVerticesAndEdgesIndexMap();
14 13
}
15 14

  
16 15
GraphManager& GraphManager::operator=(GraphManager& rhs) {
17 16
    cout << "\n\n*******ASSIGNMENT OPERATOR******\n\n";
18 17
    g_ = rhs.g_;
19
    reset_v_id_vertex_map();
20
    reset_v_index_map();
21
    reset_e_index_map();
18
    ResetVerticesAndEdgesIndexMap();
22 19

  
23 20
    return *this;
24 21
}
25 22

  
23
// GETTERS
24
const VertexIndexPMap& GraphManager::v_index_pmap() const {
25
    return v_index_pmap_;
26
}
27

  
28
const EdgeIndexPMap& GraphManager::e_index_pmap() const {
29
    return e_index_pmap_;
30
}
31
NameToIntMap const& GraphManager::v_id_index_map() const {
32
    return v_id_index_map_;
33
}
34

  
35
// UPDATE GRAPHS
26 36
void GraphManager::AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep) {
27 37
    // cout << "add edge GM " << vp1.label << " - " << vp2.label << endl;
28 38

  
......
37 47
    catch (exception& e) {
38 48
        v1 = boost::add_vertex(vp1, g_);
39 49
        v_id_vertex_map_[s1] = v1;
40
        update_v_index_map(v1);
50
        update_v_index_pmap(v1);
41 51
    }
42 52
    try {
43 53
        v2 = get_vertex_from_id(s2);
......
45 55
    catch (exception& e) {
46 56
        v2 = boost::add_vertex(vp2, g_);
47 57
        v_id_vertex_map_[s2] = v2;
48
        update_v_index_map(v2);
58
        update_v_index_pmap(v2);
49 59
    }
50 60

  
51 61
    Edge e;
52 62
    bool inserted;
53 63
    boost::tie(e, inserted) = boost::add_edge(v1, v2, ep, g_);
54
    update_e_index_map(e);
55
    // print_e_index_map();
64
    update_e_index_pmap(e);
65
}
56 66

  
57
    // Print the VertexIndexMap and EdgeIndexMap
58
    // print_v_index_map();
59
    // graphext::print_v_index_map(g_, v_index_map_);
67
void GraphManager::ResetVerticesAndEdgesIndexMap() {
68
    reset_v_index_pmap();
69
    reset_v_id_vertex_map();
70
    // The line below must be called after reset_v_index_pmap()
71
    reset_v_id_index_map();
72

  
73
    reset_e_index_pmap();
60 74
}
61 75

  
76
// HELPERS
62 77
bool GraphManager::vertex_existed(string s) {
63 78
    std::map<std::string, Vertex>::iterator it;
64 79
    it = v_id_vertex_map_.find(s);
......
74 89
    }
75 90
}
76 91

  
77
void GraphManager::ResetVerticesAndEdgesIndexMap() {
78
    v_index_std_map_.erase(v_index_std_map_.begin(), v_index_std_map_.end());
79
    e_index_std_map_.erase(e_index_std_map_.begin(), e_index_std_map_.end());
80
    int i;
81

  
82
    // Reset VertexIndexMap
83
    i = 0;
84
    BGL_FORALL_VERTICES(v, g_, Graph) {
85
        boost::put(v_index_map_, v, i);
86
        ++i;
92
int GraphManager::get_index_from_id(string s) {
93
    if (vertex_existed(s)) {
94
        return v_id_index_map_[s];
87 95
    }
88

  
89
    // Reset EdgeIndexMap
90
    i = 0;
91
    BGL_FORALL_EDGES(e, g_, Graph) {
92
        boost::put(e_index_map_, e, i);
93
        ++i;
96
    else {
97
        throw std::runtime_error("Vertex with id " + s + " is not found\n");
94 98
    }
95 99
}
96 100

  
97
std::ostream& operator<<(std::ostream& os, const GraphManager& gm) {
98
    cout << "Graph Manager: " << endl;
99
    outops::operator<<(cout, gm.g_);
100
    return os;
101
}
101
// OUTPUTTING THE RESULT
102
void GraphManager::print() {
103
    cout << "\nGraph Manager:\n";
104
    outops::operator<<(cout, g_);
105
    print_v_index_pmap();
106
    print_e_index_pmap();
102 107

  
103
void GraphManager::print_v_index_map() {
104
    graphext::print_v_index_map(g_, v_index_map_);
108
    cout << "v_id_index_map:\n";
109
    outops::operator<< <int>(cout, v_id_index_map_);
105 110
}
106 111

  
107
void GraphManager::print_e_index_map() {
108
    std::list<std::string> outputs;
109
    BGL_FORALL_EDGES_T(e, g_, Graph) {
110
        int index = boost::get(e_index_map_, e);
111
        std::string source_id = g_[boost::source(e, g_)].id;
112
        std::string target_id = g_[boost::target(e, g_)].id;
113
        outputs.push_back("edge (" + source_id + ", " + target_id + ")" + ": " + std::to_string(index));
114
    }
115

  
116
    using namespace boost::spirit::karma;
117
    cout << "Edge Index Map:\n";
118
    cout << format("[\n  " << (auto_ % "\n  ") << "\n]\n", outputs);
112
void GraphManager::print_v_index_pmap() {
113
    graphext::print_v_index_pmap(g_, v_index_pmap_);
119 114
}
120 115

  
121
const VertexIndexMap& GraphManager::v_index_map() const {
122
    return v_index_map_;
116
void GraphManager::print_e_index_pmap() {
117
    graphext::print_e_index_pmap(g_, e_index_pmap_);
123 118
}
124 119

  
125
const EdgeIndexMap& GraphManager::e_index_map() const {
126
    return e_index_map_;
120
std::ostream& operator<<(std::ostream& os, const GraphManager& gm) {
121
    cout << "\nGraph Manager: " << endl;
122
    outops::operator<<(cout, gm.g_);
123

  
124
    cout << "v_id_index_map:\n";
125
    outops::operator<< <int>(cout, gm.v_id_index_map());
126
    return os;
127 127
}
128 128

  
129
// Private Functions
129 130
void GraphManager::reset_v_id_vertex_map() {
130 131
    v_id_vertex_map_ = NameVertexMap();
131 132
    BGL_FORALL_VERTICES(v, g_, Graph) {
......
134 135
    }
135 136
}
136 137

  
137
void GraphManager::reset_v_index_map() {
138
void GraphManager::reset_v_id_index_map() {
139
    v_id_index_map_ = NameToIntMap();
140
    BGL_FORALL_VERTICES(v, g_, Graph) {
141
        int index = boost::get(v_index_pmap_, v);
142
        string name = g_[v].id;
143
        v_id_index_map_[name] = index;
144
    }
145
}
146

  
147
void GraphManager::reset_v_index_pmap() {
138 148
    v_index_std_map_ = VertexIndexStdMap();
139
    v_index_map_ = VertexIndexMap(v_index_std_map_);
149
    v_index_pmap_ = VertexIndexPMap(v_index_std_map_);
140 150
    int i = 0;
141 151
    BGL_FORALL_VERTICES(v, g_, Graph) {
142
        boost::put(v_index_map_, v, i);
152
        boost::put(v_index_pmap_, v, i);
143 153
        ++i;
144 154
    }
145 155
}
146 156

  
147
void GraphManager::reset_e_index_map() {
157
void GraphManager::reset_e_index_pmap() {
148 158
    e_index_std_map_ = EdgeIndexStdMap();
149
    e_index_map_ = EdgeIndexMap(e_index_std_map_);
159
    e_index_pmap_ = EdgeIndexPMap(e_index_std_map_);
150 160
    int i = 0;
151 161
    BGL_FORALL_EDGES(e, g_, Graph) {
152
        boost::put(e_index_map_, e, i);
162
        boost::put(e_index_pmap_, e, i);
153 163
        ++i;
154 164
    }
155 165
}
156 166

  
157
void GraphManager::update_v_index_map(Vertex new_vertex) {
167
void GraphManager::update_v_index_pmap(Vertex new_vertex) {
168
    // NOTE: this function might not perform correctly for vecS
158 169
    int index = boost::num_vertices(g_);
159 170
    v_index_std_map_[new_vertex] = index - 1;
160 171
}
161 172

  
162
void GraphManager::update_e_index_map(Edge new_edge) {
173
void GraphManager::update_e_index_pmap(Edge new_edge) {
163 174
    int index = boost::num_edges(g_);
164 175
    e_index_std_map_[new_edge] = index - 1;
165 176
}
custompackages/graph-parser/src/graph_manager.h
14 14
    typedef boost::edge_bundle_type<Graph>::type EdgeProperties; // aka Link in common.h
15 15
    typedef std::map<std::string, Vertex> NameVertexMap;
16 16

  
17
    // CONSTRUCTOR
17 18
    GraphManager(); // constructor
18 19
    GraphManager(const GraphManager& other); // copy constructor
19 20
    GraphManager& operator=(GraphManager& rhs); // assignment operator
20 21
    // check out more here: http://www.cplusplus.com/articles/y8hv0pDG/
21 22

  
23
    // GETTERS
24
    const VertexIndexPMap& v_index_pmap() const;
25
    const EdgeIndexPMap& e_index_pmap() const;
26
    NameToIntMap const& v_id_index_map() const;
27

  
28
    // UPDATE GRAPH
22 29
    void AddEdge(VertexProperties vp1, VertexProperties vp2, EdgeProperties ep);
30
    void ResetVerticesAndEdgesIndexMap();
31

  
32
    // HELPERS
23 33
    bool vertex_existed(string s);
24 34
    const Vertex& get_vertex_from_id(string s);
35
    int get_index_from_id(string s);
25 36

  
26
    StringSet vertices_id();
27

  
28
    void ResetVerticesAndEdgesIndexMap();
29 37

  
30
    // Function to print results
38
    // OUTPUTTING THE RESULT
31 39
    // TODO: checkout utility.h, I can't overload << operator to output
32 40
    // the correct result. Therefore, I use print() ufnction as a replacement.
33
    void print_v_index_map();
34
    void print_e_index_map();
35

  
36
    // Getter
37
    const VertexIndexMap& v_index_map() const;
38
    const EdgeIndexMap& e_index_map() const;
39

  
40
    // Output Operators
41
    void print();
42
    void print_v_index_pmap();
43
    void print_e_index_pmap();
41 44
    friend std::ostream& operator<<(std::ostream& os, const GraphManager& gm);
42 45

  
46
    // Variables
43 47
    Graph g_;
44 48
private:
49
    void reset_v_index_pmap();
45 50
    void reset_v_id_vertex_map();
46
    void reset_v_index_map();
47
    void reset_e_index_map();
48
    void update_v_index_map(Vertex new_vertex);
49
    void update_e_index_map(Edge new_edge);
51
    void reset_v_id_index_map(); // must be called after reset_v_index_pmap()
52

  
53
    void reset_e_index_pmap();
54
    void update_v_index_pmap(Vertex new_vertex);
55
    void update_e_index_pmap(Edge new_edge);
50 56

  
57
    // VARIABLES
51 58
    NameVertexMap v_id_vertex_map_;
59
    NameToIntMap v_id_index_map_;
52 60

  
53
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
61
    // VertexIndexPMap - since we use listS instead of vecS in Graph, this one maps each vertex to an id
54 62
    VertexIndexStdMap v_index_std_map_;
55
    VertexIndexMap v_index_map_; //
63
    VertexIndexPMap v_index_pmap_; //
56 64

  
57
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
65
    // EdgeIndexPMap - boost will return the component id that each edge in the graph belongs to.
58 66
    EdgeIndexStdMap e_index_std_map_;
59
    EdgeIndexMap e_index_map_;
67
    EdgeIndexPMap e_index_pmap_;
60 68
};
61 69

  
62 70
#endif //GRAPH_PARSER_GRAPH_MANAGER_H
custompackages/graph-parser/src/main.cpp
71 71
void testHeuristic(string filePath) {
72 72
    GraphManager gm;
73 73
    readEdgeFileGraphManager(filePath, gm);
74
    BiConnectedComponents bcc(gm);
74
    gm.print();
75
    BiConnectedComponents bcc = BiConnectedComponents(gm);
76
    cout << bcc;
75 77
    cout << "DONE" << endl;
76 78
}
77 79

  
78 80
void testGraphManager(string filePath) {
79 81
    GraphManager gm;
80 82
    readEdgeFileGraphManager(filePath, gm);
81
    cout << gm;
82

  
83
    gm.ResetVerticesAndEdgesIndexMap();
84
    gm.print_v_index_map();
85

  
83
    gm.print();
86 84
}
87 85

  
88 86
int main(int, char *[]) {
custompackages/graph-parser/src/parser.cpp
135 135
            GraphManager::EdgeProperties ep = GraphManager::EdgeProperties(cost);
136 136

  
137 137
            gm.AddEdge(vp1, vp2, ep);
138

  
139 138
        }
140 139
    }
140
    gm.ResetVerticesAndEdgesIndexMap();
141 141
    inFile.close();
142 142
}
custompackages/graph-parser/src/sub_component.cpp
39 39
    return traffic_matrix_;
40 40
}
41 41

  
42
CentralityVec const& SubComponent::v_centrality_vec() const {
43
    return v_centrality_vec_;
44
}
45

  
42 46
/* CREATE SUB-COMPONENT */
43 47
void SubComponent::AddEdge(Router r1, Router r2, Link l) {
44 48
    gm_.AddEdge(r1, r2, l);
45 49
}
46 50

  
47 51
void SubComponent::FinalizeSubComponent(StringSet all_art_points_id) {
52
    // TODO: is there anyway to not have to call this function after the graph was created completely?
53
    gm_.ResetVerticesAndEdgesIndexMap();
54

  
48 55
    // Create set of vertices id
49 56
    graphext::id_of_all_vertices(gm_.g_, all_vertices_id_);
50 57

  
......
58 65
    // Create name -> index map
59 66
    int index = 0;
60 67
    for (string s : all_vertices_id_) {
61
        name_index_map_[s] = index;
68
        name_index_pmap_[s] = index;
62 69
        ++index;
63 70
    }
64 71
}
......
166 173
    cout << "Mark 1" << endl;
167 174

  
168 175
    boost::brandes_betweenness_centrality(gm_.g_,
169
        boost::centrality_map(v_centrality_map_).vertex_index_map(
170
            gm_.v_index_map())
176
        boost::centrality_map(v_centrality_pmap_).vertex_index_map(
177
            gm_.v_index_pmap())
171 178
    );
172 179

  
173 180
    cout << "Mark 2" << endl;
......
180 187

  
181 188
void SubComponent::initialize_betweenness_centrality() {
182 189
    v_centrality_vec_ = CentralityVec(num_of_vertices());
183
    v_centrality_map_ = CentralityMap(v_centrality_vec_.begin(), gm_.v_index_map());
190
    v_centrality_pmap_ = CentralityPMap(v_centrality_vec_.begin(), gm_.v_index_pmap());
191
}
192

  
193
double SubComponent::get_betweenness_centrality(string name) {
194
    // There are 2 ways to retrieve the BC score
195
    // 1st way - through v_centrality_vec_
196
    int index = gm_.get_index_from_id(name);
197
    cout << "    index = " << index << endl;
198
    return v_centrality_vec_.at(index);
199
}
200

  
201
double SubComponent::get_betweenness_centrality(Vertex v) {
202
    // 2nd way - uncomment to use v_centrality_pmap
203
    return boost::get(v_centrality_pmap_, v);
184 204
}
185 205

  
186 206
/* HELPERS */
......
190 210

  
191 211
int SubComponent::index_of_vertex_id(string vertex_id) {
192 212
    // TODO: might throw exception here
193
    return name_index_map_[vertex_id];
213
    return name_index_pmap_[vertex_id];
194 214
}
195 215

  
196 216
bool SubComponent::vertex_exists(string name) {
......
209 229
}
210 230

  
211 231
/* HELPERS FOR OUTPUTTING RESULT */
212
void SubComponent::print_traffic_matrix() {
232
void SubComponent::print() {
233
    cout << "Sub-component:" << endl;
234
    gm_.print();
235

  
236
    cout << "\nArticulation points ID:\n";
237
    outops::operator<<(cout, art_points_id());
238

  
239
    cout << "\nNormal Vertices ID:\n";
240
    outops::operator<<(cout, all_vertices_id());
213 241

  
242
    cout << "\nLink Weight:\n";
243
    outops::operator<< <int> (cout, weight_map());
244
    // printhelper::for_map<string, int>(sc.weight_map());
245

  
246
    cout << "\nTraffic Matrix:\n";
247
    outops::operator<<(cout, traffic_matrix());
248

  
249
    cout << "\nBetweenness Centrality:\n";
250
    outops::operator<< <double>(cout, v_centrality_vec());
214 251
}
215 252

  
216 253
std::ostream& operator<<(std::ostream& os, const SubComponent& sc) {
......
224 261
    outops::operator<<(cout, sc.all_vertices_id());
225 262

  
226 263
    cout << "\nLink Weight:\n";
227
    outops::operator<<(cout, sc.weight_map());
264
    outops::operator<< <int> (cout, sc.weight_map());
228 265
    // printhelper::for_map<string, int>(sc.weight_map());
229 266

  
230 267
    cout << "\nTraffic Matrix:\n";
231 268
    outops::operator<<(cout, sc.traffic_matrix());
232 269

  
270
    cout << "\nBetweenness Centrality:\n";
271
    outops::operator<< <double>(cout, sc.v_centrality_vec());
272

  
233 273
    return os;
234 274
}
custompackages/graph-parser/src/sub_component.h
17 17
class SubComponent {
18 18
public:
19 19
    typedef std::vector<double> CentralityVec;
20
    typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexMap> CentralityMap;
20
    typedef boost::iterator_property_map<CentralityVec::iterator, VertexIndexPMap> CentralityPMap;
21 21

  
22 22
    SubComponent();
23 23

  
......
32 32

  
33 33
    vector< vector< int > > const& traffic_matrix() const;
34 34

  
35
    CentralityVec const& v_centrality_vec() const;
36

  
35 37
    // CREATE SUB-COMPONENT
36 38
    void AddEdge(Router r1, Router r2, Link l);
37 39
    void FinalizeSubComponent(StringSet all_art_points_id);
......
51 53
    // BETWEENNESS CENTRALITY
52 54
    void CalculateBetweennessCentrality();
53 55
    void initialize_betweenness_centrality();
56
    double get_betweenness_centrality(string name);
57
    double get_betweenness_centrality(Vertex v);
54 58

  
55 59
    // HELPERS
56 60
    int num_of_vertices();
......
59 63
    string first_vertex_id_with_unknown_weight();
60 64

  
61 65
    // HELPERS FOR OUTPUTTING RESULT
62
    void print_traffic_matrix();
66
    void print();
63 67
    friend std::ostream& operator<<(std::ostream& os, const SubComponent& sc);
68
    void print_traffic_matrix();
64 69

  
65 70

  
66 71
    // OLD CODE
......
79 84
    StringSet all_vertices_id_;
80 85
    StringSet art_points_id_;
81 86
    StringSet non_art_points_id_; // vertices that are not articulation points
82
    NameToIntMap name_index_map_;
87
    NameToIntMap name_index_pmap_;
83 88

  
84 89

  
85 90
    NameToIntMap weight_map_;
......
88 93
    vector<vector<int> > traffic_matrix_;
89 94

  
90 95
    CentralityVec v_centrality_vec_;
91
    CentralityMap v_centrality_map_;
96
    CentralityPMap v_centrality_pmap_;
92 97

  
93 98

  
94 99
};
95

  
96

  
97 100
#endif //GRAPH_PARSER_SUB_COMPONENT_H
custompackages/graph-parser/src/utility.cpp
12 12
                "---------- " << boost::num_vertices(g) << " vertices\n"
13 13
                "---------- " << boost::num_edges(g) << " edges\n";
14 14

  
15
        std::set<std::string> verticesSet;
16
        BGL_FORALL_VERTICES_T(v, g, Graph) verticesSet.insert(g[v].id);
15
        std::vector<std::string> verticesVec;
16
        BGL_FORALL_VERTICES(v, g, Graph) verticesVec.push_back(g[v].id);
17 17

  
18 18
        std::vector<std::string> edgesVec;
19 19
        std::vector<double> costsVec;
20
        BGL_FORALL_EDGES_T(e, g, Graph) {
20
        BGL_FORALL_EDGES(e, g, Graph) {
21 21
            std::string s = "(" + g[e.m_source].id + ", " + g[e.m_target].id + ") - " + std::to_string(g[e].cost);
22 22
            edgesVec.push_back(s);
23 23
            costsVec.push_back(g[e].cost);
......
26 26
        using namespace boost::spirit::karma;
27 27
        os <<   "Vertices:\n"
28 28
                "  ";
29
        os << format("(" << auto_ % ", " << ") ", verticesSet);
29
        os << format("(" << auto_ % ", " << ") ", verticesVec);
30 30
        os << "\n";
31 31

  
32 32
        os <<   "Edges:\n";
......
36 36
        return os;
37 37
    }
38 38

  
39
    std::ostream& operator<<(std::ostream& os, std::pair<const Graph&, const VertexIndexMap&> p) {
39
    std::ostream& operator<<(std::ostream& os, std::pair<const Graph&, const VertexIndexPMap&> p) {
40 40
        // ERROR: wrong output.
41 41
        // I think it's because of copy constructor.
42 42
        // Check out shell_output/w14
43 43

  
44 44
        // Calling example:
45
        // outops::operator<<(cout, std::pair<const Graph&, const VertexIndexMap&>(g_, v_index_map_));
45
        // outops::operator<<(cout, std::pair<const Graph&, const VertexIndexPMap&>(g_, v_index_pmap_));
46 46
        Graph g = p.first;
47
        VertexIndexMap v_index_map = p.second;
47
        VertexIndexPMap v_index_map = p.second;
48 48

  
49 49
        std::list<std::string> outputs;
50 50
        BGL_FORALL_VERTICES_T(v, g, Graph) {
......
62 62
        return os;
63 63
    }
64 64

  
65
    std::ostream& operator<<(std::ostream& os, const std::map<string, int>& m) {
66
        // similar to printhelper::for_map()
67
        os << "cout << std::map\n";
68
        std::map<string, int>::const_iterator iter;
69
        for (iter = m.begin(); iter != m.end(); ++iter) {
70
            os << (*iter).first << ": " << (*iter).second << endl;
71
        }
72
        os << endl;
73

  
74
        return os;
75
    }
76

  
77 65
    std::ostream& operator<<(std::ostream& os, const vector< vector< int> >& data) {
78 66
        cout << "cout << vector<vector<int> >\n";
79 67
        int row_size = data.size();
......
113 101
        cout << format("[\n  " << (auto_ % "\n  ") << "\n]\n", outputs);
114 102
    }
115 103

  
116
    void print_v_index_map(const Graph& g, const VertexIndexMap& v_index_map) {
117
        cout << "Vertex Index Map:\n";
118

  
104
    void print_v_index_pmap(const Graph& g, const VertexIndexPMap& v_index_pmap) {
119 105
        std::list<std::string> outputs;
120 106
        BGL_FORALL_VERTICES_T(v, g, Graph) {
121
            int index = boost::get(v_index_map, v);
107
            int index = boost::get(v_index_pmap, v);
122 108
            std::string vertex_id = g[v].id;
123
            cout << v << endl;
109
            // Uncomment to print the address of vertex v
110
            // cout << v << endl;
124 111
            outputs.push_back(vertex_id + ": " + std::to_string(index));
125 112
        }
126 113

  
127 114
        using namespace boost::spirit::karma;
115
        cout << "Vertex Index Map:\n";
116
        cout << format("[\n  " << (auto_ % "\n  ") << "\n]\n", outputs);
117
    }
118

  
119
    void print_e_index_pmap(const Graph& g, const EdgeIndexPMap& e_index_pmap) {
120
        std::list<std::string> outputs;
121
        BGL_FORALL_EDGES_T(e, g, Graph) {
122
            int index = boost::get(e_index_pmap, e);
123
            std::string source_id = g[boost::source(e, g)].id;
124
            std::string target_id = g[boost::target(e, g)].id;
125
            outputs.push_back("edge (" + source_id + ", " + target_id + ")" + ": " + std::to_string(index));
126
        }
127

  
128
        using namespace boost::spirit::karma;
129
        cout << "Edge Index Map:\n";
128 130
        cout << format("[\n  " << (auto_ % "\n  ") << "\n]\n", outputs);
129 131
    }
130 132
}
custompackages/graph-parser/src/utility.h
17 17
    std::ostream& operator<<(std::ostream& os, const Graph& g);
18 18

  
19 19
    // I have to use pair to add more than one argument for cout operator<<
20
    std::ostream& operator<<(std::ostream& os, std::pair<const Graph&, const VertexIndexMap&> p);
20
    std::ostream& operator<<(std::ostream& os, std::pair<const Graph&, const VertexIndexPMap&> p);
21 21

  
22
    template <typename T> // declared in utitlity.tpp
23
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
22
    // For set
23
    template <typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& data);
24 24

  
25
    std::ostream& operator<<(std::ostream& os, const std::map<string, int>& m);
25
    // For vector
26
    template <typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& data);
26 27

  
28
    // For map
29
    template <typename T> std::ostream& operator<<(std::ostream& os, const std::map<string, T>& data);
30

  
31
    // For 2-D vector
27 32
    std::ostream& operator<<(std::ostream& os, const vector< vector< int> >& data);
28 33
}
29 34

  
......
38 43
    void id_of_some_vertices(const Graph& g, const Container& container, std::set<std::string>& r);
39 44

  
40 45
    void print_v_index_std_map(const Graph& g, const VertexIndexStdMap& v_index_std_map);
41
    void print_v_index_map(const Graph& g, const VertexIndexMap& v_index_map);
46
    void print_v_index_pmap(const Graph& g, const VertexIndexPMap& v_index_pmap);
47
    void print_e_index_pmap(const Graph& g, const EdgeIndexPMap& e_index_pmap);
42 48
}
43 49

  
44 50
namespace setops {
custompackages/graph-parser/src/utility.tpp
1 1
namespace outops
2 2
{
3 3
    template <typename T>
4
    std::ostream& operator<<(std::ostream& os, const std::set<T>& s)
5
    {
4
    std::ostream& operator<<(std::ostream& os, const std::set<T>& data) {
6 5
        using namespace boost::spirit::karma;
7
        os << format("(" << (auto_ % "\n  ") << ")", s);
6
        os << format("(" << (auto_ % "\n  ") << ")", data);
7
        os << endl;
8
    }
9

  
10
    template <typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& data) {
11
        os << "cout << std::vector<T>\n";
12

  
13
        using namespace boost::spirit::karma;
14
        os << format("(" << (auto_ % "\n  ") << ")", data);
15
        os << endl;
16
    }
17

  
18
    template <typename T>
19
    std::ostream& operator<<(std::ostream& os, const std::map<string, T>& data) {
20
        os << "cout << std::map<string, T>\n";
21
        typename std::map<string, T>::const_iterator iter;
22
        for (iter = data.begin(); iter != data.end(); ++iter) {
23
            os << (*iter).first << ": " << (*iter).second << endl;
24
        }
8 25
        os << endl;
9 26
    }
10 27
}
......
22 39
}
23 40
namespace graphext {
24 41
    template <typename Container>
25
    void id_of_some_vertices(const Graph& g, const Container& container, std::set<std::string>& r)
26
    {
42
    void id_of_some_vertices(const Graph& g, const Container& container, std::set<std::string>& r) {
27 43
        /*
28 44
        ** Find id for a vec
29 45
        */
......
35 51

  
36 52
namespace setops {
37 53
    // From http://stackoverflow.com/questions/8175933/to-compare-two-boost-graph-having-same-vertices
38
    template <typename T> std::set<T> operator-(const std::set<T>& a, const std::set<T>& b)
39
    {
54
    template <typename T> std::set<T> operator-(const std::set<T>& a, const std::set<T>& b) {
40 55
        std::set<T> r;
41 56
        std::set_difference(
42 57
                a.begin(), a.end(),
......
46 61
        return r;
47 62
    }
48 63

  
49
    template <typename T> std::set<T> operator/(const std::set<T>& a, const std::set<T>& b)
50
    {
64
    template <typename T> std::set<T> operator/(const std::set<T>& a, const std::set<T>& b) {
51 65
        std::set<T> r;
52 66
        std::set_intersection(
53 67
                a.begin(), a.end(),

Also available in: Unified diff