m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/brandes.cc18
-rw-r--r--src/dependency_calculator.h9
-rw-r--r--src/graph.h6
-rw-r--r--src/parse.h8
4 files changed, 22 insertions, 19 deletions
diff --git a/src/brandes.cc b/src/brandes.cc
index 5060a9d..7d12ec6 100644
--- a/src/brandes.cc
+++ b/src/brandes.cc
@@ -1,13 +1,13 @@
-#include <algorithm>
#include <fstream>
#include <iostream>
-#include <thread>
-#include <queue>
#include <mutex>
+#include <queue>
+#include <string>
+#include <thread>
-#include "parse.h"
-#include "graph.h"
#include "dependency_calculator.h"
+#include "graph.h"
+#include "parse.h"
int threads;
std::string input_file;
@@ -16,9 +16,10 @@ std::string output_file;
Graph graph;
std::unordered_map<int, double> betweenness;
std::queue<int> vertices_to_process;
+
+std::vector<std::thread> threads_list;
std::mutex queue_mutex;
std::mutex betweenness_mutex;
-std::vector<std::thread> threads_list;
void parse_args(int argc, char *argv[]) {
if (argc < 4) {
@@ -50,13 +51,12 @@ int next_vertex() {
if (vertices_to_process.empty()) {
return -1;
}
- int vertex;
- vertex = vertices_to_process.front();
+ int vertex = vertices_to_process.front();
vertices_to_process.pop();
return vertex;
}
-void update_betweenness(int vertex, DependencyCalculator & dc) {
+void update_betweenness(int vertex, DependencyCalculator& dc) {
std::lock_guard<std::mutex> lock(betweenness_mutex);
for (int v : graph.get_vertices()) {
if (v != vertex ) {
diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h
index be6aeb7..93a751e 100644
--- a/src/dependency_calculator.h
+++ b/src/dependency_calculator.h
@@ -1,16 +1,16 @@
#ifndef DEPENDENCY_CALCULATOR_H
#define DEPENDENCY_CALCULATOR_H
-#include <stack>
#include <queue>
-#include <vector>
+#include <stack>
#include <unordered_map>
+#include <vector>
#include "graph.h"
class DependencyCalculator {
public:
- DependencyCalculator(const Graph &graph, int vertex) : graph_(graph),
+ DependencyCalculator(const Graph& graph, int vertex) : graph_(graph),
vertex_(vertex) {
init_();
find_shortest_paths_();
@@ -21,7 +21,7 @@ public:
return dependency_.find(vertex)->second;
}
private:
- const Graph &graph_; // (V, E)
+ const Graph& graph_; // (V, E)
int vertex_; // s
std::stack<int> stack_; // S
std::unordered_map<int, std::vector<int>> shortest_path_predecessors_; // P
@@ -67,6 +67,7 @@ private:
while (!stack_.empty()) {
int vertex = stack_.top();
stack_.pop();
+
for (int predecessor : shortest_path_predecessors_[vertex]) {
double shortest_path_ratio =
(double) shortest_paths_[predecessor] /
diff --git a/src/graph.h b/src/graph.h
index 47dce16..317024e 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -29,16 +29,16 @@ public:
std::sort(orderable_vertices_.begin(), orderable_vertices_.end());
}
- const std::vector<int> & get_vertices() const {
+ const std::vector<int>& get_vertices() const {
return orderable_vertices_;
}
- const std::vector<int> & get_neighbors(int vertex) const {
+ const std::vector<int>& get_neighbors(int vertex) const {
return graph_.find(vertex)->second;
}
bool has_out_edges(int vertex) const {
- return has_out_edges_.count(vertex) > 0;
+ return has_out_edges_.find(vertex) == has_out_edges_.end();
}
private:
diff --git a/src/parse.h b/src/parse.h
index 1d37083..31fa7c6 100644
--- a/src/parse.h
+++ b/src/parse.h
@@ -2,9 +2,9 @@
#define PARSE_H
#include <fstream>
-#include <set>
#include <sstream>
#include <string>
+
#include "graph.h"
class Parser {
@@ -17,7 +17,7 @@ public:
graph_.sort_vertices();
}
- const Graph & get_graph() {
+ const Graph& get_graph() {
return graph_;
}
private:
@@ -25,9 +25,11 @@ private:
std::ifstream input_file_;
void parse_edge_(std::string edge) {
- int from, to;
std::stringstream sstream(edge);
+
+ int from, to;
sstream >> from >> to;
+
graph_.add_edge(from, to);
}
};