Class FullyRecursiveNodeToLeafPathsBuilder


Recursive implementation.

Inheritance
System.Object
FullyRecursiveNodeToLeafPathsBuilder
Implements
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.Paths
Assembly: MoreStructures.dll
Syntax
public class FullyRecursiveNodeToLeafPathsBuilder : INodeToLeafPathsBuilder
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with tree of a "reasonable" height.

ALGORITHM
- The implementation iterates over the children, getting its node-to-leaf subpaths by calling GetAllNodeToLeafPaths<TEdge, TNode>(TNode) recursively.
- Then, it prepends the child and its incoming edge to each subpath of each child.
- If the node has no child, a singleton path is returned, containing only the child and its incoming edge.

COMPLEXITY
- Each node is processed once and the number of node-to-leaf paths returned has an upper bound on n = number of nodes in the tree. The length of each node-to-leaf path is also limited by n.
- So, both Time and Space Complexity are O(n).

Methods

| Improve this Doc View Source

GetAllNodeToLeafPaths<TEdge, TNode>(TNode)

Declaration
public IEnumerable<TreePath<TEdge, TNode>> GetAllNodeToLeafPaths<TEdge, TNode>(TNode node)
    where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Parameters
Type Name Description
TNode node
Returns
Type Description
IEnumerable<TreePath<TEdge, TNode>>
Type Parameters
Name Description
TEdge
TNode

Implements

Extension Methods