Wie kann man einen Baum über LINQ abflachen?

94

Also habe ich einen einfachen Baum:

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

Ich habe eine IEnumerable<MyNode>. Ich möchte eine Liste aller MyNode(einschließlich der Objekte des inneren Knotens ( Elements)) als eine flache Liste erhalten Where group == 1. Wie mache ich so etwas über LINQ?

myWallJSON
quelle
1
In welcher Reihenfolge soll die abgeflachte Liste sein?
Philip
1
Wann haben Knoten keine untergeordneten Knoten mehr? Ich nehme an, es ist wann Elementsist null oder leer?
Adam Houldsworth
Der einfachste / klarste Weg, dies zu beheben, ist die Verwendung einer rekursiven LINQ-Abfrage. Diese Frage: stackoverflow.com/questions/732281/expressing-recursion-in-linq hat viele Diskussionen darüber, und diese spezielle Antwort geht detailliert darauf ein, wie Sie sie implementieren würden.
Alvaro Rodriguez

Antworten:

137

Sie können einen Baum wie folgt abflachen:

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

Anschließend können Sie filtern , indem Sie groupmit Where(...).

Konvertieren Sie Flattenin eine Erweiterungsfunktion in einer statischen Klasse, um einige "Punkte für Stil" zu erhalten.

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

Um mehr Punkte für einen "noch besseren Stil" zu erhalten, konvertieren Sie Flattenin eine generische Erweiterungsmethode, die einen Baum und eine Funktion verwendet, die Nachkommen von einem Knoten erzeugt:

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

Rufen Sie diese Funktion folgendermaßen auf:

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

Wenn Sie das Abflachen lieber in der Vorbestellung als in der Nachbestellung bevorzugen, wechseln Sie die Seiten des Concat(...).

dasblinkenlight
quelle
@AdamHouldsworth Danke für die Bearbeitung! Das Element im Aufruf von Concatsollte sein new[] {e}, nicht new[] {c}(es würde dort nicht einmal kompilieren c).
Dasblinkenlight
Ich bin anderer Meinung: kompiliert, getestet und gearbeitet c. Verwenden ekompiliert nicht. Sie können auch hinzufügen if (e == null) return Enumerable.Empty<T>();, um mit untergeordneten Nulllisten fertig zu werden.
Adam Houldsworth
1
eher wie `public static IEnumerable <T> Flatten <T> (diese IEnumerable <T> -Quelle, Func <T, IEnumerable <T>> f) {if (source == null) return Enumerable.Empty <T> (); return source.SelectMany (c => f (c) .Flatten (f)). Concat (source); } `
myWallJSON
10
Beachten Sie, dass diese Lösung O (nh) ist, wobei n die Anzahl der Elemente im Baum und h die durchschnittliche Tiefe des Baums ist. Da h zwischen O (1) und O (n) liegen kann, liegt dies zwischen einem O (n) - und einem O (n-Quadrat) -Algorithmus. Es gibt bessere Algorithmen.
Eric Lippert
1
Ich habe festgestellt, dass die Funktion der abgeflachten Liste keine Elemente hinzufügt, wenn die Liste IEnumerable <baseType> ist. Sie können dies lösen, indem Sie die Funktion wie folgt aufrufen: var res = tree.Flatten (node ​​=> node.Elements.OfType <DerivedType>)
Frank Horemans
125

Das Problem mit der akzeptierten Antwort ist, dass es ineffizient ist, wenn der Baum tief ist. Wenn der Baum sehr tief ist, bläst er den Stapel. Sie können das Problem mithilfe eines expliziten Stapels lösen:

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

Unter der Annahme von n Knoten in einem Baum der Höhe h und einem Verzweigungsfaktor, der erheblich kleiner als n ist, ist diese Methode O (1) im Stapelraum, O (h) im Heapraum und O (n) in der Zeit. Der andere angegebene Algorithmus ist O (h) im Stapel, O (1) im Heap und O (nh) in der Zeit. Wenn der Verzweigungsfaktor im Vergleich zu n klein ist, liegt h zwischen O (lg n) und O (n), was zeigt, dass der naive Algorithmus eine gefährliche Menge an Stapel und eine große Zeit verwenden kann, wenn h nahe an n liegt.

