77 auto isAbstract = [&](
gate_t g) {
78 return g != root && abstract_leaves && abstract_leaves->count(g) != 0;
80 static const std::vector<gate_t> no_children;
81 auto childrenOf = [&](
gate_t g) ->
const std::vector<gate_t>& {
82 return isAbstract(g) ? no_children : c.
getWires(g);
87 std::vector<gate_t> nodes(node_set.begin(), node_set.end());
88 std::unordered_map<gate_t, idx_t, CanonicalGateHash> index;
89 index.reserve(nodes.size());
90 for(idx_t i = 0; i < nodes.size(); ++i)
92 const idx_t n = nodes.size();
94 std::vector<uint64_t> fanout(n, 0);
95 std::vector<idx_t> pending(n, 0);
96 for(idx_t i = 0; i < n; ++i) {
97 const auto &ch = childrenOf(nodes[i]);
98 pending[i] = ch.size();
100 ++fanout[index.at(u)];
103 std::vector<std::vector<idx_t> > consumers(n);
104 for(idx_t i = 0; i < n; ++i)
105 for(
gate_t u : childrenOf(nodes[i]))
106 consumers[index.at(u)].push_back(i);
108 std::vector<uint64_t> height(n, 0);
109 std::vector<idx_t> worklist;
110 for(idx_t i = 0; i < n; ++i)
112 worklist.push_back(i);
113 size_t processed = 0;
114 while(processed < worklist.size()) {
115 idx_t v = worklist[processed++];
116 for(idx_t w : consumers[v]) {
117 if(height[w] < height[v] + 1)
118 height[w] = height[v] + 1;
119 if(--pending[w] == 0)
120 worklist.push_back(w);
123 assert(worklist.size() == n);
125 uint64_t max_height = 0;
126 for(idx_t i = 0; i < n; ++i)
127 max_height = std::max(max_height, height[i]);
128 std::vector<std::vector<idx_t> > by_height(max_height + 1);
129 for(idx_t i = 0; i < n; ++i)
130 by_height[height[i]].push_back(i);
132 std::vector<uint64_t> col(n, 0);
133 uint64_t colours_assigned = 0;
134 std::vector<uint64_t> sig;
135 for(uint64_t h = 0; h <= max_height; ++h) {
136 std::vector<std::pair<std::vector<uint64_t>, idx_t> > sigs;
137 sigs.reserve(by_height[h].size());
138 for(idx_t v : by_height[h]) {
140 const bool abs = isAbstract(g);
142 sig.push_back(typeCode(c, g, abs));
143 sig.push_back(fanout[v]);
144 const auto &ch = childrenOf(g);
145 const size_t list_start = sig.size();
147 sig.push_back(col[index.at(u)]);
150 std::sort(sig.begin() + list_start, sig.end());
151 sigs.emplace_back(sig, v);
153 std::sort(sigs.begin(), sigs.end());
155 for(
size_t k = 0; k < sigs.size(); ++k) {
156 if(k > 0 && sigs[k].first != sigs[k-1].first)
158 col[sigs[k].second] = colours_assigned + rank + 1;
161 colours_assigned += rank + 1;
164 std::vector<std::vector<gate_t> > canonical_children(n);
165 for(idx_t i = 0; i < n; ++i) {
166 canonical_children[i] = childrenOf(nodes[i]);
168 if(!isAbstract(nodes[i]) &&
170 std::stable_sort(canonical_children[i].begin(),
171 canonical_children[i].end(),
173 return col[index.at(a)] < col[index.at(b)];
178 std::vector<uint64_t> number(n, 0);
179 uint64_t counter = 0;
181 struct Frame { idx_t v;
size_t next_child; };
182 std::vector<Frame> stack;
183 std::string &out = cf.
form;
185 auto firstVisit = [&](idx_t v) {
187 const bool abs = isAbstract(g);
188 number[v] = ++counter;
189 if(isLeafToken(c, g, abs)) {
190 out += typeToken(c, g, abs);
194 out += typeToken(c, g, abs);
195 stack.push_back(Frame{v, 0});
199 firstVisit(index.at(root));
200 while(!stack.empty()) {
201 Frame &f = stack.back();
202 const auto &ch = canonical_children[f.v];
203 if(f.next_child < ch.size()) {
204 idx_t u = index.at(ch[f.next_child++]);
208 out += std::to_string(number[u]);
224 std::vector<gate_t> nodes(node_set.begin(), node_set.end());
225 std::unordered_map<gate_t, idx_t, CanonicalGateHash> index;
226 index.reserve(nodes.size());
227 for(idx_t i = 0; i < nodes.size(); ++i)
229 const idx_t n = nodes.size();
230 const idx_t root_idx = index.at(root);
235 std::vector<std::vector<idx_t> > kids(n);
236 for(idx_t i = 0; i < n; ++i) {
237 const auto &wires = c.
getWires(nodes[i]);
238 kids[i].reserve(wires.size());
240 kids[i].push_back(index.at(u));
243 std::vector<uint64_t> start(n, 0), end(n, 0), last(n, 0);
244 std::vector<bool> marked(n,
false);
245 std::vector<idx_t> finished;
253 std::vector<Frame> stack;
255 auto visit = [&](idx_t x) {
261 stack.push_back(Frame{x, 0});
266 while(!stack.empty()) {
267 const idx_t v = stack.back().v;
268 if(stack.back().next_child < kids[v].size()) {
269 const idx_t u = kids[v][stack.back().next_child++];
273 if(!kids[v].empty()) {
278 finished.push_back(v);
281 assert(finished.size() == n);
283 const uint64_t NO_DATE = std::numeric_limits<uint64_t>::max();
284 std::vector<uint64_t> lo(n, NO_DATE), hi(n, 0);
285 for(idx_t v : finished)
286 for(idx_t u : kids[v]) {
287 lo[v] = std::min(lo[v], std::min(start[u], lo[u]));
288 hi[v] = std::max(hi[v], std::max(last[u], hi[u]));
291 std::vector<bool> in_r(n,
false);
292 for(idx_t v = 0; v < n; ++v) {
293 if(v == root_idx || kids[v].empty())
299 in_r[v] = start[v] < lo[v] && hi[v] < end[v];
302 std::vector<bool> reached(n,
false);
303 std::vector<idx_t> queue{root_idx};
304 reached[root_idx] =
true;
305 std::vector<gate_t> result;
306 for(
size_t head = 0; head < queue.size(); ++head) {
307 const idx_t x = queue[head];
309 result.push_back(nodes[x]);
312 for(idx_t u : kids[x])