traversal

Traversal implements generic and lazy tree traversal algorithms.

Includes: - [Breadth-First Traversal] ([Bft]) - [Depth-First Traversal] in Pre-Order ([DftPre]) - [Depth-First Traversal] in Post-Order ([DftPost]) - Reverse [Depth-First Traversal] in Pre-Order ([DftPreRev]) - Reverse [Depth-First Traversal] in Post-Order ([DftPostRev]) - All Paths ([DftPaths]) - Longest Paths ([DftLongestPaths]) - All Cycles (Paths) ([DftCycles])

Generic

Traversal uses [generics] (or [type parameters]) to be flexible to use, and easy to implement and fit into existing architecture.

Laziness

Laziness or [lazy evaluation] refers to evaluation being delayed until needed.

Traversal delays processing Nodes and fetching child Nodes until [Iterator::next][next] is called. When [next] is called, then traversal only processes the Nodes required for this iteration.

From Rust's docs:

Iterators (and iterator [adapters]) are lazy. This means that just creating an iterator doesn't do a whole lot. Nothing really happens until you call [next].

— [Iterator] - [Laziness]

Usage

Add this to your Cargo.toml:

toml [dependencies] traversal = "0.1"

Releases

Release notes are available in the repo at [CHANGELOG.md].

Algorithms

text A / \ B C / \ / \ D E F G

Given the above tree, then the following are the orders, that each individual iterator / traversal algorithm produces.

| Algorithm | Order | |-----------|-------| | [Bft] (Breadth-First Traversal) | A, B, C, D, E, F, G | | [DftPre] (Depth-First Traversal in Pre-Order) | A, B, D, E, C, F, G | | [DftPost] (Depth-First Traversal in Post-Order) | D, E, B, F, G, C, A | | [DftPreRev] (Reverse Depth-First Traversal in Pre-Order) | G, F, C, E, D, B, A | | [DftPostRev] (Reverse Depth-First Traversal in Post-Order) | A, C, G, F, B, E, D |

See each individual algorithm for code examples.

All Paths and Longest Paths

[DftPaths] and [DftLongestPaths] are utilities for iterating all paths and the longest paths in a tree.

Given the same tree as the previous examples, then [DftPaths] and [DftLongestPaths] produce the following paths.

• A, B, D
• A, B, E
• A, C
• A, C, F

• A, C, G

• A, B, E

• A, C, F
• A, C, G

See each individual algorithm for code examples.

Cycles

text A <---+ / \ | B D >-+ | | | C E >-+

• A -> D -> E

See each individual algorithm for code examples.