Revision cb770240 custompackages/graph-parser/src/bi_connected_components.h

View differences:

custompackages/graph-parser/src/bi_connected_components.h
8 8
#include <boost/graph/biconnected_components.hpp>
9 9
#include <queue>
10 10
#include "common.h"
11
#include "parser.h"
11
#include "parser.h" // ? check to remove
12 12
#include "utility.h"
13 13
#include "sub_component.h"
14
#include "graph_manager.h"
14 15

  
15 16

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

  
19
typedef map<Vertex, vector<int> > ArtPointComponentStdMap;
20
typedef boost::associative_property_map<ArtPointComponentStdMap> ArtPointComponentMap;
20
typedef map<string, vector<int> > VertexIdToComponentStdMap;
21
typedef boost::associative_property_map<VertexIdToComponentStdMap> VertexIdToComponentMap;
21 22

  
22
typedef std::map<int, vector<Vertex> > ComponentArtPointStdMap;
23
typedef boost::associative_property_map<ComponentArtPointStdMap> ComponentArtPointMap;
23
typedef std::map<int, vector<string> > ComponentToVertexIdStdMap;
24
typedef boost::associative_property_map<ComponentToVertexIdStdMap> ComponentToVertexIdMap;
24 25

  
25 26
typedef vector<vector<Vertex> > Bcc_t;
26 27
typedef vector<vector<Vertex> >::iterator BccIter_t;
27 28

  
28

  
29

  
30 29
typedef struct {
31 30
    int component_index;
32
    Vertex art_point;
31
    string vertex_id;
33 32
    string type;
34 33
} QueueElem;
35 34

  
36 35
class BiConnectedComponents {
37
private:
38
    // EdgeIndexMap - boost will return the component id that each edge in the graph belongs to.
39
    StdEdgeIndexMap e_index_std_map;
40
    EdgeIndexMap e_index_map;
41

  
42
    // VertexIndexMap - since we use listS instead of vecS, this one maps each vertex to an id
43
    StdVertexIndexMap v_index_std_map;
36
public:
37
    BiConnectedComponents(GraphManager &gm);
38
    void init();
44 39

  
45
    int num_of_bcc = -1;
40
    // Getter functions
41
    set<string> const& all_art_points_id() const;
42
    int num_of_vertices() const;
46 43

  
47
    std::queue<QueueElem> Q;
44
    // SUB-COMPONENT
45
    void FindBiConnectedComponents();
46
    void CreateSubComponents();
48 47

  
49
public:
50
    typedef vector<SubComponent> Component_t;
51
    typedef vector<SubComponent>::iterator ComponentIter_t;
48
    // LINK WEIGHT - calculation for all sub-components
49
    void CalculateLinkWeight();
52 50

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

  
55
    VertexIndexMap v_index_map;
56
    ComponentVec component_vec;
57
    ComponentMap component_map;
54
    // HELPERS
55
    int num_of_bcc();
58 56

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

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

  
64
    ArtPointComponentStdMap art_point_component_std_map;
65
    ArtPointComponentMap art_point_component_map;
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);
66 75

  
67
    ComponentArtPointStdMap component_art_point_std_map;
68
    ComponentArtPointMap component_art_point_map;
76
    // Private variables
77
    ComponentVec component_vec_;
78
    ComponentMap component_map_;
79
    vector<Vertex> art_points_;
69 80

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

  
71
    BiConnectedComponents(const Graph &g);
72
    void init();
73
    void findBiConnectedComponents();
74
    void createSubComponents();
75
    void print();
84
    StringSet all_art_points_id_;
76 85

  
77
    int num_bcc();
78
    void verticesInBCC();
79
    void testVerticesInBCC();
86
    std::queue<QueueElem> Q;
80 87

  
81
    bool hasVertex(Vertex v, int comp_index);
88
    // Old code
82 89
    void processArtPoints();
83 90
    void testProcessArtPoints();
84 91

  
85
    VertexVec get_art_points_for_component(int comp_index);
86
    vector<int> get_components_for_art_point(Vertex vertex);
87

  
88 92
    VertexVec get_normal_vertices_for_component(int comp_index);
89 93

  
90
    int num_of_vertices_in_component(int comp_index);
91

  
92
    // Calculate link weight (component tree weight)
93
    void compute_weight();
94
    void _initialize_weight();
95
    void _initialize_queue();
96
    void _find_unknown_weight_wrt_art_point(Vertex art_point);
97
    void _find_unknown_weight_wrt_component(int comp_index);
98
    void _find_unknown_weight_for_component(int comp_index, VertexVec& unknown_weight_vertices);
99
    bool _verify_weight(int comp_index, Vertex art_point, int weight);
100
    void print_weight();
101

  
102 94
    // Calculate Betweenness Centrality
103 95
    void findBetweennessCentrality();
104 96
    void printBetweennessCentrality();

Also available in: Unified diff