Crate 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 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

Algorithms

     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.

DftPaths:

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

DftLongestPaths:

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

See each individual algorithm for code examples.

Cycles

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

DftCycles:

• A -> D (implies D is connected with A)
• A -> D -> E

See each individual algorithm for code examples.

Structs

Bft	Breadth-First Traversal (or Level Order Traversal).
DftCycles	Produces all cycle paths using Depth-First Traversal (in Pre-Order).
DftLongestPaths	Produces the longest paths using Depth-First Traversal (in Pre-Order).
DftPaths	Produces all paths using Depth-First Traversal (in Pre-Order).
DftPost	Depth-First Traversal in Post-Order.
DftPostRev	Reverse Depth-First Traversal in Post-Order.
DftPre	Depth-First Traversal in Pre-Order.
DftPreRev	Reverse Depth-First Traversal in Pre-Order.

Functions

bft	This is a shorthand for Bft::new, see Bft for more information.
dft_cycles	This is a shorthand for DftCycles::new, see DftCycles for more information.
dft_longest_paths	This is a shorthand for DftLongestPaths::new, see DftLongestPaths for more information.
dft_paths	This is a shorthand for DftPaths::new, see DftPaths for more information.
dft_post	This is a shorthand for DftPost::new, see DftPost for more information.
dft_post_rev	This is a shorthand for DftPostRev::new, see DftPostRev for more information.
dft_pre	This is a shorthand for DftPre::new, see DftPre for more information.
dft_pre_rev	This is a shorthand for DftPreRev::new, see DftPreRev for more information.