< Summary

Information
Class: MoreStructures.RecImmTrees.Paths.FullyIterativeNodeToLeafPathsBuilder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/RecImmTrees/Paths/FullyIterativeNodeToLeafPathsBuilder.cs
Line coverage
100%
Covered lines: 38
Uncovered lines: 0
Coverable lines: 38
Total lines: 132
Line coverage: 100%
Branch coverage
100%
Covered branches: 14
Total branches: 14
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Edge()100%1100%
get_Node()100%1100%
get_ParentNodeSubpaths()100%1100%
get_NodeSubpaths()100%1100%
GetAllNodeToLeafPaths()100%6100%
ProcessStack(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/RecImmTrees/Paths/FullyIterativeNodeToLeafPathsBuilder.cs

#LineLine coverage
 1namespace MoreStructures.RecImmTrees.Paths;
 2
 3/// <summary>
 4///     <inheritdoc/>
 5///     <br/>
 6///     Iterative implementation.
 7/// </summary>
 8/// <remarks>
 9///     <inheritdoc cref="INodeToLeafPathsBuilder" path="/remarks"/>
 10///     <para id="advantages">
 11///     ADVANTAGES AND DISADVANTAGES
 12///     <br/>
 13///     <inheritdoc cref="DocFragments" path="/remarks/para[@id='fully-iterative-advantages']"/>
 14///     </para>
 15///     <para id="algo">
 16///     ALGORITHM
 17///     <br/>
 18///     The implementation uses a <see cref="Stack{T}"/>, onto which quadrules are stacked up:
 19///     <br/>
 20///     (incoming edge, node, queue of subpaths of the parent node of node, queue of subpaths of the node itself).
 21///     <br/>
 22///     - A queue of subpaths of the root node is instantiated empty. It will collect the output
 23///       <see cref="TreePath{TEdge, TNode}"/> instances.
 24///       <br/>
 25///     - Children (node and incoming edge) of the root node are pushed onto the stack in reverse order. The queue of
 26///       subpaths of the root is passed to each child. The queue of the child is set to <see langword="null"/>, since
 27///       children of the child haven't been processed yet (i.e. the child queue of subpath hasn't been populated yet).
 28///       <br/>
 29///     - Then the stack processing loop is performed. After every stack item is processed, the queue of subpaths of
 30///       the root is unloaded, emitting <see cref="TreePath{TEdge, TNode}"/> instances from the collected
 31///       <see cref="IEnumerable{T}"/> of <see cref="KeyValuePair{TKey, TValue}"/> of edges and nodes.
 32///       <br/>
 33///     <br/>
 34///     Stack processing iteration:
 35///     <br/>
 36///     - The frame at the top of the stack is popped.
 37///       <br/>
 38///     - If the node is a leaf, the node and its incoming edge are added to the queue of subpaths of the parent node.
 39///       <br/>
 40///     - If the node has children and the queue of subpaths of the node is set, children have been already processed.
 41///       So as many paths are enqueued to the queue of subpaths of the parent node as paths in the queue of subpaths
 42///       of the node. Each subpath of the node is prepended with the node itself.
 43///       <br/>
 44///     - If the node has children and the queue of subpaths of the node is not set, children have not been processed
 45///       yet. So create a new queue for the subpaths of the node and push the node back to the stack, this time with
 46///       the queue of subpaths set. Then push all the children of the node to the stack (in reverse order), passing
 47///       the queue of subpaths of the node as queue of subpaths of the parent, and the queue of subpaths of the child
 48///       not set.
 49///     </para>
 50///     <para id="complexity">
 51///     COMPLEXITY
 52///     <br/>
 53///     - Each node is pushed to the stack and then processed at most twice (only once for leaves). So the maximum
 54///       number of items in the stack is 2 * n, where n = number of nodes in the tree.
 55///       <br/>
 56///     - The total number of paths from root to leaf is equal to the total number of leaves of the tree, which can
 57///       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
 58///       flat) or anything down to 1 (if the tree is as unbalanced as it can be).
 59///       <br/>
 60///     - Each stack processing iteration does constant time work: stack item deconstruction, check whether the node is
 61///       a leaf or not, instantiate a queue of subpaths of the node. Children are iterated, however, the total number
 62///       of children iteration over all the nodes of the tree is equal to the number of edges, which is n - 1.
 63///       <br/>
 64///     - For each non-leaf node (and there can be O(n) of those), a queue of subpaths is instantiated and populated.
 65///       Such queue can have O(n) items in it (for a flattish tree), each being a subpath of length O(n). This would
 66///       suggest a cubic complexity. However, there is at most a total of n root-to-leaf paths, each being at most of
 67///       length n, so overall Space Complexity is quadratic.
 68///       <br/>
 69///     - So Time Complexity is O(n) and Space Complexity is O(n^2).
 70///     </para>
 71/// </remarks>
 72public class FullyIterativeNodeToLeafPathsBuilder : INodeToLeafPathsBuilder
 73{
 74    private record struct StackFrame<TEdge, TNode>(
 552875        TEdge Edge,
 552876        TNode Node,
 552877        Queue<IEnumerable<KeyValuePair<TEdge, TNode>>> ParentNodeSubpaths,
 552878        Queue<IEnumerable<KeyValuePair<TEdge, TNode>>>? NodeSubpaths);
 79
 80    /// <inheritdoc path="//*[not(self::remarks)]"/>
 81    /// <inheritdoc cref="FullyIterativeNodeToLeafPathsBuilder" path="/remarks"/>
 82    public IEnumerable<TreePath<TEdge, TNode>> GetAllNodeToLeafPaths<TEdge, TNode>(TNode node)
 83        where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>
 84        where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
 39585    {
 39586        var stack = new Stack<StackFrame<TEdge, TNode>>();
 39587        var rootSubpaths = new Queue<IEnumerable<KeyValuePair<TEdge, TNode>>> { };
 88
 285589        foreach (var child in node.Children.Reverse())
 83590        {
 83591            stack.Push(new(child.Key, child.Value, rootSubpaths, null));
 83592        }
 93
 270494        while (stack.Count > 0)
 261095        {
 261096            ProcessStack(stack);
 97
 305598            while (rootSubpaths.Count > 0)
 74699                yield return new TreePath<TEdge, TNode>(rootSubpaths.Dequeue());
 2309100        }
 94101    }
 102
 103    private static void ProcessStack<TEdge, TNode>(Stack<StackFrame<TEdge, TNode>> stack)
 104        where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>
 105        where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
 2610106    {
 2610107        var (edge, node, parentNodeSubpaths, nodeSubpaths) = stack.Pop();
 108
 2610109        if (node.IsLeaf())
 826110        {
 826111            parentNodeSubpaths.Enqueue(new [] { KeyValuePair.Create(edge, node) });
 826112            return;
 113        }
 114
 1784115        if (nodeSubpaths != null)
 892116        {
 117            // Children have already been processed
 5470118            foreach (var nodeSubpath in nodeSubpaths)
 1397119                parentNodeSubpaths.Enqueue(nodeSubpath.Prepend(KeyValuePair.Create(edge, node)));
 892120        }
 121        else
 892122        {
 123            // Children have not been processed yet
 892124            nodeSubpaths = new Queue<IEnumerable<KeyValuePair<TEdge, TNode>>> { };
 892125            stack.Push(new(edge, node, parentNodeSubpaths, nodeSubpaths));
 5058126            foreach (var child in node.Children.Reverse())
 1191127            {
 1191128                stack.Push(new(child.Key, child.Value, nodeSubpaths, null));
 1191129            }
 892130        }
 2610131    }
 132}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_Edge()
get_Node()
get_ParentNodeSubpaths()
get_NodeSubpaths()
GetAllNodeToLeafPaths()
ProcessStack(System.Collections.Generic.Stack`1<MoreStructures.RecImmTrees.Paths.FullyIterativeNodeToLeafPathsBuilder/StackFrame`2<TEdge,TNode>>)