m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-04 15:20:48 -0500
committerMarcin Chrzanowski <marcin.j.chrzanowski@gmail.com>2017-01-04 15:20:48 -0500
commit17eae42992c8c2675993bca09c3e619456700122 (patch)
tree092a96e6654a73fd0582060d9dd2f3f3c6076c4d
parenta6528cc50bb2ebc509cd4ede4deda1a112c45d57 (diff)
Implement DependencyCalculator
A DependencyCalculator instance will, for each vertex in the given graph, calculate the dependency on the given vertex.
-rw-r--r--src/dependency_calculator.h81
1 files changed, 81 insertions, 0 deletions
diff --git a/src/dependency_calculator.h b/src/dependency_calculator.h
new file mode 100644
index 0000000..1c77991
--- /dev/null
+++ b/src/dependency_calculator.h
@@ -0,0 +1,81 @@
+#ifndef DEPENDENCY_CALCULATOR_H
+#define DEPENDENCY_CALCULATOR_H
+
+#include <stack>
+#include <queue>
+#include <vector>
+#include <map>
+
+#include "graph.h"
+
+class DependencyCalculator {
+public:
+ DependencyCalculator(const Graph &graph, int vertex) : graph_(graph),
+ vertex_(vertex) {
+ init_();
+ find_shortest_paths_();
+ calculate_dependencies_();
+ }
+
+ double get_dependency(int vertex) const {
+ return dependency_.find(vertex)->second;
+ }
+private:
+ const Graph &graph_; // (V, E)
+ int vertex_; // s
+ std::stack<int> stack_; // S
+ std::map<int, std::vector<int>> shortest_path_predecessors_; // P
+ std::map<int, int> shortest_paths_; // sigma
+ std::map<int, int> distance_; // d
+ std::queue<int> queue_; // Q
+ std::map<int, 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;
+ }
+
+ shortest_paths_[vertex_] = 1;
+ distance_[vertex_] = 0;
+ queue_.push(vertex_);
+ }
+
+ void find_shortest_paths_() {
+ while (!queue_.empty()) {
+ int vertex = queue_.front();
+ queue_.pop();
+ stack_.push(vertex);
+
+ for (int neighbor : graph_.get_neighbors(vertex)) {
+ if (distance_[neighbor] < 0) {
+ queue_.push(neighbor);
+ distance_[neighbor] = distance_[vertex] + 1;
+ }
+
+ if (distance_[neighbor] == distance_[vertex] + 1) {
+ shortest_paths_[neighbor] += shortest_paths_[vertex];
+ shortest_path_predecessors_[neighbor].push_back(vertex);
+ }
+ }
+ }
+ }
+
+ void calculate_dependencies_() {
+ while (!stack_.empty()) {
+ int vertex = stack_.top();
+ stack_.pop();
+ for (int predecessor : shortest_path_predecessors_[vertex]) {
+ double shortest_path_ratio =
+ (double) shortest_paths_[predecessor] /
+ (double) shortest_paths_[vertex];
+ dependency_[predecessor] +=
+ shortest_path_ratio * (1 + dependency_[vertex]);
+ }
+ }
+ }
+};
+
+#endif