Statistics
| Branch: | Revision:

root / custompackages / graph-parser / src / simulation.cpp @ 4fe0cb58

History | View | Annotate | Download (6.27 KB)

1
#include <cstdlib>
2
#include <ctime>
3
#include <iostream>
4
#include <fstream>
5
#include <dirent.h>
6
#include <vector>
7
#include "bi_connected_components.h"
8
#include "centrality.h"
9
#include "graph_manager.h"
10
#include "parser.h"
11
using namespace std;
12

    
13
void get_all_files_in_directory(string dir_path, vector<string>& files, string with_extension) {
14
    DIR*    dir;
15
    dirent* pdir;
16

    
17
    dir = opendir(dir_path.c_str());
18

    
19
    while (pdir = readdir(dir)) {
20
        string filename = pdir->d_name;
21
        string::size_type idx;
22
        idx = filename.find('.');
23
        string extension = "";
24
        if (idx != string::npos) {
25
            extension = filename.substr(idx + 1);
26
        }
27

    
28
        if (extension.compare(with_extension) == 0) {
29
            files.push_back(filename);
30
            cout << filename << endl;
31
        }
32
    }
33
}
34

    
35
void calculate_brandes_bc(const GraphManager& gm, bool targets_inclusion) {
36
    CentralityVec v_centrality_vec = CentralityVec(boost::num_vertices(gm.g_));
37
    CentralityPMap v_centrality_pmap = CentralityPMap(v_centrality_vec.begin(), gm.v_index_pmap());;
38

    
39
    if (gm.weighted_graph()) { // calculate BC for weighted graph
40
        cout << "======= BCC - BC for weighted graph ======\n";
41

    
42
        typedef map<Edge, double> EdgeWeightStdMap;
43
        typedef boost::associative_property_map<EdgeIndexStdMap> EdgeWeightPMap;
44
        EdgeIndexStdMap edge_weight_std_map;
45
        EdgeWeightPMap edge_weight_pmap = EdgeWeightPMap(edge_weight_std_map);
46

    
47

    
48
        BGL_FORALL_EDGES(edge, gm.g_, Graph) {
49
            edge_weight_std_map[edge] = gm.g_[edge].cost;
50
        }
51
        boost::brandes_betweenness_centrality_targets_inclusion(gm.g_,
52
            targets_inclusion,
53
            boost::centrality_map(
54
                v_centrality_pmap).vertex_index_map(
55
                gm.v_index_pmap()).weight_map(
56
                edge_weight_pmap)
57
        );
58
    }
59
    else { // for unweighted graph
60
        boost::brandes_betweenness_centrality_targets_inclusion(gm.g_,
61
            targets_inclusion,
62
            boost::centrality_map(
63
                v_centrality_pmap).vertex_index_map(
64
                gm.v_index_pmap())
65
        );
66
    }
67

    
68
    boost::relative_betweenness_centrality(gm.g_, v_centrality_pmap);
69
}
70

    
71
void run_simulation_for_a_graph(string input_path, double& bc_clock_begin, double& bc_clock_end,
72
        double& hbc_clock_begin, double& hbc_clock_end, int number_of_experiments, bool is_weighted_graph) {
73
    /* Returns the running time for Brandes BC and HBC
74
    */
75
    double begin, end;
76

    
77
    // Disable the console output: http://stackoverflow.com/questions/30184998/how-to-disable-cout-output-in-the-runtime
78
    streambuf* orig_buf = cout.rdbuf(); // get underlying buffer
79
    cout.rdbuf(0); // set null
80

    
81
    GraphManager gm(is_weighted_graph);
82
    cout << input_path << endl;
83
    readEdgeFileGraphManager(input_path, gm);
84

    
85
    // For Brandes BC
86
    bc_clock_begin = clock();
87
    bool targets_inclusion = true;
88
    calculate_brandes_bc(gm, targets_inclusion);
89
    bc_clock_end = clock();
90

    
91
    // For HBC
92
    hbc_clock_begin = clock();
93
    BiConnectedComponents bcc = BiConnectedComponents(gm);
94
    bcc.run();
95
    hbc_clock_end = clock();
96
    cout.rdbuf(orig_buf);
97
}
98

    
99
void write_simulation_result(string out_file_path, string filename, int run_index, double bc_clock_begin, double bc_clock_end, double hbc_clock_begin, double hbc_clock_end) {
100
    ofstream out_file(out_file_path.c_str(), std::ofstream::out | std::ofstream::app);
101

    
102
    // Extract information from file name
103
    string graph_type = filename.substr(0, 2);
104

    
105
    string::size_type sep_pos = filename.find('_');
106
    string number_of_nodes = filename.substr(2, sep_pos - 2);
107

    
108
    long double bc_seconds = (bc_clock_end - bc_clock_begin) * 1.0 / CLOCKS_PER_SEC;
109
    if (bc_seconds < 0) {
110
        bc_seconds = bc_seconds + 2147;
111
    }
112
    long double hbc_seconds = (hbc_clock_end - hbc_clock_begin) * 1.0 / CLOCKS_PER_SEC;
113
    if (hbc_seconds < 0) {
114
        hbc_seconds = hbc_seconds + 2147;
115
    }
116

    
117
    cout << "    " << run_index << " " << bc_seconds << " | " << hbc_seconds << endl;
118

    
119
    string separator = "\t";
120
    if (out_file.is_open()) {
121
        out_file << filename << separator;
122
        out_file << graph_type << separator;
123
        out_file << number_of_nodes << separator;
124
        out_file << run_index << separator;
125
        out_file << bc_seconds << separator;
126
        out_file << hbc_seconds << separator;
127
        out_file << bc_clock_begin << separator;
128
        out_file << bc_clock_end << separator;
129
        out_file << hbc_clock_begin << separator;
130
        out_file << hbc_clock_end << endl;
131
    }
132
    out_file.close();
133
}
134

    
135
int main(int argc, char * argv[]) {
136
    /*
137
    Input: the folder with all the *.edges graph file
138

139
    For each graph, run the simulation <num_of_times> times
140
    Write the output into one csv file
141

142
    filename | graph type | number of nodes | id of the run | Brandes | HBC
143
    */
144

    
145
    // Handle command-line arguments
146
    if (argc < 2) {
147
        cout << "Provide the input directory\n";
148
        exit(1);
149
    }
150

    
151
    string input_dir = string(argv[1]);
152

    
153
    int number_of_experiments = 10; // default
154
    if (argc >= 3) {
155
        number_of_experiments = atoi(argv[2]);
156
    }
157

    
158
    string output_file_path = "../output/simulation.out";
159
    if (argc >= 4) {
160
        output_file_path = string(argv[3]);
161
    }
162

    
163
    bool is_weighted_graph = true;
164
    if (argc >= 5) {
165
        if (string(argv[4]).compare("false") == 0) {
166
            is_weighted_graph = false;
167
        }
168
    }
169

    
170
    // Find all the files
171
    vector<string> files;
172
    get_all_files_in_directory(input_dir, files, "edges");
173

    
174
    for (string file : files) {
175
        cout << "Running for file " << file << endl;
176
        for (int run_index = 0; run_index < number_of_experiments; ++run_index) {
177
            double bc_clock_begin, bc_clock_end;
178
            double hbc_clock_begin, hbc_clock_end;
179

    
180
            string input_path = input_dir + "/" + file;
181
            run_simulation_for_a_graph(input_path, bc_clock_begin, bc_clock_end, hbc_clock_begin, hbc_clock_end, number_of_experiments, is_weighted_graph);
182
            write_simulation_result(output_file_path, file, run_index, bc_clock_begin, bc_clock_end, hbc_clock_begin, hbc_clock_end);
183
        }
184
    }
185

    
186
    cout << "CLOCKS_PER_SEC = " << CLOCKS_PER_SEC << endl;
187
}
188

    
189

    
190

    
191
// # Negative - end_clock - begin_clock
192
// # -2054053648 | 31706352 - 2085760000
193
// #
194
// # Normal result: 93420000