Find a candidate set using at most max_iterations iterations, and the number of iterations * actually performed. If that number is less than max_iterations, then the result is optimal. * * Always returns a connected set of transactions. * * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster. * That number is bounde
| 96 | * That number is bounded by M <= 2^(N-1). |
| 97 | */ |
| 98 | std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept |
| 99 | { |
| 100 | uint64_t iterations_left = max_iterations; |
| 101 | // Queue of work units. Each consists of: |
| 102 | // - inc: set of transactions definitely included |
| 103 | // - und: set of transactions that can be added to inc still |
| 104 | std::vector<std::pair<SetType, SetType>> queue; |
| 105 | // Initially we have just one queue element, with the entire graph in und. |
| 106 | queue.emplace_back(SetType{}, m_todo); |
| 107 | // Best solution so far. Initialize with the remaining ancestors of the first remaining |
| 108 | // transaction. |
| 109 | SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo); |
| 110 | // Process the queue. |
| 111 | while (!queue.empty() && iterations_left) { |
| 112 | // Pop top element of the queue. |
| 113 | auto [inc, und] = queue.back(); |
| 114 | queue.pop_back(); |
| 115 | // Look for a transaction to consider adding/removing. |
| 116 | bool inc_none = inc.None(); |
| 117 | for (auto split : und) { |
| 118 | // If inc is empty, consider any split transaction. Otherwise only consider |
| 119 | // transactions that share ancestry with inc so far (which means only connected |
| 120 | // sets will be considered). |
| 121 | if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) { |
| 122 | --iterations_left; |
| 123 | // Add a queue entry with split included. |
| 124 | SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split))); |
| 125 | queue.emplace_back(new_inc.transactions, und - new_inc.transactions); |
| 126 | // Add a queue entry with split excluded. |
| 127 | queue.emplace_back(inc, und - m_depgraph.Descendants(split)); |
| 128 | // Update statistics to account for the candidate new_inc. |
| 129 | if (ByRatioNegSize{new_inc.feerate} > ByRatioNegSize{best.feerate}) best = new_inc; |
| 130 | break; |
| 131 | } |
| 132 | } |
| 133 | } |
| 134 | return {std::move(best), max_iterations - iterations_left}; |
| 135 | } |
| 136 | }; |
| 137 | |
| 138 | /** A very simple finder class for optimal candidate sets, which tries every subset. |