Comment aplatir l'arbre via LINQ?

Donc j'ai un arbre simple:

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

J'ai un IEnumerable<MyNode>. Je veux obtenir une liste de tous MyNode(y compris les objets de nœud interne ( Elements)) sous la forme d'une liste plate Where group == 1. Comment faire une telle chose via LINQ?

Vous pouvez aplatir un arbre comme ceci:

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

Vous pouvez ensuite filtrer en grouputilisant Where(...).

Pour gagner des "points pour le style", convertissez-vous Flattenen une fonction d'extension dans une classe statique.

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

Pour gagner plus de points pour un "style encore meilleur", convertissez-vous Flattenen une méthode d'extension générique qui prend un arbre et une fonction qui produit des descendants à partir d'un nœud:

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

Appelez cette fonction comme ceci:

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

Si vous préférez aplatir en pré-commande plutôt qu'en post-commande, changez les côtés du fichier Concat(...).

Le problème avec la réponse acceptée est qu'elle est inefficace si l'arbre est profond. Si l'arbre est très profond, il fait exploser la pile. Vous pouvez résoudre le problème en utilisant une pile explicite:

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);
    }
}

En supposant n nœuds dans un arbre de hauteur h et un facteur de branchement considérablement inférieur à n, cette méthode est O (1) dans l'espace de pile, O (h) dans l'espace de tas et O (n) dans le temps. L'autre algorithme donné est O (h) dans la pile, O (1) dans le tas et O (nh) dans le temps. Si le facteur de branchement est petit par rapport à n, alors h est compris entre O (lg n) et O (n), ce qui montre que l'algorithme naïf peut utiliser une quantité dangereuse de pile et une grande quantité de temps si h est proche de n.

Maintenant que nous avons un parcours, votre requête est simple:

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

Pour être complet, voici la combinaison des réponses de dasblinkenlight et d'Eric Lippert. Unité testée et tout. :-)

 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);
     }
 }

Mettre à jour:

Pour les personnes intéressées par le niveau de nidification (profondeur). L'un des avantages de l'implémentation explicite de la pile d'énumérateurs est qu'à tout moment (et en particulier lors de la production de l'élément), le stack.Countreprésente la profondeur de traitement en cours. Donc, en prenant cela en compte et en utilisant les tuples de valeur C # 7.0, nous pouvons simplement modifier la déclaration de méthode comme suit:

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

et yielddéclaration:

yield return (item, stack.Count);

Ensuite, nous pouvons implémenter la méthode originale en appliquant simple Selectsur ce qui précède:

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

Original:

Étonnamment, personne (même Eric) n'a montré le port itératif "naturel" d'un DFT de pré-commande récursif, alors le voici:

    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();
        }
    }

J'ai trouvé quelques petits problèmes avec les réponses données ici:

• Que faire si la liste initiale d'éléments est nulle?
• Que faire s'il y a une valeur nulle dans la liste des enfants?

Basé sur les réponses précédentes et est venu avec ce qui suit:

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);
        }
    }
}

Et les tests unitaires:

[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; }
    }
}

Au cas où quelqu'un d'autre trouverait cela, mais aurait également besoin de connaître le niveau après avoir aplati l'arbre, cela étend la combinaison de Konamiman de dasblinkenlight et des solutions d'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));
        }
    }

Une autre option consiste à avoir une conception OO appropriée.

par exemple, demandez au MyNodepour retourner tout aplatir.

Comme ça:

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());
    }
}

Vous pouvez maintenant demander au MyNode de niveau supérieur d'obtenir tous les nœuds.

var flatten = topNode.GetAllNodes();

Si vous ne pouvez pas modifier la classe, ce n'est pas une option. Mais sinon, je pense que cela pourrait être préféré d'une méthode LINQ séparée (récursive).

Ceci utilise LINQ, donc je pense que cette réponse est applicable ici;)

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;
}

Combiner la réponse de Dave et Ivan Stoev au cas où vous auriez besoin du niveau d'imbrication et de la liste aplatie "dans l'ordre" et non inversée comme dans la réponse donnée par 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();
            }
        }
    }

Sur la base de la réponse de Konamiman et du commentaire selon lequel la commande est inattendue, voici une version avec un paramètre de tri explicite:

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);
    }
}

Et un exemple d'utilisation:

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

Vous trouverez ci-dessous le code d'Ivan Stoev avec la fonctionnalité supplémentaire de dire l'index de chaque objet dans le chemin. Par exemple, recherchez "Item_120":

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

retournerait l'élément et un tableau int [1,2,0]. Évidemment, le niveau d'imbrication est également disponible, en tant que longueur du tableau.

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();
    }
}

Voici quelques implémentations prêtes à l'emploi utilisant Queue et renvoyant l'arborescence Flatten moi d'abord, puis mes enfants.

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 temps en temps, j'essaie de gratter ce problème et de concevoir ma propre solution qui prend en charge des structures arbitrairement profondes (pas de récursivité), effectue une première traversée en largeur et n'abuse pas trop de requêtes LINQ ou n'exécute pas de manière préventive la récursivité sur les enfants. Après avoir fouillé dans la source .NET et essayé de nombreuses solutions, j'ai enfin trouvé cette solution. Cela a fini par être très proche de la réponse d'Ian Stoev (dont je n'ai vu que la réponse tout à l'heure), mais la mienne n'utilise pas de boucles infinies ou n'a pas de flux de code inhabituel.

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();
        }
    }
}

Un exemple fonctionnel peut être trouvé ici .