blob: acab78ee5f5b8dff35b093f8cd3164d3ba737ec8 (
plain)
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
|
/*
* Copyright 2024 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef wasm_support_topological_orders_h
#define wasm_support_topological_orders_h
#include <cstddef>
#include <optional>
#include <vector>
namespace wasm {
// A utility for iterating through all possible topological orders in a graph
// using an extension of Kahn's algorithm (see
// https://en.wikipedia.org/wiki/Topological_sorting) that iteratively makes all
// possible choices for each position of the output order.
struct TopologicalOrders {
// Takes an adjacency list, where the list for each vertex is a sorted list of
// the indices of its children, which will appear after it in the order.
TopologicalOrders(const std::vector<std::vector<size_t>>& graph);
struct Iterator {
using value_type = const std::vector<size_t>;
using difference_type = std::ptrdiff_t;
using reference = const std::vector<size_t>&;
using pointer = const std::vector<size_t>*;
using iterator_category = std::input_iterator_tag;
TopologicalOrders* parent;
bool isEnd() const { return !parent || parent->selectors.empty(); }
bool operator==(const Iterator& other) const {
return isEnd() == other.isEnd();
}
bool operator!=(const Iterator& other) const { return !(*this == other); }
const std::vector<size_t>& operator*() { return parent->buf; }
const std::vector<size_t>* operator->() { return &parent->buf; }
Iterator& operator++() {
parent->advance();
return *this;
}
Iterator operator++(int) { return ++(*this); }
};
Iterator begin() { return {this}; }
Iterator end() { return {nullptr}; }
private:
// The input graph given as an adjacency list with edges from vertices to
// their dependent children.
const std::vector<std::vector<size_t>>& graph;
// The current in-degrees for each vertex. When a vertex is appended to our
// permutation, the in-degrees of its children are decremented and those that
// go to zero become available for the next selection.
std::vector<size_t> indegrees;
// The buffer in which we are constructing a permutation. It contains a
// sequence of selected vertices followed by a sequence of possible choices
// for the next vertex.
std::vector<size_t> buf;
// The state for tracking the possible choices for a single vertex in the
// output order.
struct Selector {
// The start index of the sequence of available choices. Also the index
// where we place the current choice.
size_t start;
// The number of choices we have.
size_t count;
// The index of the current choice in the original order.
size_t index;
// Select the next available vertex, decrement in-degrees, and update the
// sequence of available vertices. Return the Selector for the next vertex.
Selector select(TopologicalOrders& ctx);
// Undo the current selection, move the next selection into the first
// position and return the new selector for the next position. Returns
// nullopt if advancing wraps back around to the original configuration.
std::optional<Selector> advance(TopologicalOrders& ctx);
};
// A stack of selectors, one for each vertex in a complete topological order.
// Empty if we've already seen every possible ordering.
std::vector<Selector> selectors;
void advance();
};
} // namespace wasm
#endif // wasm_support_topological_orders_h
|
