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

La plupart des réponses présentées ici produisent profondeur d'abord ou des séquences en zig-zag. Par exemple, à partir de l'arbre ci-dessous :

        1                   2 
       / \                 / \
      /   \               /   \
     /     \             /     \
    /       \           /       \
   11       12         21       22
  / \       / \       / \       / \
 /   \     /   \     /   \     /   \
111 112   121 122   211 212   221 222

dasblinkenlight's réponse produit cette séquence aplatie :

111, 112, 121, 122, 11, 12, 211, 212, 221, 222, 21, 22, 1, 2

Konamiman réponse (qui généralise la méthode d'Eric Lippert réponse ) produit cette séquence aplatie :

2, 22, 222, 221, 21, 212, 211, 1, 12, 122, 121, 11, 112, 111

Ivan Stoev réponse produit cette séquence aplatie :

1, 11, 111, 112, 12, 121, 122, 2, 21, 211, 212, 22, 221, 222

Si vous êtes intéressé par un en premier lieu séquence comme celle-ci :

1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222

...alors cette solution est faite pour vous :

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector)
{
    var queue = new Queue<T>(source);
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        yield return current;
        var children = childrenSelector(current);
        if (children == null) continue;
        foreach (var child in children) queue.Enqueue(child);
    }
}

La différence dans l'implémentation consiste essentiellement à utiliser une Queue au lieu d'un Stack . Aucun tri réel n'a lieu.

---

Attention : cette implémentation est loin d'être optimale en ce qui concerne l'efficacité de la mémoire, puisqu'un grand pourcentage du nombre total d'éléments finira par être stocké dans la file d'attente interne pendant l'énumération. Stack -sont beaucoup plus efficaces en termes d'utilisation de la mémoire que les parcours d'arbres basés sur les Queue -Les implémentations basées sur l'Internet.

Answer 2

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

Answer 3

Une autre option est d'avoir une véritable conception OO.

Par exemple, demandez au MyNode pour retourner tous les aplatissements.

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

Maintenant vous pouvez demander au niveau supérieur MyNode d'obtenir tous les noeuds.

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é à une méthode LINQ séparée (récursive).

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

Answer 4

Combinaison des réponses de Dave et d'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();
            }
        }
    }

Answer 5

Voici une implémentation prête à l'emploi utilisant une file d'attente et renvoyant l'arbre Flatten moi d'abord et ensuite 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);
            }
        }

    }