dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
components.h
Go to the documentation of this file.
1// Copyright 2024 Markus Anders
2// This file is part of dejavu 2.0.
3// See LICENSE for extended copyright information.
4
5#ifndef DEJAVU_COMPONENTS_H
6#define DEJAVU_COMPONENTS_H
7
8#include "graph.h"
9#include "coloring.h"
10#include "ds.h"
11
12namespace dejavu {
13namespace ir {
14
24 static int quotient_components(sgraph *g, int* colmap, ds::worklist *vertex_to_component) {
25 coloring c;
26 g->initialize_coloring(&c, colmap); // TODO certainly possible without a coloring, just keep a
27 // TODO color_to_component array
28
29 ds::markset handled(g->v_size);
30 ds::markset col_handled(g->v_size);
31 ds::worklist wl(g->v_size);
32
33 int current_component = 0;
34 int total_size = 0;
35 int in_handle = 0;
36 bool one_component = false;
37
38 for(int i = 0; i < g->v_size; ++i) {
39 if(handled.get(i)) continue;
40 handled.set(i);
41 ++in_handle;
42
43 wl.push_back(i);
44 int current_component_size = 0;
45
46 while(!wl.empty()) {
47 if(current_component_size + wl.size() == g->v_size) {
48 one_component = true;
49 break;
50 }
51
52 const int k = wl.pop_back();
53
54 const int col = c.vertex_to_col[k];
55 const int col_sz = c.ptn[col] + 1;
56
57 if(col_sz == 1) {
58 (*vertex_to_component)[k] = -1;
59 continue;
60 }
61
62 (*vertex_to_component)[k] = current_component;
63 ++current_component_size;
64
65 if(in_handle == g->v_size) continue;
66
67 const int deg = g->d[k];
68 const int vpt = g->v[k];
69 for (int j = vpt; j < vpt + deg; ++j) {
70 const int neighbour = g->e[j];
71 if(!handled.get(neighbour)) {
72 ++in_handle;
73 handled.set(neighbour);
74 wl.push_back(neighbour);
75 }
76 }
77 if(!col_handled.get(col)) {
78 col_handled.set(col);
79 for (int j = col; j < col + col_sz; ++j) {
80 const int neighbour = c.lab[j];
81 if (!handled.get(neighbour)) {
82 ++in_handle;
83 handled.set(neighbour);
84 wl.push_back(neighbour);
85 }
86 }
87 }
88 }
89
90 total_size += current_component_size;
91
92 if(current_component_size > 0) {
93 ++current_component;
94 }
95
96 if(total_size == g->v_size || one_component) break;
97 }
98
99 if(one_component) {
100 for(int i = 0; i < g->v_size; ++i) (*vertex_to_component)[i] = 0;
101 }
102
103 return current_component;
104 }
105
111 int num_components = 0;
112 std::vector<sgraph> components_graph;
113 std::vector<int*> components_coloring;
114 std::vector<int> backward_translation;
115 std::vector<int> component_to_backward_translation;
116
117 public:
124 int map_back(int component, int vertex) {
125 dej_assert(component >= 0);
126 dej_assert(component < num_components);
127 dej_assert(component_to_backward_translation[component] + vertex <
128 static_cast<int>(backward_translation.size()));
129 return (num_components <= 1? vertex :
130 backward_translation[component_to_backward_translation[component] + vertex]);
131 }
132
142 void decompose(sgraph *g, int* colmap, ds::worklist& vertex_to_component, int new_num_components) {
143 // set up forward / backward maps
144 num_components = new_num_components; // new_num_components
145 if(num_components <= 1) return;
146
147 std::vector<int> vertices_in_component;
148 vertices_in_component.resize(num_components);
149
150 std::vector<int> forward_translation;
151 forward_translation.resize(g->v_size);
152
153 int backward_size = 0;
154
155 for(int v = 0; v < g->v_size; ++v) {
156 const int component = vertex_to_component[v];
157 if(component < 0) {
158 forward_translation[v] = -1;
159 continue;
160 }
161 const int v_in_component = vertices_in_component[component];
162 ++vertices_in_component[component];
163 ++backward_size;
164 forward_translation[v] = v_in_component;
165 }
166
167 backward_translation.resize(backward_size);
168 component_to_backward_translation.reserve(num_components);
169
170 int current_pos = 0;
171 for(int i = 0; i < num_components; ++i) {
172 const int component_size = vertices_in_component[i];
173 component_to_backward_translation.push_back(current_pos);
174 current_pos += component_size;
175 }
176
177 for(int v = 0; v < g->v_size; ++v) {
178 const int component = vertex_to_component[v];
179 if(component < 0) continue;
180 const int v_in_component = forward_translation[v];
181 dej_assert(v_in_component >= 0);
182 dej_assert(v_in_component < vertices_in_component[component]);
183 backward_translation[component_to_backward_translation[component] + v_in_component] = v;
184 }
185
186 for(int v = 0; v < g->v_size; ++v) {
187 const int deg = g->d[v];
188 const int vpt = g->v[v];
189 int ept = vpt;
190 for (int j = vpt; j < vpt + deg; ++j) {
191 const int neighbour = g->e[j];
192 const int fwd_neighbour = forward_translation[neighbour];
193 if(fwd_neighbour >= 0) {
194 g->e[ept] = fwd_neighbour;
195 dej_assert(vertex_to_component[v] == vertex_to_component[neighbour]);
196 //assert(g->e[ept] >= 0 && g->e[ept] < vertices_in_component[vertex_to_component[ept]]);
197 ++ept;
198 }
199 }
200 }
201
202 std::vector<int> original_v;
203 std::vector<int> original_d;
204 original_v.reserve(g->v_size);
205 original_d.reserve(g->v_size);
206 for(int v = 0; v < g->v_size; ++v) original_v.push_back(g->v[v]);
207 for(int v = 0; v < g->v_size; ++v) original_d.push_back(g->d[v]);
208
209 for(int v = 0; v < g->v_size; ++v) {
210 const int component = vertex_to_component[v];
211 if(component < 0) continue;
212 const int v_in_component = forward_translation[v];
213 const int bw_translate = component_to_backward_translation[component];
214 g->v[bw_translate + v_in_component] = original_v[v];
215 g->d[bw_translate + v_in_component] = original_d[v];
216 }
217
218 for(int v = 0; v < g->v_size; ++v) original_v[v] = colmap[v];
219
220 components_graph.reserve(num_components);
221 for(int i = 0; i < num_components; ++i) {
222 const int bw_translate = component_to_backward_translation[i];
223 components_graph.emplace_back();
224 sgraph* component_i = &components_graph[components_graph.size() - 1];
225 component_i->v_size = vertices_in_component[i];
226 component_i->e_size = g->e_size;
227 component_i->v = g->v + bw_translate;
228 component_i->d = g->d + bw_translate;
229 component_i->e = g->e;
230 component_i->initialized = false;
231
232 for(int j = 0; j < vertices_in_component[i]; ++j) {
233 colmap[bw_translate + j] = original_v[backward_translation[bw_translate + j]];
234 }
235 components_coloring.push_back(colmap + bw_translate);
236 }
237
238 }
239
247 return &components_graph[i];
248 }
249
256 int* get_colmap(int i) {
257 return components_coloring[i];
258 }
259 };
260} }
261
262#endif //DEJAVU_COMPONENTS_H
Vertex coloring for a graph.
Definition: coloring.h:23
Set specialized for quick resets.
Definition: ds.h:546
bool get(int pos)
Definition: ds.h:605
void set(int pos)
Definition: ds.h:616
dej_nodiscard bool empty() const
Definition: ds.h:206
void resize(const int size)
Definition: ds.h:248
dej_nodiscard int size() const
Definition: ds.h:222
void push_back(T value)
Definition: ds.h:177
Decomposes graphs and manages decomposition information.
Definition: components.h:110
sgraph * get_component(int i)
Definition: components.h:246
int map_back(int component, int vertex)
Definition: components.h:124
void decompose(sgraph *g, int *colmap, ds::worklist &vertex_to_component, int new_num_components)
Definition: components.h:142
Internal graph data structure.
Definition: graph.h:19
int * e
Definition: graph.h:46
bool initialized
Definition: graph.h:43
int e_size
Definition: graph.h:49
void initialize_coloring(ds::coloring *c, int *vertex_to_col)
Definition: graph.h:61
int v_size
Definition: graph.h:48
int * v
Definition: graph.h:44
int * d
Definition: graph.h:45
Definition: bfs.h:10
#define dej_assert(expr)
Definition: utility.h:40