-
Notifications
You must be signed in to change notification settings - Fork 0
/
subgraph.hpp
256 lines (203 loc) · 8.1 KB
/
subgraph.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#pragma once
#include <vector>
#include <algorithm>
#include <map>
#include "utils.hpp"
#include "graph.hpp"
namespace detail {
// 边
struct edge {
vertex_t from, to;
};
inline bool operator==(edge lhs, edge rhs) { return lhs.to == rhs.to && lhs.from == rhs.from; }
inline bool operator!=(edge lhs, edge rhs) { return !(lhs == rhs); }
inline edge reversed(edge e) { return { e.to, e.from }; }
inline std::ostream& operator<<(std::ostream& out, edge e) {
out << "(" << e.from << ", " << e.to << ")";
return out;
}
// ----------------------------------------------------------------------------------------------
// -------------------------------------- SUBGRAPH --------------------------------------------
// ----------------------------------------------------------------------------------------------
/**
* 给定图的子图
* 在构建之后添加的顶点称为虚拟顶点
* 它们可用于区分原始图的顶点和因算法目的添加的顶点
*/
class subgraph {
graph& m_source;
std::vector< vertex_t > m_vertices;
vertex_t m_dummy_border;
public:
subgraph(graph& g, std::vector< vertex_t > vertices)
: m_source(g)
, m_vertices(std::move(vertices)) {
if (!m_vertices.empty()) {
m_dummy_border = 1 + *std::max_element(m_vertices.begin(), m_vertices.end());
}
else {
m_dummy_border = 0;
}
}
unsigned size() const { return m_vertices.size(); }
void add_edge(edge e) { m_source.add_edge(e.from, e.to); }
void add_edge(vertex_t u, vertex_t v) { add_edge({ u, v }); }
vertex_t add_dummy() {
auto u = m_source.add_node();
m_vertices.push_back(u);
return u;
}
bool is_dummy(vertex_t u) const { return u >= m_dummy_border; }
void remove_edge(edge e) { m_source.remove_edge(e.from, e.to); }
void remove_edge(vertex_t u, vertex_t v) { remove_edge({ u, v }); }
bool has_edge(edge e) const {
auto out = out_neighbours(e.from);
return std::find(out.begin(), out.end(), e.to) != out.end();
}
bool has_edge(vertex_t u, vertex_t v) const { return has_edge({ u, v }); }
const std::vector<vertex_t>& out_neighbours(vertex_t u) const { return m_source.out_neighbours(u); }
const std::vector<vertex_t>& in_neighbours(vertex_t u) const { return m_source.in_neighbours(u); }
chain_range< std::vector<vertex_t> > neighbours(vertex_t u) const { return { out_neighbours(u), in_neighbours(u) }; }
vertex_t out_neighbour(vertex_t u, int i) const { return m_source.out_neighbours(u)[i]; }
vertex_t in_neighbour(vertex_t u, int i) const { return m_source.in_neighbours(u)[i]; }
unsigned out_degree(vertex_t u) const { return m_source.out_neighbours(u).size(); }
unsigned in_deree(vertex_t u) const { return m_source.in_neighbours(u).size(); }
const std::vector<vertex_t>& vertices() const { return m_vertices; }
vertex_t vertex(int i) const { return m_vertices[i]; }
};
inline std::ostream& operator<<(std::ostream& out, const subgraph& g) {
for (auto u : g.vertices()) {
out << u << ": {";
const char* sep = "";
for (auto v : g.out_neighbours(u)) {
out << sep << v;
sep = ", ";
}
out << "}\n";
}
return out;
}
// ----------------------------------------------------------------------------------------------
// -------------------------------------- SPLITING --------------------------------------------
// ----------------------------------------------------------------------------------------------
/**
* 递归地将顶点u及其在底层无向图中可达的所有顶点分配到同一个连通分量中
*/
inline void split(const graph& g, std::vector<bool>& done, std::vector<vertex_t>& component, vertex_t u) {
done[u] = true;
component.push_back(u);
for (auto v : g.out_neighbours(u)) {
if (!done[v]) {
split(g, done, component, v);
}
}
for (auto v : g.in_neighbours(u)) {
if (!done[v]) {
split(g, done, component, v);
}
}
}
/**
* 将给定的图分割成由子图表示的连通分量。
*/
inline std::vector<subgraph> split(graph& g) {
std::vector< std::vector<vertex_t> > components;
std::vector< bool > done(g.size(), false);
for (auto u : g.vertices()) {
if (!done[u]) {
components.emplace_back();
split(g, done, components.back(), u);
}
}
std::vector<subgraph> subgraphs;
for (auto component : components) {
subgraphs.emplace_back(g, component);
}
return subgraphs;
}
// ----------------------------------------------------------------------------------------------
// ----------------------------------- VERTEX MAP ---------------------------------------------
// ----------------------------------------------------------------------------------------------
/**
* 将顶点映射到类型为T的对象
*/
template< typename T >
struct vertex_map {
std::vector< T > data;
vertex_map() = default;
vertex_map(const graph& g) : data(g.size(), T{}) {}
vertex_map(const graph& g, T val) : data(g.size(), val) {}
vertex_map(const subgraph& g) : vertex_map(g, T{}) {}
vertex_map(const subgraph& g, T val) {
for (auto u : g.vertices()) {
if (u >= data.size()) {
data.resize(u + 1);
}
data[u] = val;
}
}
void resize(const graph& g) { data.resize(g.size()); }
void resize(const graph& g, T val) { data.resize(g.size(), val); }
void resize(const subgraph& g) { resize(g, T{}); }
void resize(const subgraph& g, T val) {
for (auto u : g.vertices()) {
if (u >= data.size()) {
data.resize(u + 1);
data[u] = val;
}
}
}
void init(const subgraph& g, T val) {
for (auto u : g.vertices()) {
if (u >= data.size()) {
data.resize(u + 1);
}
data[u] = val;
}
}
// 只能用于 T = bool,因为 operator[] 不起作用
T at(vertex_t u) const { return data[u]; }
void set(vertex_t u, T val) { data[u] = val; }
T& operator[](vertex_t u) { return data[u]; }
const T& operator[](vertex_t u) const { return data[u]; }
void insert(vertex_t u, const T& val) {
add_vertex(u);
data[u] = val;
}
void insert(vertex_t u) { insert(u, T{}); }
void add_vertex(vertex_t u) {
if (u >= data.size()) {
data.resize(u + 1);
}
}
bool contains(vertex_t u) const {
return u < data.size();
}
void clear() { data.clear(); }
};
struct edge_set {
vertex_map< std::vector<vertex_t> > data;
bool contains(edge e) const { return contains(e.from, e.to); }
bool contains(vertex_t u, vertex_t v) const {
return data.contains(u) && std::find(data[u].begin(), data[u].end(), v) != data[u].end();
}
void insert(edge e) { insert(e.from, e.to); }
void insert(vertex_t u, vertex_t v) {
data.add_vertex(u);
data[u].push_back(v);
}
bool remove(edge e) { return remove(e.from, e.to); }
bool remove(vertex_t u, vertex_t v) {
if (!data.contains(u))
return false;
auto it = std::find(data[u].begin(), data[u].end(), v);
if (it == data[u].end())
return false;
data[u].erase(it);
return true;
}
};
#ifdef DEBUG_LABELS
std::map<vertex_t, std::string> debug_labels;
#endif
} //namespace detail