81 lines
2.3 KiB
C++
81 lines
2.3 KiB
C++
#ifndef KING_H_
|
|
#define KING_H_
|
|
|
|
#include "algorithm/dynamic_reachability.h"
|
|
#include "algorithm/italiano.h"
|
|
|
|
namespace algo {
|
|
|
|
template <typename T> class King : public DynamicReachability<T> {
|
|
public:
|
|
King() = default;
|
|
|
|
explicit King(graph::Digraph<T> G) { this->G = G; }
|
|
|
|
// Initialize decremental maintenance data structures for DAGs for each
|
|
// vertex's in and out reachability trees
|
|
void init() override;
|
|
|
|
// Execute reachability query q(u, v) from vertex u to vertex v
|
|
// in O(n) using the stored decremental maintenance data structure for DAGs
|
|
bool query(const T &u, const T &v) override;
|
|
|
|
// Delete collection of edges
|
|
void remove(const std::vector<std::pair<T, T>> &edges) override;
|
|
|
|
// Delete edge e(u, v) from all reachability trees and update each one of
|
|
// them using the decremental reachability algorithm for DAGs
|
|
void remove(const T &u, const T &v);
|
|
|
|
// Insert edge e(u, v) by reconstructing all reachability trees
|
|
void insert(const T &c, const std::vector<T> &vertices) override;
|
|
|
|
private:
|
|
// Connect each reachabiliy tree with decremental maintenance data structure
|
|
std::unordered_map<T, Italiano<T>> In;
|
|
std::unordered_map<T, Italiano<T>> Out;
|
|
};
|
|
|
|
template <typename T> void King<T>::init() {
|
|
for (const auto &u : this->G.vertices()) {
|
|
In[u] = Italiano<T>(BreadthFirstTree<T>(this->G.reverse(), u));
|
|
In[u].init();
|
|
Out[u] = Italiano<T>(BreadthFirstTree<T>(this->G, u));
|
|
Out[u].init();
|
|
}
|
|
}
|
|
|
|
template <typename T> bool King<T>::query(const T &u, const T &v) {
|
|
return std::any_of(
|
|
this->G.vertices().begin(), this->G.vertices().end(),
|
|
[&](const T &w) { return In[w].query(w, u) && Out[w].query(w, v); });
|
|
}
|
|
|
|
template <typename T>
|
|
void King<T>::remove(const std::vector<std::pair<T, T>> &edges) {
|
|
for (const auto &[u, v] : edges)
|
|
remove(u, v);
|
|
}
|
|
|
|
template <typename T> void King<T>::remove(const T &u, const T &v) {
|
|
this->G.remove(u, v);
|
|
for (const auto &w : this->G.vertices()) {
|
|
In[w].remove(v, u);
|
|
Out[w].remove(u, v);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
void King<T>::insert(const T &c, const std::vector<T> &vertices) {
|
|
for (const auto &v : vertices) {
|
|
this->G.insert(c, v);
|
|
}
|
|
In[c] = Italiano<T>(BreadthFirstTree<T>(this->G.reverse(), c));
|
|
In[c].init();
|
|
Out[c] = Italiano<T>(BreadthFirstTree<T>(this->G, c));
|
|
Out[c].init();
|
|
}
|
|
|
|
} // namespace algo
|
|
|
|
#endif |