¿Cómo aplanar un árbol a través de LINQ?

Entonces tengo un árbol simple:

class MyNode
{
 public MyNode Parent;
 public IEnumerable<MyNode> Elements;
 int group = 1;
}

Tengo un IEnumerable<MyNode>. Quiero obtener una lista de todos MyNode(incluidos los objetos de nodo interno ( Elements)) como una lista plana Where group == 1. ¿Cómo hacer tal cosa a través de LINQ?

Puedes aplanar un árbol como este:

IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
    e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });

A continuación, puede filtrar grouputilizando Where(...).

Para ganar algunos "puntos por estilo", conviértalo Flattenen una función de extensión en una clase estática.

public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

Para ganar más puntos por "un estilo aún mejor", conviértalo Flattena un método de extensión genérico que toma un árbol y una función que produce descendientes de un nodo:

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e
,   Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

Llame a esta función así:

IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);

Si prefiere aplanar en preorden en lugar de posorder, cambie los lados del Concat(...).

El problema con la respuesta aceptada es que es ineficaz si el árbol es profundo. Si el árbol es muy profundo, hace volar la pila. Puede resolver el problema utilizando una pila explícita:

public static IEnumerable<MyNode> Traverse(this MyNode root)
{
    var stack = new Stack<MyNode>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Elements)
            stack.Push(child);
    }
}

Suponiendo n nodos en un árbol de altura h y un factor de ramificación considerablemente menor que n, este método es O (1) en el espacio de la pila, O (h) en el espacio del montón y O (n) en el tiempo. El otro algoritmo dado es O (h) en la pila, O (1) en el montón y O (nh) en el tiempo. Si el factor de ramificación es pequeño en comparación con n, entonces h está entre O (lg n) y O (n), lo que ilustra que el algoritmo ingenuo puede usar una cantidad peligrosa de pila y una gran cantidad de tiempo si h está cerca de n.

Ahora que tenemos un recorrido, su consulta es sencilla:

root.Traverse().Where(item=>item.group == 1);

Solo para completar, aquí está la combinación de las respuestas de dasblinkenlight y Eric Lippert. Unidad probada y todo. :-)

 public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items,
        Func<T, IEnumerable<T>> getChildren)
 {
     var stack = new Stack<T>();
     foreach(var item in items)
         stack.Push(item);

     while(stack.Count > 0)
     {
         var current = stack.Pop();
         yield return current;

         var children = getChildren(current);
         if (children == null) continue;

         foreach (var child in children) 
            stack.Push(child);
     }
 }

Actualizar:

Para personas interesadas en el nivel de anidación (profundidad). Una de las cosas buenas de la implementación explícita de la pila de enumeradores es que en cualquier momento (y en particular cuando se obtiene el elemento) stack.Countrepresenta la profundidad de procesamiento actual. Entonces, teniendo esto en cuenta y utilizando las tuplas de valor de C # 7.0, podemos simplemente cambiar la declaración del método de la siguiente manera:

public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)

y yielddeclaración:

yield return (item, stack.Count);

Entonces podemos implementar el método original aplicando simple Selecten lo anterior:

public static IEnumerable<T> Expand<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
    source.ExpandWithLevel(elementSelector).Select(e => e.Item);

Original:

Sorprendentemente, nadie (ni siquiera Eric) mostró el puerto iterativo "natural" de una DFT recursiva de reserva, así que aquí está:

    public static IEnumerable<T> Expand<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }

Encontré algunos pequeños problemas con las respuestas dadas aquí:

• ¿Qué pasa si la lista inicial de elementos es nula?
• ¿Qué pasa si hay un valor nulo en la lista de hijos?

Se basó en las respuestas anteriores y se le ocurrió lo siguiente:

public static class IEnumerableExtensions
{
    public static IEnumerable<T> Flatten<T>(
        this IEnumerable<T> items, 
        Func<T, IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var stack = new Stack<T>(items);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;

            if (current == null) continue;

            var children = getChildren(current);
            if (children == null) continue;

            foreach (var child in children)
                stack.Push(child);
        }
    }
}

