44template<
typename F,
typename T>
45concept EqualityFn = std::is_invocable_r_v<bool, F, const T&, const T&>;
47template<
typename F,
typename T>
48concept WeightFn = std::is_invocable_v<F, const T&, const T&>
49 && std::is_arithmetic_v<std::invoke_result_t<F, const T&, const T&>>;
65template<
typename T,
typename Equal =
void, GraphKind Kind = GraphKind::Undirected>
75 if constexpr (!std::is_void_v<Equal>) {
77 "Equal must be callable as bool(const T&, const T&)");
79 for (std::size_t i = 0; i < nodes_.size(); ++i) {
80 if (eq(nodes_[i], value))
return static_cast<int>(i);
83 nodes_.push_back(value);
84 return static_cast<int>(nodes_.size() - 1);
87 void addEdge(
int from,
int to,
double weight = 0.0) {
88 edges_.push_back({from, to, weight});
91 void clear() { nodes_.clear(); edges_.clear(); }
98 const std::vector<T>&
nodes()
const {
return nodes_; }
99 const std::vector<Link>&
edges()
const {
return edges_; }
100 const T&
node(
int i)
const {
return nodes_[i]; }
103 bool empty()
const {
return nodes_.empty(); }
111 std::vector<int> result;
112 for (
const auto& e : edges_) {
114 result.push_back(e.to);
116 if (e.to == idx) result.push_back(e.from);
124 std::vector<int> result;
125 for (
const auto& e : edges_)
126 if (e.from == idx) result.push_back(e.to);
132 std::vector<int> result;
133 for (
const auto& e : edges_)
134 if (e.to == idx) result.push_back(e.from);
142 template<
typename Weight =
void>
144 if constexpr (!std::is_void_v<Weight>) {
146 "Weight must be callable as arithmetic(const T&, const T&)");
150 for (
const auto& p : pairs) {
154 if constexpr (!std::is_void_v<Weight>) {
156 w =
static_cast<double>(weight(p.first, p.second));
170 result.nodes_ = nodes_;
171 if (nodes_.empty() || edges_.empty())
return result;
173 std::vector<Link> sorted = edges_;
174 std::sort(sorted.begin(), sorted.end(),
175 [](
const Link& a,
const Link& b) { return a.weight < b.weight; });
177 std::vector<int> parent(nodes_.size());
178 std::vector<int> rank_(nodes_.size(), 0);
179 std::iota(parent.begin(), parent.end(), 0);
181 auto find = [&](
int x) {
182 while (x != parent[x]) {
183 parent[x] = parent[parent[x]];
188 auto unite = [&](
int a,
int b) ->
bool {
189 int ra = find(a), rb = find(b);
190 if (ra == rb)
return false;
191 if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
193 if (rank_[ra] == rank_[rb]) ++rank_[ra];
198 for (
const auto& e : sorted) {
199 if (unite(e.from, e.to)) result.edges_.push_back(e);
209 result.nodes_ = nodes_;
211 std::set<std::pair<int,int>> keys;
212 for (
const auto& e : other.edges_) keys.insert(edgeKey(e));
214 for (
const auto& e : edges_) {
215 if (!keys.count(edgeKey(e))) result.edges_.push_back(e);
222 Graph result = *
this;
223 result.edges_.insert(result.edges_.end(),
224 other.edges_.begin(), other.edges_.end());
231 std::vector<int> parent(nodes_.size());
232 std::iota(parent.begin(), parent.end(), 0);
233 auto find = [&](
int x) {
234 while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; }
237 for (
const auto& e : edges_) {
238 int ra = find(e.from), rb = find(e.to);
239 if (ra != rb) parent[ra] = rb;
241 std::map<int, std::vector<int>> groups;
242 for (std::size_t i = 0; i < nodes_.size(); ++i)
243 groups[find(
static_cast<int>(i))].push_back(
static_cast<int>(i));
245 std::vector<std::vector<int>> result;
246 result.reserve(groups.size());
247 for (
auto& [_, v] : groups) result.push_back(std::move(v));
252 std::vector<int>
bfs(
int start)
const {
253 std::vector<int> order;
254 if (nodes_.empty())
return order;
255 std::vector<bool> seen(nodes_.size(),
false);
260 int x = q.front(); q.pop();
263 if (!seen[n]) { seen[n] =
true; q.push(n); }
269 std::vector<T> nodes_;
270 std::vector<Link> edges_;
272 static std::pair<int,int> edgeKey(
const Link& e) {
274 return {std::min(e.
from, e.
to), std::max(e.
from, e.
to)};
bool empty() const
Definition graph.hpp:103
std::size_t nodeCount() const
Definition graph.hpp:101
const std::vector< T > & nodes() const
Definition graph.hpp:98
std::vector< std::vector< int > > connectedComponents() const
Definition graph.hpp:230
Graph unionWith(const Graph &other) const
Definition graph.hpp:221
std::vector< int > predecessors(int idx) const
Definition graph.hpp:131
std::size_t edgeCount() const
Definition graph.hpp:102
static Graph fromPairs(const std::vector< std::pair< T, T > > &pairs)
Definition graph.hpp:143
void addEdge(int from, int to, double weight=0.0)
Definition graph.hpp:87
Graph difference(const Graph &other) const
Definition graph.hpp:207
int addNode(const T &value)
Definition graph.hpp:74
const T & node(int i) const
Definition graph.hpp:100
void reserveEdges(std::size_t n)
Definition graph.hpp:94
Graph mst() const
Definition graph.hpp:168
static constexpr bool isDirected()
Definition graph.hpp:104
void reserveNodes(std::size_t n)
Definition graph.hpp:93
const std::vector< Link > & edges() const
Definition graph.hpp:99
std::vector< int > bfs(int start) const
Definition graph.hpp:252
void clear()
Definition graph.hpp:91
std::vector< int > neighbors(int idx) const
Definition graph.hpp:110
std::vector< int > successors(int idx) const
Definition graph.hpp:123
GraphKind
Definition graph.hpp:61
@ Undirected
Definition graph.hpp:61
@ Directed
Definition graph.hpp:61
int to
Definition graph.hpp:55
double weight
Definition graph.hpp:56
int from
Definition graph.hpp:54