28 lines
703 B
C++
28 lines
703 B
C++
#ifndef DECREMENTAL_REACHABILITY_H_
|
|
#define DECREMENTAL_REACHABILITY_H_
|
|
|
|
#include "graph/digraph.h"
|
|
|
|
namespace algo {
|
|
template <typename T> class DecrementalReachability {
|
|
public:
|
|
virtual ~DecrementalReachability() = default;
|
|
|
|
// This method is implemented and executed by all roditty and zwick
|
|
// algorithms, it constructs the data structures used in other operations
|
|
virtual void init() = 0;
|
|
|
|
// Answer if vertex v is reachable from vertex u
|
|
virtual bool query(const T &u, const T &v) = 0;
|
|
|
|
// Remove edge e(u,v) and maintain the transitive closure matrix
|
|
virtual void remove(const std::vector<std::pair<T, T>> &edges) = 0;
|
|
|
|
protected:
|
|
Digraph<T> G;
|
|
};
|
|
|
|
}; // namespace algo
|
|
|
|
#endif
|