This commit modifies the SingleCoherentPathBetweenNodesFinder algorithm to halt when a number of paths max_num_paths is reached. I have used a two stack implementation: Each possible path is analysed for cycle repeats before being pushed to a stack; if a cycle is repeated more than the allowed max_cycles, it is pushed to a secondary stack, otherwise to the primary stack. The secondary stack is used once the primary stack is empty. The stack size + number of found solutions is compared to max_num_paths and triggers the parachute if it exceeds.
I used this implementation instead of a priority queue as it is simpler while meeting the following goals:
Reach the max_num_paths parachute quickly if it is going to, and
Only trigger parachute if number of found paths is going to exceed max_num_paths.
I also created a new class CycleCounter that caches max cycle counts for paths when it computes them. The path finder algorithm makes a lot of redundant calls, so I hope this helps? The cache can get pretty big though. I don't know if that could be a problem.
This commit modifies the
SingleCoherentPathBetweenNodesFinderalgorithm to halt when a number of pathsmax_num_pathsis reached. I have used a two stack implementation: Each possible path is analysed for cycle repeats before being pushed to a stack; if a cycle is repeated more than the allowedmax_cycles, it is pushed to a secondary stack, otherwise to the primary stack. The secondary stack is used once the primary stack is empty. The stack size + number of found solutions is compared tomax_num_pathsand triggers the parachute if it exceeds.I used this implementation instead of a priority queue as it is simpler while meeting the following goals:
max_num_pathsparachute quickly if it is going to, andmax_num_paths.I also created a new class
CycleCounterthat caches max cycle counts for paths when it computes them. The path finder algorithm makes a lot of redundant calls, so I hope this helps? The cache can get pretty big though. I don't know if that could be a problem.