95 lines
1.9 KiB
C++
95 lines
1.9 KiB
C++
#ifndef GRAPH_ATTRIBUTES_H
|
|
#define GRAPH_ATTRIBUTES_H
|
|
|
|
#include <numeric>
|
|
#include "graph.hpp"
|
|
|
|
namespace ED
|
|
{
|
|
struct GraphAttributes
|
|
{
|
|
explicit GraphAttributes(NodeId num_nodes);
|
|
|
|
[[nodiscard]] NodeId num_nodes() const;
|
|
|
|
[[nodiscard]] bool is_outer(NodeId id) const;
|
|
|
|
[[nodiscard]] bool is_inner(NodeId id) const;
|
|
|
|
[[nodiscard]] bool is_out_of_forest(NodeId id) const;
|
|
|
|
void reset_forest();
|
|
|
|
NodeId rho(NodeId id);
|
|
|
|
void reset_matching();
|
|
|
|
std::vector<NodeId> phi;
|
|
std::vector<NodeId> rho_;
|
|
std::vector<NodeId> mu;
|
|
std::vector<bool> scanned;
|
|
};
|
|
|
|
inline
|
|
GraphAttributes::GraphAttributes(const ED::NodeId num_nodes):
|
|
phi(num_nodes),
|
|
rho_(num_nodes),
|
|
mu(num_nodes),
|
|
scanned(num_nodes)
|
|
{
|
|
|
|
}
|
|
|
|
inline
|
|
NodeId GraphAttributes::num_nodes() const
|
|
{
|
|
assert(phi.size() == rho_.size());
|
|
assert(phi.size() == mu.size());
|
|
assert(phi.size() == scanned.size());
|
|
return phi.size();
|
|
}
|
|
|
|
inline
|
|
bool GraphAttributes::is_outer(NodeId const id) const {
|
|
return mu[id] == id or phi[mu[id]] != mu[id];
|
|
}
|
|
|
|
inline
|
|
bool GraphAttributes::is_inner(NodeId const id) const
|
|
{
|
|
return phi[id] != id and phi[mu[id]] == mu[id];
|
|
}
|
|
|
|
inline
|
|
bool GraphAttributes::is_out_of_forest(const ED::NodeId id) const
|
|
{
|
|
return mu[id] != id and phi[id] == id and phi[mu[id]] == mu[id];
|
|
}
|
|
|
|
inline
|
|
void GraphAttributes::reset_forest()
|
|
{
|
|
std::iota(phi.begin(), phi.end(), 0);
|
|
std::iota(rho_.begin(), rho_.end(), 0);
|
|
std::fill(scanned.begin(), scanned.end(), false);
|
|
}
|
|
|
|
inline
|
|
NodeId GraphAttributes::rho(NodeId id)
|
|
{
|
|
while(rho_[id] != id)
|
|
{
|
|
rho_[id] = rho_[rho_[id]];
|
|
id = rho_[id];
|
|
}
|
|
return id;
|
|
}
|
|
|
|
inline
|
|
void GraphAttributes::reset_matching()
|
|
{
|
|
std::iota(mu.begin(), mu.end(), 0);
|
|
}
|
|
}
|
|
#endif //GRAPH_ATTRIBUTES_H
|