m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-06 15:57:28 -0500
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-06 15:57:28 -0500
commited0ac6791435c36e8374b218454ebfa7485f0845 (patch)
tree4b0b48afa48f9e09ef9ab1f9ba27f68f9f118840
parentdc88e19199f056d6f2e17c481737a71fcab70398 (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
-rw-r--r--src/brandes.cc12
-rw-r--r--src/dependency_calculator.h20
-rw-r--r--src/graph.h44
-rw-r--r--src/parse.h31
4 files changed, 72 insertions, 35 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;
}
}
}
diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h
index 93a751e..c24f5ef 100644
--- a/src/dependency_calculator.h
+++ b/src/dependency_calculator.h
@@ -18,24 +18,24 @@ public:
}
double get_dependency(int vertex) const {
- return dependency_.find(vertex)->second;
+ return dependency_[vertex];
}
private:
const Graph& graph_; // (V, E)
int vertex_; // s
std::stack<int> stack_; // S
- std::unordered_map<int, std::vector<int>> shortest_path_predecessors_; // P
- std::unordered_map<int, int> shortest_paths_; // sigma
- std::unordered_map<int, int> distance_; // d
+ std::vector<std::vector<int>> shortest_path_predecessors_; // P
+ std::vector<int> shortest_paths_; // sigma
+ std::vector<int> distance_; // d
std::queue<int> queue_; // Q
- std::unordered_map<int, double> dependency_; // delta
+ std::vector<double> dependency_; // delta
void init_() {
- for (int vertex : graph_.get_vertices()) {
- shortest_path_predecessors_[vertex] = std::vector<int>();
- shortest_paths_[vertex] = 0;
- distance_[vertex] = -1;
- dependency_[vertex] = 0;
+ for (int vertex = 0; vertex < graph_.get_number_vertices(); vertex++) {
+ shortest_path_predecessors_.emplace_back();
+ shortest_paths_.push_back(0);
+ distance_.push_back(-1);
+ dependency_.push_back(0);
}
shortest_paths_[vertex_] = 1;
diff --git a/src/graph.h b/src/graph.h
index f313cae..85c66e7 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -8,44 +8,60 @@
class Graph {
public:
- Graph() : vertices_(), graph_() {}
+ Graph() : vertices_(), graph_(), number_vertices_(0) {}
void add_vertex(int vertex) {
if (vertices_.find(vertex) == vertices_.end()) {
vertices_.insert(vertex);
orderable_vertices_.push_back(vertex);
- graph_[vertex] = std::vector<int>();
+ graph_.push_back(std::vector<int>());
+ has_out_edges_.push_back(false);
+ number_vertices_++;
}
}
void add_edge(int from, int to) {
- add_vertex(from);
- add_vertex(to);
- graph_[from].push_back(to);
- has_out_edges_.insert(from);
+ graph_[mapped_to_[from]].push_back(mapped_to_[to]);
+ has_out_edges_[mapped_to_[from]] = true;
}
- void sort_vertices() {
- std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+ void done_with_vertices() {
+ sort_vertices_();
+ map_vertices_();
}
- const std::vector<int>& get_vertices() const {
- return orderable_vertices_;
+ int get_number_vertices() const {
+ return number_vertices_;
}
const std::vector<int>& get_neighbors(int vertex) const {
- return graph_.find(vertex)->second;
+ return graph_[vertex];
}
bool has_out_edges(int vertex) const {
- return has_out_edges_.find(vertex) != has_out_edges_.end();
+ return has_out_edges_[vertex];
}
+ int get_real_vertex(int vertex) const {
+ return orderable_vertices_[vertex];
+ }
private:
std::unordered_set<int> vertices_;
std::vector<int> orderable_vertices_;
- std::unordered_map<int, std::vector<int>> graph_;
- std::unordered_set<int> has_out_edges_;
+ std::vector<std::vector<int>> graph_;
+ std::vector<bool> has_out_edges_;
+ std::unordered_map<int, int> mapped_to_;
+ int number_vertices_;
+
+ void sort_vertices_() {
+ std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
+ }
+
+ void map_vertices_() {
+ for (int i = 0; i < number_vertices_; i++) {
+ mapped_to_[orderable_vertices_[i]] = i;
+ }
+ }
};
#endif
diff --git a/src/parse.h b/src/parse.h
index 31fa7c6..095232a 100644
--- a/src/parse.h
+++ b/src/parse.h
@@ -11,10 +11,10 @@ class Parser {
public:
Parser(std::string filename) : graph_(), input_file_(filename) {
std::string edge;
- while (std::getline(input_file_, edge)) {
- parse_edge_(edge);
- }
- graph_.sort_vertices();
+ read_file_();
+ add_vertices_();
+ graph_.done_with_vertices();
+ add_edges_();
}
const Graph& get_graph() {
@@ -23,6 +23,14 @@ public:
private:
Graph graph_;
std::ifstream input_file_;
+ std::vector<std::pair<int, int>> edges_;
+
+ void read_file_() {
+ std::string edge;
+ while (std::getline(input_file_, edge)) {
+ parse_edge_(edge);
+ }
+ }
void parse_edge_(std::string edge) {
std::stringstream sstream(edge);
@@ -30,7 +38,20 @@ private:
int from, to;
sstream >> from >> to;
- graph_.add_edge(from, to);
+ edges_.push_back(std::pair<int, int>(from, to));
+ }
+
+ void add_vertices_() {
+ for (auto edge : edges_) {
+ graph_.add_vertex(edge.first);
+ graph_.add_vertex(edge.second);
+ }
+ }
+
+ void add_edges_() {
+ for (auto edge : edges_) {
+ graph_.add_edge(edge.first, edge.second);
+ }
}
};