Y las pruebas unitarias:

[TestClass]
public class IEnumerableExtensionsTests
{
    [TestMethod]
    public void NullList()
    {
        IEnumerable<Test> items = null;
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void EmptyList()
    {
        var items = new Test[0];
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(0, flattened.Count());
    }
    [TestMethod]
    public void OneItem()
    {
        var items = new[] { new Test() };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(1, flattened.Count());
    }
    [TestMethod]
    public void OneItemWithChild()
    {
        var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i.Id == 2));
    }
    [TestMethod]
    public void OneItemWithNullChild()
    {
        var items = new[] { new Test { Id = 1, Children = new Test[] { null } } };
        var flattened = items.Flatten(i => i.Children);
        Assert.AreEqual(2, flattened.Count());
        Assert.IsTrue(flattened.Any(i => i.Id == 1));
        Assert.IsTrue(flattened.Any(i => i == null));
    }
    class Test
    {
        public int Id { get; set; }
        public IEnumerable<Test> Children { get; set; }
    }
}

En caso de que alguien más encuentre esto, pero también necesite saber el nivel después de haber aplanado el árbol, esto amplía la combinación de Konamiman de dasblinkenlight y las soluciones de Eric Lippert:

    public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(
            this IEnumerable<T> items,
            Func<T, IEnumerable<T>> getChilds)
    {
        var stack = new Stack<Tuple<T, int>>();
        foreach (var item in items)
            stack.Push(new Tuple<T, int>(item, 1));

        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;
            foreach (var child in getChilds(current.Item1))
                stack.Push(new Tuple<T, int>(child, current.Item2 + 1));
        }
    }

Una opción realmente diferente es tener un diseño orientado a objetos adecuado.

por ejemplo, pregunte al MyNode que devuelva todo aplanar.

Me gusta esto:

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;

    public IEnumerable<MyNode> GetAllNodes()
    {
        if (Elements == null)
        {
            return Enumerable.Empty<MyNode>(); 
        }

        return Elements.SelectMany(e => e.GetAllNodes());
    }
}

Ahora puede pedirle al MyNode de nivel superior que obtenga todos los nodos.

var flatten = topNode.GetAllNodes();

Si no puede editar la clase, esta no es una opción. Pero de lo contrario, creo que esto podría preferirse de un método LINQ separado (recursivo).

Esto está usando LINQ, así que creo que esta respuesta es aplicable aquí;)

void Main()
{
    var allNodes = GetTreeNodes().Flatten(x => x.Elements);

    allNodes.Dump();
}

public static class ExtensionMethods
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null)
    {
        if (source == null)
        {
            return new List<T>();
        }

        var list = source;

        if (childrenSelector != null)
        {
            foreach (var item in source)
            {
                list = list.Concat(childrenSelector(item).Flatten(childrenSelector));
            }
        }

        return list;
    }
}

IEnumerable<MyNode> GetTreeNodes() {
    return new[] { 
        new MyNode { Elements = new[] { new MyNode() }},
        new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }}
    };
}

class MyNode
{
    public MyNode Parent;
    public IEnumerable<MyNode> Elements;
    int group = 1;
}

Combinando la respuesta de Dave e Ivan Stoev en caso de que necesite el nivel de anidamiento y la lista aplanada "en orden" y no invertida como en la respuesta dada por Konamiman.

 public static class HierarchicalEnumerableUtils
    {
        private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level)
        {
            if (source == null)
            {
                return null;
            }
            else
            {
                return source.Select(item => new Tuple<T, int>(item, level));
            }
        }

        public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
        {
            var stack = new Stack<IEnumerator<Tuple<T, int>>>();
            var leveledSource = source.ToLeveled(0);
            var e = leveledSource.GetEnumerator();
            try
            {
                while (true)
                {
                    while (e.MoveNext())
                    {
                        var item = e.Current;
                        yield return item;
                        var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1);
                        if (elements == null) continue;
                        stack.Push(e);
                        e = elements.GetEnumerator();
                    }
                    if (stack.Count == 0) break;
                    e.Dispose();
                    e = stack.Pop();
                }
            }
            finally
            {
                e.Dispose();
                while (stack.Count != 0) stack.Pop().Dispose();
            }
        }
    }

