From 17eae42992c8c2675993bca09c3e619456700122 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 4 Jan 2017 15:20:48 -0500 Subject: Implement DependencyCalculator A DependencyCalculator instance will, for each vertex in the given graph, calculate the dependency on the given vertex. --- src/dependency_calculator.h | 81 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 81 insertions(+) create mode 100644 src/dependency_calculator.h (limited to 'src') 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 +#include +#include +#include + +#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 stack_; // S + std::map> shortest_path_predecessors_; // P + std::map shortest_paths_; // sigma + std::map distance_; // d + std::queue queue_; // Q + std::map dependency_; // delta + + void init_() { + for (int vertex : graph_.get_vertices()) { + shortest_path_predecessors_[vertex] = std::vector(); + 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 -- cgit v1.2.3