This code checks if we should switch from backtracking to forward-tracking, i.e., moving forward in the DFS logic to find paths. We switch from backtracking if:
| 209 | // This code checks if we should switch from backtracking to forward-tracking, i.e., |
| 210 | // moving forward in the DFS logic to find paths. We switch from backtracking if: |
| 211 | bool PathsOutputWriter::isNextViable(ParentList* next, const std::vector<ParentList*>& path) const { |
| 212 | if (next == nullptr) { |
| 213 | return false; |
| 214 | } |
| 215 | auto nextIter = next->getIter(); |
| 216 | // (1) if this is the first element in the stack (curPath.size() == 1), i.e., we |
| 217 | // are enumerating the parents of the destination, then we should switch to |
| 218 | // forward-tracking if the next parent has visited the destination at a length |
| 219 | // that's greater than or equal to the lower bound of the recursive join. Otherwise, we would |
| 220 | // enumerate paths that are smaller than the lower bound from the start element, so we can stop |
| 221 | // here.; OR |
| 222 | if (path.size() == 1) { |
| 223 | return nextIter >= info.lowerBound; |
| 224 | } |
| 225 | // (2) if this is not the first element in the stack, i.e., then we should switch |
| 226 | // to forward tracking only if the next parent of the top node in the stack has the |
| 227 | // same iter value as the current parent. That's because the levels/iter need to |
| 228 | // decrease by 1 each time we add a new node in the stack. |
| 229 | if (nextIter == getTop(path)->getIter()) { |
| 230 | return true; |
| 231 | } |
| 232 | return false; |
| 233 | } |
| 234 | |
| 235 | bool PathsOutputWriter::checkPathNodeMask(ParentList* element) const { |
| 236 | if (!info.hasNodeMask() || element->getIter() == 1) { |