Sobre la base de la respuesta de Konamiman y el comentario de que el orden es inesperado, aquí hay una versión con un parámetro de clasificación explícito:

public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy)
{
    var stack = new Stack<T>();
    foreach (var item in items.OrderBy(orderBy))
        stack.Push(item);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;

        var children = nested(current).OrderBy(orderBy);
        if (children == null) continue;

        foreach (var child in children)
            stack.Push(child);
    }
}

Y un uso de muestra:

var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();

A continuación se muestra el código de Ivan Stoev con la característica adicional de decir el índice de cada objeto en la ruta. Por ejemplo, busque "Item_120":

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

devolvería el elemento y una matriz int [1,2,0]. Obviamente, el nivel de anidamiento también está disponible, como longitud de la matriz.

public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
    var stack = new Stack<IEnumerator<T>>();
    var e = source.GetEnumerator();
    List<int> indexes = new List<int>() { -1 };
    try {
        while (true) {
            while (e.MoveNext()) {
                var item = e.Current;
                indexes[stack.Count]++;
                yield return (item, indexes.Take(stack.Count + 1).ToArray());
                var elements = getChildren(item);
                if (elements == null) continue;
                stack.Push(e);
                e = elements.GetEnumerator();
                if (indexes.Count == stack.Count)
                    indexes.Add(-1);
                }
            if (stack.Count == 0) break;
            e.Dispose();
            indexes[stack.Count] = -1;
            e = stack.Pop();
        }
    } finally {
        e.Dispose();
        while (stack.Count != 0) stack.Pop().Dispose();
    }
}

Aquí hay una implementación lista para usar usando Queue y devolviéndome el árbol Flatten primero y luego a mis hijos.

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> items, 
    Func<T,IEnumerable<T>> getChildren)
    {
        if (items == null)
            yield break;

        var queue = new Queue<T>();

        foreach (var item in items) {
            if (item == null)
                continue;

            queue.Enqueue(item);

            while (queue.Count > 0) {
                var current = queue.Dequeue();
                yield return current;

                if (current == null)
                    continue;

                var children = getChildren(current);
                if (children == null)
                    continue;

                foreach (var child in children)
                    queue.Enqueue(child);
            }
        }

    }

De vez en cuando trato de abordar este problema e idear mi propia solución que admita estructuras arbitrariamente profundas (sin recursividad), realice un primer recorrido amplio y no abuse de demasiadas consultas LINQ o ejecute de forma preventiva la recursividad en los hijos. Después de buscar en la fuente .NET y probar muchas soluciones, finalmente se me ocurrió esta solución. Terminó estando muy cerca de la respuesta de Ian Stoev (cuya respuesta solo vi ahora), sin embargo, la mía no utiliza bucles infinitos ni tiene un flujo de código inusual.

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> fnRecurse)
{
    if (source != null)
    {
        Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
        try
        {
            enumerators.Push(source.GetEnumerator());
            while (enumerators.Count > 0)
            {
                var top = enumerators.Peek();
                while (top.MoveNext())
                {
                    yield return top.Current;

                    var children = fnRecurse(top.Current);
                    if (children != null)
                    {
                        top = children.GetEnumerator();
                        enumerators.Push(top);
                    }
                }

                enumerators.Pop().Dispose();
            }
        }
        finally
        {
            while (enumerators.Count > 0)
                enumerators.Pop().Dispose();
        }
    }
}

Puede encontrar un ejemplo práctico aquí .