2 releases

0.1.2 Mar 13, 2020
0.1.1 Mar 13, 2020
0.1.0 Mar 11, 2020

#618 in Algorithms

Download history 235/week @ 2024-06-16 210/week @ 2024-06-23 160/week @ 2024-06-30 145/week @ 2024-07-07 102/week @ 2024-07-14 323/week @ 2024-07-21 149/week @ 2024-07-28 267/week @ 2024-08-04 282/week @ 2024-08-11 259/week @ 2024-08-18 172/week @ 2024-08-25 263/week @ 2024-09-01 133/week @ 2024-09-08 337/week @ 2024-09-15 74/week @ 2024-09-22 107/week @ 2024-09-29

656 downloads per month
Used in 4 crates (2 directly)

MIT license

73KB
999 lines

traversal

Build Status Latest Version Docs License

Traversal implements generic and lazy tree traversal algorithms.

Includes:

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

Usage

Add this to your Cargo.toml:

[dependencies]
traversal = "0.1"

Releases

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

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.

No runtime deps