Skip to content

Implement lookback feature to fastWalkthrough

Jay Chanrequested to merge
jay_fastwalkthrough_lookback into dev

Implement the lookback feature what was previously only implemented in CCandWalk to fastWalkthrough for faster running in acorn and also for easier transport to the As-a-Service.

The changes include:

  • Implement lookback to compare the edge scores between multiple incoming edges connecting to a junction node that is the second node from the starting node. The difference from the original lookback implemented in CCandWalk is that, if it finds an alternative precedent node, it can trace all the way back to the alternative starting node, which should provide better performance.
  • Use Breadth-first search (BFS) for walkthrough and only save the longest paths for each starting node for v0. This avoids comparing the path lengths in the end and improves computing time.
  • Also use BFS for walkthrough and save the longest and the second longest paths for v2, and both longest and second longest will be compared against their edges scores along the paths.
  • Fix a potential bug in the original fast walkthrough implementation: complete paths need to be added when all the next nodes from the current node are already used.

Merge request reports