66 lines
1.3 KiB
C++
66 lines
1.3 KiB
C++
#ifndef SCC_H_
|
|
#define SCC_H_
|
|
|
|
#include "digraph.h"
|
|
|
|
#include <algorithm>
|
|
#include <functional>
|
|
|
|
namespace graph {
|
|
|
|
template <typename T> class SCC : public Digraph<T> {
|
|
public:
|
|
SCC() = default;
|
|
|
|
SCC(std::unordered_map<T, std::unordered_set<T>> G, T id)
|
|
: Digraph<T>(G), id(id) {
|
|
normalize();
|
|
}
|
|
|
|
SCC(Digraph<T> G, T id) : id(id) { normalize(); }
|
|
|
|
// Return true if u is part of this SCC
|
|
bool contains(const T &u) const;
|
|
|
|
// Representative vertex of this SCC
|
|
T id{};
|
|
|
|
//
|
|
std::unordered_map<T, std::unordered_set<T>> neighboorList;
|
|
|
|
bool operator==(const SCC &o) const;
|
|
|
|
private:
|
|
// Erase all edges that include vertices outside this SCC
|
|
void normalize();
|
|
};
|
|
|
|
template <typename T> void SCC<T>::normalize() {
|
|
for (const auto &u : this->vertices()) {
|
|
for (const auto &v : this->adjList[u]) {
|
|
if (!this->contains(v)) {
|
|
this->adjList[u].erase(v);
|
|
this->adjList.erase(v);
|
|
neighboorList[u].insert(v);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
template <typename T> bool SCC<T>::contains(const T &u) const {
|
|
return this->adjList.count(u);
|
|
}
|
|
|
|
template <typename T> bool SCC<T>::operator==(const SCC &o) const {
|
|
return id == o.id;
|
|
}
|
|
|
|
template <typename T> struct HashSCC {
|
|
std::size_t operator()(const SCC<T> &C) const {
|
|
return static_cast<std::size_t>(C.id);
|
|
}
|
|
};
|
|
|
|
}; // namespace graph
|
|
|
|
#endif |