P-E-R-R-Y
Utilitaires, contrats et vendors du moteur, en une seule doc
Loading...
Searching...
No Matches
graph.hpp
Go to the documentation of this file.
1
28
29#pragma once
30
31#include <algorithm>
32#include <concepts>
33#include <cstddef>
34#include <map>
35#include <numeric>
36#include <queue>
37#include <set>
38#include <type_traits>
39#include <utility>
40#include <vector>
41
42// ---------- concepts ----------
43
44template<typename F, typename T>
45concept EqualityFn = std::is_invocable_r_v<bool, F, const T&, const T&>;
46
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&>>;
50
51// ---------- edge ----------
52
53struct Link {
54 int from = 0;
55 int to = 0;
56 double weight = 0.0;
57};
58
59// ---------- graph kind ----------
60
62
63// ---------- graph ----------
64
65template<typename T, typename Equal = void, GraphKind Kind = GraphKind::Undirected>
66class Graph {
67public:
68 Graph() = default;
69
70 // ----- mutation -----
71
72 // Add a node and return its index. If Equal is provided and an equivalent
73 // node already exists, returns the existing index instead.
74 int addNode(const T& value) {
75 if constexpr (!std::is_void_v<Equal>) {
76 static_assert(EqualityFn<Equal, T>,
77 "Equal must be callable as bool(const T&, const T&)");
78 Equal eq{};
79 for (std::size_t i = 0; i < nodes_.size(); ++i) {
80 if (eq(nodes_[i], value)) return static_cast<int>(i);
81 }
82 }
83 nodes_.push_back(value);
84 return static_cast<int>(nodes_.size() - 1);
85 }
86
87 void addEdge(int from, int to, double weight = 0.0) {
88 edges_.push_back({from, to, weight});
89 }
90
91 void clear() { nodes_.clear(); edges_.clear(); }
92
93 void reserveNodes(std::size_t n) { nodes_.reserve(n); }
94 void reserveEdges(std::size_t n) { edges_.reserve(n); }
95
96 // ----- accessors -----
97
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]; }
101 std::size_t nodeCount() const { return nodes_.size(); }
102 std::size_t edgeCount() const { return edges_.size(); }
103 bool empty() const { return nodes_.empty(); }
104 static constexpr bool isDirected() { return Kind == GraphKind::Directed; }
105
106 // ----- queries -----
107
108 // All nodes incident to `idx`. Honors the graph kind: undirected graphs
109 // return both predecessors and successors.
110 std::vector<int> neighbors(int idx) const {
111 std::vector<int> result;
112 for (const auto& e : edges_) {
113 if (e.from == idx) {
114 result.push_back(e.to);
115 } else if constexpr (Kind == GraphKind::Undirected) {
116 if (e.to == idx) result.push_back(e.from);
117 }
118 }
119 return result;
120 }
121
122 // Always returns outgoing targets, regardless of Kind.
123 std::vector<int> successors(int idx) const {
124 std::vector<int> result;
125 for (const auto& e : edges_)
126 if (e.from == idx) result.push_back(e.to);
127 return result;
128 }
129
130 // Always returns incoming sources, regardless of Kind.
131 std::vector<int> predecessors(int idx) const {
132 std::vector<int> result;
133 for (const auto& e : edges_)
134 if (e.to == idx) result.push_back(e.from);
135 return result;
136 }
137
138 // ----- factories -----
139
140 // Build a graph from a list of (T, T) pairs. Optionally provide a Weight
141 // functor to compute edge weights from endpoint data.
142 template<typename Weight = void>
143 static Graph fromPairs(const std::vector<std::pair<T, T>>& pairs) {
144 if constexpr (!std::is_void_v<Weight>) {
145 static_assert(WeightFn<Weight, T>,
146 "Weight must be callable as arithmetic(const T&, const T&)");
147 }
148 Graph g;
149 g.reserveEdges(pairs.size());
150 for (const auto& p : pairs) {
151 int from = g.addNode(p.first);
152 int to = g.addNode(p.second);
153 double w = 0.0;
154 if constexpr (!std::is_void_v<Weight>) {
155 Weight weight{};
156 w = static_cast<double>(weight(p.first, p.second));
157 }
158 g.addEdge(from, to, w);
159 }
160 return g;
161 }
162
163 // ----- algorithms (non-mutating, return new graphs) -----
164
165 // Minimum Spanning Tree via Kruskal. Returns a new graph sharing the same
166 // node indexing as `*this`, containing only the MST edges. The original
167 // is untouched, so caller can compute `difference(*this, mst)` for loopback.
168 Graph mst() const {
169 Graph result;
170 result.nodes_ = nodes_;
171 if (nodes_.empty() || edges_.empty()) return result;
172
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; });
176
177 std::vector<int> parent(nodes_.size());
178 std::vector<int> rank_(nodes_.size(), 0);
179 std::iota(parent.begin(), parent.end(), 0);
180
181 auto find = [&](int x) {
182 while (x != parent[x]) {
183 parent[x] = parent[parent[x]]; // path halving
184 x = parent[x];
185 }
186 return x;
187 };
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);
192 parent[rb] = ra;
193 if (rank_[ra] == rank_[rb]) ++rank_[ra];
194 return true;
195 };
196
197 result.reserveEdges(nodes_.size() - 1);
198 for (const auto& e : sorted) {
199 if (unite(e.from, e.to)) result.edges_.push_back(e);
200 }
201 return result;
202 }
203
204 // Edges in *this that are NOT in `other`. Useful for TinyKeep-style
205 // "Delaunay minus MST" to recover loopback candidates.
206 // Both graphs must share the same node indexing.
207 Graph difference(const Graph& other) const {
208 Graph result;
209 result.nodes_ = nodes_;
210
211 std::set<std::pair<int,int>> keys;
212 for (const auto& e : other.edges_) keys.insert(edgeKey(e));
213
214 for (const auto& e : edges_) {
215 if (!keys.count(edgeKey(e))) result.edges_.push_back(e);
216 }
217 return result;
218 }
219
220 // Union of edge sets (does not deduplicate parallel edges, just concatenates).
221 Graph unionWith(const Graph& other) const {
222 Graph result = *this;
223 result.edges_.insert(result.edges_.end(),
224 other.edges_.begin(), other.edges_.end());
225 return result;
226 }
227
228 // Connected components as lists of node indices. Honors graph kind: in
229 // directed mode this is *weakly* connected components.
230 std::vector<std::vector<int>> connectedComponents() const {
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]; }
235 return x;
236 };
237 for (const auto& e : edges_) {
238 int ra = find(e.from), rb = find(e.to);
239 if (ra != rb) parent[ra] = rb;
240 }
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));
244
245 std::vector<std::vector<int>> result;
246 result.reserve(groups.size());
247 for (auto& [_, v] : groups) result.push_back(std::move(v));
248 return result;
249 }
250
251 // Breadth-first visit order starting from `start`. Honors graph kind.
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);
256 std::queue<int> q;
257 q.push(start);
258 seen[start] = true;
259 while (!q.empty()) {
260 int x = q.front(); q.pop();
261 order.push_back(x);
262 for (int n : neighbors(x))
263 if (!seen[n]) { seen[n] = true; q.push(n); }
264 }
265 return order;
266 }
267
268private:
269 std::vector<T> nodes_;
270 std::vector<Link> edges_;
271
272 static std::pair<int,int> edgeKey(const Link& e) {
273 if constexpr (Kind == GraphKind::Undirected) {
274 return {std::min(e.from, e.to), std::max(e.from, e.to)};
275 } else {
276 return {e.from, e.to};
277 }
278 }
279};
280
281
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
Graph()=default
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
Definition graph.hpp:45
Definition graph.hpp:48
GraphKind
Definition graph.hpp:61
@ Undirected
Definition graph.hpp:61
@ Directed
Definition graph.hpp:61