Jetzt, da wir eine Durchquerung haben, ist Ihre Anfrage unkompliziert:

root.Traverse().Where(item=>item.group == 1);
Eric Lippert
quelle
3
@ Johnnycardy: Wenn Sie einen Punkt argumentieren wollten, dann ist der Code vielleicht nicht offensichtlich korrekt. Was könnte es klarer richtig machen?
Eric Lippert
3
@ebramtharwat: Richtig. Sie können Traversealle Elemente aufrufen . Sie können Traverseauch eine Sequenz ändern , um alle Elemente der Sequenz darauf zu übertragen stack. Denken Sie daran, stackist "Elemente, die ich noch nicht durchlaufen habe". Oder Sie können eine "Dummy" -Wurzel erstellen, in der Ihre Sequenz aus untergeordneten Elementen besteht, und dann die Dummy-Wurzel durchlaufen.
Eric Lippert
2
Wenn Sie dies tun, erhalten foreach (var child in current.Elements.Reverse())Sie eine erwartete Abflachung. Insbesondere werden Kinder in der Reihenfolge angezeigt, in der sie erscheinen, und nicht das letzte Kind zuerst. Dies sollte in den meisten Fällen keine Rolle spielen, aber in meinem Fall musste die Abflachung in einer vorhersehbaren und erwarteten Reihenfolge erfolgen.
Micah Zoltu
2
@MicahZoltu, Sie könnten das vermeiden, .Reverseindem Sie das Stack<T>gegen einQueue<T>
Rubens Farias
2
@MicahZoltu Sie haben Recht mit der Reihenfolge, aber das Problem Reverseist, dass zusätzliche Iteratoren erstellt werden, was durch diesen Ansatz vermieden werden soll . @RubensFarias Das Ersetzen Queuevon StackErgebnissen führt zu einer Durchquerung der Breite.
Jack A.
25

Der Vollständigkeit halber hier die Kombination der Antworten von dasblinkenlight und Eric Lippert. Gerät getestet und alles. :-)

 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);
     }
 }
Konamiman
quelle
3
Um NullReferenceException zu vermeiden var children = getChildren (current); if (Kinder! = null) {foreach (var Kind in Kindern) stack.Push (Kind); }
Serg
2
Ich möchte darauf hinweisen, dass die Liste zwar abgeflacht, aber in umgekehrter Reihenfolge zurückgegeben wird. Das letzte Element wird das erste usw.
Corcus
21

Aktualisieren:

Für Leute, die sich für das Verschachtelungsniveau (Tiefe) interessieren. Eines der guten Dinge bei der Implementierung eines expliziten Enumerator-Stacks ist, dass zu jedem Zeitpunkt (und insbesondere bei der Ausgabe des Elements) stack.Countdie aktuelle Verarbeitungstiefe dargestellt wird. Wenn wir dies berücksichtigen und die C # 7.0-Wertetupel verwenden, können wir die Methodendeklaration einfach wie folgt ändern:

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

und yieldAussage:

yield return (item, stack.Count);

Dann können wir die ursprüngliche Methode implementieren, indem wir einfach Folgendes anwenden Select:

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

Original:

Überraschenderweise zeigte niemand (selbst Eric) den "natürlichen" iterativen Port einer rekursiven DFT vor der Bestellung. Hier ist es also:

    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();
        }
    }
Ivan Stoev
quelle
Ich gehe davon aus, dass Sie ejedes Mal wechseln, wenn Sie anrufen elementSelector, um die Vorbestellung aufrechtzuerhalten. Wenn die Reihenfolge keine Rolle spielt, können Sie dann die Funktion ändern, um alle eeinmal gestarteten Vorgänge zu verarbeiten ?
NetMage
@ NetMage Ich wollte speziell vorbestellen. Mit Kleingeld kann es Nachbestellungen abwickeln. Aber der Hauptpunkt ist, dass dies Depth First Traversal ist . Für Breath First Traversal würde ich verwenden Queue<T>. Wie auch immer, die Idee hier ist, einen kleinen Stapel mit Enumeratoren zu behalten, der dem sehr ähnlich ist, was in der rekursiven Implementierung geschieht.
Ivan Stoev
@IvanStoev Ich dachte, der Code würde vereinfacht. Ich denke, die Verwendung von Stackwürde zu einer Zick-Zack-Breite der ersten Durchquerung führen.
NetMage
7

