diff options
author | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2017-01-06 15:57:28 -0500 |
---|---|---|
committer | Marcin Chrzanowski <marcin.j.chrzanowski@gmail.com> | 2017-01-06 15:57:28 -0500 |
commit | ed0ac6791435c36e8374b218454ebfa7485f0845 (patch) | |
tree | 4b0b48afa48f9e09ef9ab1f9ba27f68f9f118840 /src/brandes.cc | |
parent | dc88e19199f056d6f2e17c481737a71fcab70398 (diff) |
Optimalize by using vectors over maps and sets
- Can iterate over vertices with for (int v = 0; v < number_vertices;
v++) loop
- This required internally remapping the vertices from their actual
names to 0, 1, ..., number_vertices - 1.
- Use Graph::get_real_vertex(vertex) to get original value
Diffstat (limited to 'src/brandes.cc')
-rw-r--r-- | src/brandes.cc | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/src/brandes.cc b/src/brandes.cc index 7d12ec6..c4c14cd 100644 --- a/src/brandes.cc +++ b/src/brandes.cc @@ -14,7 +14,7 @@ std::string input_file; std::string output_file; Graph graph; -std::unordered_map<int, double> betweenness; +std::vector<double> betweenness; std::queue<int> vertices_to_process; std::vector<std::thread> threads_list; @@ -40,8 +40,8 @@ void parse_input() { } void init() { - for (int vertex : graph.get_vertices()) { - betweenness[vertex] = 0; + for (int vertex = 0; vertex < graph.get_number_vertices(); vertex++) { + betweenness.push_back(0); vertices_to_process.push(vertex); } } @@ -58,7 +58,7 @@ int next_vertex() { void update_betweenness(int vertex, DependencyCalculator& dc) { std::lock_guard<std::mutex> lock(betweenness_mutex); - for (int v : graph.get_vertices()) { + for (int v = 0; v < graph.get_number_vertices(); v++) { if (v != vertex ) { betweenness[v] += dc.get_dependency(v); } @@ -88,9 +88,9 @@ void join_threads() { void print_betweenness() { std::ofstream fout(output_file); - for (int vertex : graph.get_vertices()) { + for (int vertex = 0; vertex < graph.get_number_vertices(); vertex++) { if (graph.has_out_edges(vertex)) { - fout << vertex << " " << betweenness[vertex] << std::endl; + fout << graph.get_real_vertex(vertex) << " " << betweenness[vertex] << std::endl; } } } |