Feedback

C# - TreeEnumerator

Veröffentlicht von am 02.11.2015
(0 Bewertungen)
Die Klasse TreeEnumerable enthält Erweiterungsmethoden welche es erlauben die Elemente von hierarchischen Objektstrukturen linear (als IEnumerable<T>) zu durchlaufen.

Die Elemente können dabei entweder "depth first" oder "breadth first" durchlaufen werden.
using System;
using System.Collections.Generic;
  /// <summary>
  ///   Provides a set of static extension methods, which supports simple iteration
  ///   over a graph stuctures.
  /// </summary>
  public static class TreeEnumerable
  {
    #region BreadthFirst

    /// <summary>
    ///   Linearizes the specified graph, traversing it breadth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                         Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      Queue<TNode> queue = new Queue<TNode>(256);

      foreach (TNode node in nodes)
      {
        queue.Enqueue(node);
      }

      return BreadthFirst(queue, getSubNodes);
    }

    private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
                                                          Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      TNode node;

      while (queue.Count > 0)
      {
        node = queue.Dequeue();

        if (node == null)
        {
          yield break;
        }

        foreach (TNode subNode in getSubNodes(node))
        {
          queue.Enqueue(subNode);
        }

        yield return node;
      }
    }

    #endregion

    #region BreadthFirst (repeat Nodes)

    /// <summary>
    ///   Linearizes the specified graph, traversing it breadth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <param name="repeatNodes">
    ///   A value that determines if nodes are being traversed repeated.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                         Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                         Boolean repeatNodes)
    {
      HashSet<TNode> passedNodes = new HashSet<TNode>();
      Queue<TNode> queue = new Queue<TNode>(256);

      if (repeatNodes)
      {
        return nodes.BreadthFirst(getSubNodes);
      }

      foreach (TNode node in nodes)
      {
        if (passedNodes.Contains(node))
        {
          continue;
        }

        passedNodes.Add(node);

        queue.Enqueue(node);
      }

      return BreadthFirst(queue, getSubNodes, passedNodes);
    }

    private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
                                                          Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                          HashSet<TNode> passedNodes)
    {
      TNode node;

      while (queue.Count > 0)
      {
        node = queue.Dequeue();

        if (node == null)
        {
          yield break;
        }

        foreach (TNode subNode in getSubNodes(node))
        {
          if (passedNodes.Contains(subNode))
          {
            continue;
          }

          passedNodes.Add(subNode);

          queue.Enqueue(subNode);
        }

        yield return node;
      }
    }

    #endregion
  

    #region DepthFirst

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="node">
    ///   A node that represents the root element of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(TNode node, Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      return new[] { node }.DepthFirst(getSubNodes);
    }

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                       Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      foreach (TNode node in nodes)
      {
        yield return node;

        foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes))
        {
          yield return subNode;
        }
      }
    }

    #endregion

    #region DepthFirst (repeat Nodes)

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <param name="repeatNodes">
    ///   A value that determines if nodes are being traversed repeated.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                       Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                       Boolean repeatNodes)
    {
      if (repeatNodes)
      {
        return nodes.DepthFirst(getSubNodes);
      }

      return nodes.DepthFirst(getSubNodes, new HashSet<TNode>());
    }

    private static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                        Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                        HashSet<TNode> passedNodes)
    {
      foreach (TNode node in nodes)
      {
        if (passedNodes.Contains(node))
        {
          continue;
        }

        passedNodes.Add(node);

        yield return node;

        foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes, passedNodes))
        {
          yield return subNode;
        }
      }
    }

    #endregion
  }
Abgelegt unter LINQ, Baumstruktur.

1 Kommentare zum Snippet

Tachyon schrieb am 02.11.2015:
Usage:

// class Item { public Item[] Items { get; set; } }
var allItemsDepthFirst = items.DepthFirst(i => i.Items);
var allItemsBreadthFirst = items.BreadthFirst(i => i.Items);
 

Logge dich ein, um hier zu kommentieren!