| | | 1 | | namespace MoreStructures.RecImmTrees.Visitor; |
| | | 2 | | |
| | | 3 | | /// <inheritdoc cref="IVisitStrategy{TNode, TVisitContext}" path="//*[not(self::summary or self::remarks)]"/> |
| | | 4 | | /// <summary> |
| | | 5 | | /// Base class for all tree traversal strategies, such as <see cref="DepthFirstTraversal{TEdge, TNode}"/> and |
| | | 6 | | /// <see cref="BreadthFirstTraversal{TEdge, TNode}"/> strategies, which are different strategies of traversing a |
| | | 7 | | /// <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}"/> structure top-down. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="traversal-vs-visit"> |
| | | 11 | | /// TRAVERSAL VS VISIT |
| | | 12 | | /// <br/> |
| | | 13 | | /// The word "traversal" in <see cref="TreeTraversal{TEdge, TNode}"/> and its derivations, is here used with |
| | | 14 | | /// narrower scope than the word "visit" in <see cref="IVisitStrategy{TNode, TVisitContext}"/>. |
| | | 15 | | /// <br/> |
| | | 16 | | /// - "Traversal" is used here as common class between DFS and BFS, as a visit strategy that starts from the root |
| | | 17 | | /// of the tree and proceeds downwards, following edges and terminating when leafs are reached. |
| | | 18 | | /// <br/> |
| | | 19 | | /// - "Visit" is used in a more general sense, as any algorithm which "touches" 0 or more nodes of the tree, |
| | | 20 | | /// walking the tree in any possible way (up, down, sideways, ...). |
| | | 21 | | /// </para> |
| | | 22 | | /// </remarks> |
| | | 23 | | public abstract class TreeTraversal<TEdge, TNode> |
| | | 24 | | : IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> |
| | | 25 | | where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> |
| | | 26 | | where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode> |
| | | 27 | | { |
| | | 28 | | /// <summary> |
| | | 29 | | /// The traversal order between parent and its children, to be applied when visiting the tree. By default |
| | | 30 | | /// <see cref="TreeTraversalOrder.ParentFirst"/> is applied, meaning that the parent node is visited before |
| | | 31 | | /// its children. |
| | | 32 | | /// </summary> |
| | 11250 | 33 | | public TreeTraversalOrder TraversalOrder { get; init; } = TreeTraversalOrder.ParentFirst; |
| | | 34 | | |
| | | 35 | | /// <summary> |
| | | 36 | | /// The order of visit of the children. By default <see cref="IRecImmDictIndexedTreeNode{TEdge, TNode}.Children"/> |
| | | 37 | | /// is returned as is, and no specific order is imposed to the sequence of (edge, node) couples, during the visit. |
| | | 38 | | /// </summary> |
| | | 39 | | /// <remarks> |
| | | 40 | | /// Specifying a well-defined, deterministic order ensures that children are visited in a consistent and |
| | | 41 | | /// reproducible way across executions of the visit. |
| | | 42 | | /// </remarks> |
| | | 43 | | public Func<TreeTraversalVisit<TEdge, TNode>, IEnumerable<KeyValuePair<TEdge, TNode>>> ChildrenSorter |
| | | 44 | | { |
| | 21703 | 45 | | get; |
| | 100 | 46 | | set; |
| | 20307 | 47 | | } = visit => visit.Node.Children; |
| | | 48 | | |
| | | 49 | | /// <inheritdoc/> |
| | | 50 | | /// <example> |
| | | 51 | | /// <inheritdoc cref="BreadthFirstTraversal{TEdge, TNode}" path="/example"/> |
| | | 52 | | /// </example> |
| | | 53 | | public abstract IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node); |
| | | 54 | | } |