Class FullyIterativeNodeToLeafPathsBuilder


Iterative implementation.

Inheritance
System.Object
FullyIterativeNodeToLeafPathsBuilder
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 FullyIterativeNodeToLeafPathsBuilder : INodeToLeafPathsBuilder
Remarks

ADVANTAGES AND DISADVANTAGES

ALGORITHM
The implementation uses a , onto which quadrules are stacked up:
(incoming edge, node, queue of subpaths of the parent node of node, queue of subpaths of the node itself).
- A queue of subpaths of the root node is instantiated empty. It will collect the output TreePath<TEdge, TNode> instances.
- Children (node and incoming edge) of the root node are pushed onto the stack in reverse order. The queue of subpaths of the root is passed to each child. The queue of the child is set to null, since children of the child haven't been processed yet (i.e. the child queue of subpath hasn't been populated yet).
- Then the stack processing loop is performed. After every stack item is processed, the queue of subpaths of the root is unloaded, emitting TreePath<TEdge, TNode> instances from the collected of of edges and nodes.

Stack processing iteration:
- The frame at the top of the stack is popped.
- If the node is a leaf, the node and its incoming edge are added to the queue of subpaths of the parent node.
- If the node has children and the queue of subpaths of the node is set, children have been already processed. So as many paths are enqueued to the queue of subpaths of the parent node as paths in the queue of subpaths of the node. Each subpath of the node is prepended with the node itself.
- If the node has children and the queue of subpaths of the node is not set, children have not been processed yet. So create a new queue for the subpaths of the node and push the node back to the stack, this time with the queue of subpaths set. Then push all the children of the node to the stack (in reverse order), passing the queue of subpaths of the node as queue of subpaths of the parent, and the queue of subpaths of the child not set.

COMPLEXITY
- Each node is pushed to the stack and then processed at most twice (only once for leaves). So the maximum number of items in the stack is 2 * n, where n = number of nodes in the tree.
- The total number of paths from root to leaf is equal to the total number of leaves of the tree, which can be at most n (if the root itself is a leaf), n - 1 (if the root is not a leaf and the tree is completely flat) or anything down to 1 (if the tree is as unbalanced as it can be).
- Each stack processing iteration does constant time work: stack item deconstruction, check whether the node is a leaf or not, instantiate a queue of subpaths of the node. Children are iterated, however, the total number of children iteration over all the nodes of the tree is equal to the number of edges, which is n - 1.
- For each non-leaf node (and there can be O(n) of those), a queue of subpaths is instantiated and populated. Such queue can have O(n) items in it (for a flattish tree), each being a subpath of length O(n). This would suggest a cubic complexity. However, there is at most a total of n root-to-leaf paths, each being at most of length n, so overall Space Complexity is quadratic.
- So Time Complexity is O(n) and Space Complexity is O(n^2).

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