@graphty/algorithms / index / indexed / directionOptimizedBfs
Function: directionOptimizedBfs() ​
directionOptimizedBfs(
s,sourceNode,options?):BfsResult
Defined in: indexed/bfs.ts:271
Direction-optimising breadth-first search (Beamer, Asanovic and Patterson, SC'12): a top-down step expands the frontier's out-arcs, a bottom-up step has every unvisited node look for a frontier node among its in-neighbours over s.reverse(), and the search switches between the two by the arcs each would read. Both steps give a node the LOWEST-index frontier node that reaches it as its parent, so the result does not depend on which steps ran: depth equals breadthFirstSearch's, and order lists the visited nodes level by level, ascending within a level.
Parameters ​
s ​
GraphSnapshot
The snapshot to traverse
sourceNode ​
NodeRef
The node to start from: its index, or { id }
options? ​
DirectionOptimizedBfsOptions = {}
The switching thresholds
Returns ​
The visit order, the parent array, the depth array and the visited count