Class FullyIterativeDepthFirstTraversal<TEdge, TNode>

A lazy, fully-iterative, depth-first IVisitStrategy<TNode, TVisitContext> implementation, i.e. a traversing strategy which goes in depth as far as possible along each path of the tree, only backtracking when a leaf is reached.

Inheritance
System.Object
TreeTraversal<TEdge, TNode>
DepthFirstTraversal<TEdge, TNode>
FullyIterativeDepthFirstTraversal<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 FullyIterativeDepthFirstTraversal<TEdge, TNode> : DepthFirstTraversal<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 depth-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 uses a :
- At the beginning the stack contains only a frame with the root node, no parent node nor incoming edge and with a System.Boolean indicating the children for this node haven't been added to the stack yet;
- Then each frame at the top of the stack is popped out and processed, until the stack is empty.
- If the node being processed has the "children stacked" flag not set, all children are stacked up. The node itself is also stacked up, again, this time with the "children stacked" flag set. - If the node being processed has the "children stacked" flag set, or is a leaf, it's yielded to the output sequence, so that the client code implementing the visitor can lazily process the nodes.

COMPLEXITY
- Each of the n nodes and n - 1 edges of the tree is visited at most twice: the first time with the "children stacked" flag unset and a second time with the flag set. Leafs are only visited once, since they have no children and don't have to wait for their children to be visited.
- ChildrenSorter can also increase time and space complexity, especially if it perform an actual sorting of nodes. For example, if the sorter takes n * log(n) time
- The emitted by ChildrenSorter is reversed to be pushed onto the stack in the right order, and that takes additional O(n - 1) total space, since there are n - 1 edges, which are 1-to-1 with nodes in the tree.
- Each frame processing of a node with the "children stacked" flag set takes constant time (e.g.to check traversal order) and space (e.g. to extract parent node, incoming edge and node itself from the frame and to build a TreeTraversalVisit<TEdge, TNode> object for the visit).
- Time Complexity is O(n * Ts) in total, where Ts is the amortized Time Complexity of ChildrenSorter per edge/node. Taking into account the visit of each emitted node, Time Complexity is O(n * Ts * Tv), where Tv is the Time Complexity of the visitor per node.
- Space Complexity is O(n * Ss) in total, where Ss is the amortized Space Complexity of ChildrenSorter per edge/node. Taking into account the visit of each emitted node, Space Complexity is O(n * (Ss + Sv)), where Sv is the Space Complexity of the visitor per node.

Implements

Extension Methods