Comment aplatir un arbre via LINQ ?

Question

J'ai donc 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 les MyNode (y compris les objets de nœuds internes ( Elements )) comme une liste plate Where group == 1 . Comment faire une telle chose via LINQ ?

Answer 1

Tu peux aplatir un arbre comme ça :

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

Vous pouvez ensuite filtrer par group en utilisant Where(...) .

Pour gagner quelques "points pour le style", convertissez Flatten à une fonction d'extension dans une classe statique.

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

Pour gagner des points pour "un style encore meilleur", convertissez Flatten à une méthode d'extension générique qui prend un arbre et une fonction qui produit des descendants :

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> e,
    Func<T,IEnumerable<T>> f) 
{
    return 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, intervertissez les côtés du Concat(...) .

Answer 2

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, puis il fait sauter la pile. Vous pouvez résoudre ce 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 des nœuds dans un arbre de hauteur h et un facteur de branchement considérablement inférieur à n, cette méthode est O(1) en espace de pile, O(h) en espace de tas et O(n) en temps. L'autre algorithme donné est O(h) en pile, O(1) en tas et O(nh) en temps. Si le facteur de branchement est petit par rapport à n, alors h est entre O(lg n) et O(n), ce qui illustre 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 une traversée, votre requête est simple :

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

Answer 3

Par souci d'exhaustivité, voici la combinaison des réponses de dasblinkenlight et d'Eric Lippert. Testé à l'unité et tout le reste :-)

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

Answer 4

Mise à jour :

Pour les personnes intéressées par le niveau d'emboîtement (profondeur). L'une des bonnes choses de l'implémentation explicite de la pile d'énumérateurs est qu'à tout moment (et en particulier lors de la cession de l'élément), l'élément stack.Count représente la profondeur de traitement actuelle. En prenant cela en compte et en utilisant les tuples de valeur de C#7.0, nous pouvons simplement modifier la déclaration de la méthode comme suit :

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

et yield déclaration :

yield return (item, stack.Count);

Ensuite, nous pouvons mettre en œuvre la méthode originale en appliquant une simple Select sur 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 portage itératif "naturel" d'une DFT récursive de pré-ordre, 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();
        }
    }

Answer 5

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

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

À partir des réponses précédentes, j'ai obtenu les résultats suivants :

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