Class FullyIterativeBreadthFirstTraversal<TEdge, TNode>

A lazy, fully-iterative, breadth-first IVisitStrategy<TNode, TVisitContext> implementation, i.e. a traversing strategy which visits all the nodes at the current depth, along any path of the tree, before going deeper or shallower, exploring nodes with higher or lower depth.

Inheritance
System.Object
TreeTraversal<TEdge, TNode>
BreadthFirstTraversal<TEdge, TNode>
FullyIterativeBreadthFirstTraversal<TEdge, TNode>
Implements
IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.RecImmTrees.Visitor
Assembly: MoreStructures.dll
Syntax
public class FullyIterativeBreadthFirstTraversal<TEdge, TNode> : BreadthFirstTraversal<TEdge, TNode>, IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge
TNode
Remarks

ADVANTAGES AND DISADVANTAGES

Methods

| Improve this Doc View Source

Visit(TNode)

Lazily and iteratively visits the structure of the provided node, returning the sequence of IRecImmDictIndexedTreeNode<TEdge, TNode> of the structure, in breadth-first order.

Declaration
public override IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node)
Parameters
Type Name Description
TNode node

The node on where to start visit the structure.
Returns
Type Description
IEnumerable<TreeTraversalVisit<TEdge, TNode>>

A sequence emitting (node, visit context) couples, in the visit order defined by the visit strategy.
Overrides
MoreStructures.RecImmTrees.Visitor.TreeTraversal<TEdge, TNode>.Visit(TNode)
Remarks

ALGORITHM
The algorithm performs a double walk:
- The first walk is of the nodes of the tree structure and always proceeds top-down, enqueuing each encountered child for each node into a "traversal" , which is used to reproduce the breadth-first order.
- The first walk also enqueues each encountered node into a "visit" , if the TraversalOrder is ParentFirst, or it pushes it onto a "visit" , if it is ChildrenFirst.
- The second walk goes through the "visit" queue/stack, yielding to the output sequence, so that the client code implementing the visitor can lazily process the nodes.

COMPLEXITY
Each of the walk goes through all the n nodes and n - 1 edges of the tree.
Each walk uses a O(1) insertion and extraction data structure, which contains at most n elements of constant size (reference to the node, reference to its parent, reference to its incoming edge).
Time Complexity is O(n) for the first walk, when the visit queue/stack is populated and no actual node visit is performed, and O(n) for the second walk, when the actual visit of all nodes is performed. So O(n) in total.
Space Complexity is O(2n) for the first walk, due to the traversal and visit queue/stack being allocated and populated, and O(n) for the second walk, when the actual visit of all nodes is performed. So O(n) in total.

Implements

Extension Methods