TLDR; demo and code here
Today I wrote for the n time a depth first tree traversal function to get all the paths of a tree.
I decided to share this one as I think the crawler implementation is quite generic.
It consists in a function which takes a callback each time the crawler reaches a node, a fork or a leaf.
/**
* A depth first traversal implementation.
*
* onNode(nodeId: string): void
* Called on each step
*
* onFork(): void
* Called each time the crawler reaches a fork.
*
* onLeaf(): void
* Called each time the crawler reaches a leaf.
*
* onStepBack(): void
* Called when the crawler step back to the previous node.
*/
function crawlDepthFirst({
sourceId,
graph,
onNode,
onFork,
onLeaf,
onStepBack
}: {
sourceId: string
graph: Graph<any>
onNode?: (nodeId: string) => void
onFork?:() => void
onLeaf?:() => void
onStepBack?:() => void
}): void {
function step(currentNodeId: string): void {
const nodeIds = getTargetIds({sourceId: currentNodeId, graph})
onNode?.(currentNodeId)
// Found a fork
if (nodeIds.length > 1) {
onFork?.()
}
// Found a leaf
if (!nodeIds.length) {
onLeaf?.()
}
// Crawl through each fork branch
for (let i = 0; i < nodeIds.length; i++) {
const isLastBranch = i === nodeIds.length - 1
const nodeId = nodeIds[i]
step(nodeId);
// This was the last branch of the fork. Step back
// to previous node.
if (isLastBranch) {
onStepBack?.()
}
}
}
step(sourceId);
}
As a concrete example, I used it to find all the paths in a tree.
I added a state to the crawler wich is a string array. I update this state with the crawler callback on each node, fork, leaf and step back. Here are some implementation details.
- The array string represents the current path taken by the crawler.
- When the crawler hits a leaf, it means that this is the end of a path. A copy of the current path is stored as a complete path. Then the path is poped to return to the previous node.
- If the crawler comes back from the last branch of a node fork, the path is poped to return to the previous node.
Top comments (0)