src/dependency_calculator.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#ifndef DEPENDENCY_CALCULATOR_H
#define DEPENDENCY_CALCULATOR_H

#include <queue>
#include <stack>
#include <unordered_map>
#include <vector>

#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::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::queue<int> queue_; // Q
    std::unordered_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