| 195 | */ |
| 196 | template<typename SetType> |
| 197 | std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations) |
| 198 | { |
| 199 | std::vector<DepGraphIndex> linearization; |
| 200 | SimpleCandidateFinder finder(depgraph); |
| 201 | SetType todo = depgraph.Positions(); |
| 202 | bool optimal = true; |
| 203 | while (todo.Any()) { |
| 204 | auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations); |
| 205 | if (iterations_done == max_iterations) optimal = false; |
| 206 | depgraph.AppendTopo(linearization, candidate.transactions); |
| 207 | todo -= candidate.transactions; |
| 208 | finder.MarkDone(candidate.transactions); |
| 209 | max_iterations -= iterations_done; |
| 210 | } |
| 211 | return {std::move(linearization), optimal}; |
| 212 | } |
| 213 | |
| 214 | /** An even simpler linearization algorithm that tries all permutations. |
| 215 | * |
no test coverage detected