Ich habe einige kleine Probleme mit den hier gegebenen Antworten gefunden:

  • Was ist, wenn die anfängliche Liste der Elemente null ist?
  • Was ist, wenn die Liste der Kinder einen Nullwert enthält?

Aufbauend auf den vorherigen Antworten und mit den folgenden Ergebnissen:

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

Und die Unit-Tests:

[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; }
    }
}
Doug Clutter
quelle
4

Falls jemand anderes dies findet, aber auch das Level kennen muss, nachdem er den Baum abgeflacht hat, erweitert dies Konamimans Kombination aus Dasblinkenlight und Eric Lipperts Lösungen:

    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));
        }
    }
Dave
quelle
2

Eine wirklich andere Option ist ein korrektes OO-Design.

Bitten Sie zB die MyNode, alle Abflachungen zurückzugeben.

So was:

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

Jetzt können Sie den MyNode der obersten Ebene bitten, alle Knoten abzurufen.

var flatten = topNode.GetAllNodes();

Wenn Sie die Klasse nicht bearbeiten können, ist dies keine Option. Ansonsten könnte dies meiner Meinung nach einer separaten (rekursiven) LINQ-Methode vorgezogen werden.

Dies verwendet LINQ, daher denke ich, dass diese Antwort hier anwendbar ist;)

julianisch
quelle
Vielleicht Enumerabl.Empty besser als neue Liste?
Frank
1
Tatsächlich! Aktualisiert!
Julian
0
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;
}
Tom Brothers
quelle
1
Wenn Sie in Ihrer Erweiterung ein foreach verwenden, bedeutet dies, dass die Ausführung nicht mehr verzögert wird (es sei denn, Sie verwenden natürlich die Ertragsrendite).
Tri Q Tran
0

Kombinieren Sie die Antwort von Dave und Ivan Stoev, falls Sie die Verschachtelungsebene benötigen und die Liste "in der richtigen Reihenfolge" abgeflacht und nicht wie in der Antwort von Konamiman umgekehrt.

 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();
            }
        }
    }
Corcus
quelle
Es wäre auch schön, zuerst die Tiefe oder zuerst die Breite angeben zu können ...
Hugh,
0

Aufbauend auf Konamimans Antwort und dem Kommentar, dass die Reihenfolge unerwartet ist, ist hier eine Version mit einem expliziten Sortierparameter:

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

Und ein Beispiel für die Verwendung:

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

Unten finden Sie den Code von Ivan Stoev mit der zusätzlichen Funktion, den Index jedes Objekts im Pfad zu ermitteln. ZB nach "Item_120" suchen:

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

würde das Element und ein int-Array [1,2,0] zurückgeben. Offensichtlich ist auch die Verschachtelungsebene als Länge des Arrays verfügbar.

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();
    }
}
lisz
quelle
Hallo, @lisz, wo fügst du diesen Code ein? Ich erhalte Fehler wie "Der Modifikator 'public' ist für diesen Artikel nicht gültig", "Der Modifikator 'static' ist für diesen Artikel nicht gültig"
Kynao
0

Hier einige gebrauchsfertige Implementierung mit Queue und Rückgabe des Flatten-Baums zuerst an mich und dann an meine Kinder.

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

    }
Ruben Alfonso
quelle
0

Hin und wieder versuche ich, dieses Problem zu lösen und eine eigene Lösung zu finden, die willkürlich tiefe Strukturen unterstützt (keine Rekursion), eine erste Durchquerung in der Breite durchführt und nicht zu viele LINQ-Abfragen missbraucht oder präventiv eine Rekursion für die Kinder ausführt. Nachdem ich mich in der .NET-Quelle umgesehen und viele Lösungen ausprobiert habe, habe ich endlich diese Lösung gefunden. Es war sehr nah an Ian Stoevs Antwort (deren Antwort ich erst jetzt gesehen habe), aber meine verwendet keine Endlosschleifen oder hat einen ungewöhnlichen Codefluss.

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

Ein Arbeitsbeispiel finden Sie hier .

Chris
quelle