C#: Vermeiden Sie eine unendliche Rekursion bei der Traversierung graph-Objekt

Habe ich ein graph-Objekt, wobei jedes child-Objekt enthält eine Eigenschaft, die verweist zurück auf seine Eltern. Gibt es gute Strategien für das ignorieren der parent-Verweise um zu vermeiden, dass eine unendliche Rekursion? Ich habe gedacht, hinzufügen von einem speziellen [Parent] - Attribut, um diese Eigenschaften oder Verwendung eine Besondere Namenskonvention, aber vielleicht gibt es einen besseren Weg.

Ich glaube nicht, dass ein Eltern/Kind-Beziehung inhärent führt zu einer unendlichen Rekursion. Es wäre hilfreich, wenn Sie zeigte den code, der das problem verursacht.
wenn Sie bi-direktional Schiffbarkeit auf der Eltern-Kind-Beziehung (Sie können navigieren Sie die Beziehung in beide Richtungen), dann hast du infintite Rekursion. Das Elternteil hat eine Eigenschaft, die führt zu das Kind hat eine Eigenschaft, die führt zurück zu den Eltern, die eine Eigenschaft aufweist, führt zu dem Kind, die hat eine Eigenschaft.... etc etc
Levine: ich bin sicher, Sie werden Zustimmen, dass, ob oder nicht, die eine parent/child-Beziehung wird zu einer unendlichen Rekursion führen, hängt von der Art und Weise, die Sie durchqueren das Objekt graph.
Auch ohne parent-Zeiger, gibt es ein problem. Könnte es Zyklen im Graphen, die nicht mit den Eltern. Eine gute graph-traversal Algorithmus berücksichtigt die Fälle.
fairer Punkt. Ich denke, was ich sagte, ist wahr, wenn Sie einen naiven "oben beginnen und befolgen Sie alle Referenzen" - Ansatz, aber ist nicht unbedingt wahr.

InformationsquelleAutor nw. | 2010-02-05

c#recursion

31

Wenn die Schlaufen können verallgemeinert werden (Sie können eine beliebige Anzahl von Elementen, die Schleife), können Sie verfolgen von Objekten, die Sie bereits gesehen haben in einem HashSet und stoppen, wenn das Objekt bereits in der festgelegt wird, wenn Sie es besuchen. Oder fügen Sie ein flag, um die Objekte, die Sie festlegen, wenn Sie es besuchen (aber Sie haben dann, um zurück zu gehen & unset all die Fahnen, wenn Sie fertig sind, und der graph kann nur überwunden werden durch einen einzigen thread zu einem Zeitpunkt).

Alternativ, wenn die Schlaufen nur zurück an die Eltern, behalten Sie einen Verweis auf die Eltern und nicht die Schleife auf Eigenschaften beziehen, um es zurück.

Einfachheit halber, wenn Sie wissen, die parent-Referenz einen bestimmten Namen, Sie konnte einfach nicht loop-auf dieser Eigenschaft 🙂
- Meine Letzte Lösung war der pass eine "Eltern" - Referenz mit jedem rekursiven Aufruf, dann zu überspringen-Eigenschaft verweisen auf die Eltern. Funktioniert Super!
- was ist, wenn Sie Knoten A mit Kind B, node B, Kind C und Knoten C mit dem Kind Ein? Übergeben Sie einfach die parent-Referenz funktioniert nicht immer.
- Lippert: Guter Punkt. In meinem Fall, die Grafik ist mehr oder weniger hierarchische, also die einfachere Lösung ausreichen.
InformationsquelleAutor thecoop
32

Was für ein Zufall; das ist das Thema von mein blog kommenden Montag. Sehen Sie für weitere details. Bis dann, hier ist etwas code, um Ihnen eine Idee geben, wie dies zu tun:
```
static IEnumerable<T> Traversal<T>(
    T item,
    Func<T, IEnumerable<T>> children)
{
    var seen = new HashSet<T>();
    var stack = new Stack<T>();
    seen.Add(item);
    stack.Push(item); 
    yield return item;
    while(stack.Count > 0)
    {
        T current = stack.Pop();
        foreach(T newItem in children(current))
        {
            if (!seen.Contains(newItem))
            {
                seen.Add(newItem);
                stack.Push(newItem);
                yield return newItem;
            }
        }
    } 
}
```
Die Methode benötigt zwei Dinge: einen Gegenstand, und eine relation, die die Menge, die alles ist, neben der Sache. Es erzeugt eine Tiefe-ersten traversal des transitive und reflexive Schließung des angrenzens Bezug auf das Element. Lassen Sie die Anzahl der Elemente in der Grafik werden n und die maximale Tiefe werden 1 <= d <= n, vorausgesetzt, dass die branching-Faktor ist nicht begrenzt. Dieser Algorithmus verwendet eine explizite stack statt Rekursion, weil (1) Rekursion in diesem Fall stellt sich, was sollte ein O(n) Algorithmus in O(nd), die dann irgendwas zwischen O(n) und O(n^2), und (2) zu hohe Rekursion kann Schlag den Stapel, wenn die d ist mehr als ein paar hundert Knoten.

Beachten Sie, dass die peak-Speicherverbrauch dieses Algorithmus ist natürlich O(n + d) = O(n).

So, zum Beispiel:
```
foreach(Node node in Traversal(myGraph.Root, n => n.Children))
  Console.WriteLine(node.Name);
```
Sinn?
- Aus Interesse, was ist die Allgemeine Grenze für die Anzahl der stack-frames, die Sie haben können, bevor eine StackOverflowException geworfen wird?
- Sie erhalten standardmäßig eine million bytes des Stacks pro thread. Wie viele bytes eine bestimmte Aktivierung braucht, hängt von details wie "wie groß ist eine Referenz?" (64-bit auf 64-bit-Rechner, 32 bit auf 32-bit-Maschinen...), so ist es schwer eine genaue Aussage zu den Grenzen. Ich würde mich nicht wohl mit eine Rekursion mehr als ein paar hundert tief.
InformationsquelleAutor Eric Lippert
3

Wenn Sie ein graph-traversal, können Sie eine "besucht" - flag auf jedem Knoten. Dies stellt sicher, dass Sie nicht erneut Knoten und möglicherweise stecken in einer unendlichen Schleife. Ich glaube, dies ist der standard-Art und Weise der Durchführung einer graph-traversal.
- Es sei denn, die Grafik wird von vielen geteilt-thread. In diesem Fall müssen Sie, um die Informationen irgendwo in den aktuellen thread.
- In der Tat ist es schlimmer als @Victor ' s Szenario. Angenommen, Sie möchten eine Abfrage auf das kartesische Produkt der Graphen durch sich selbst. Die naive Art und Weise zu tun, ist zum Durchlaufen des Graphen, und dann für jedes element in der "traversal", " start-up ein frisches traversal. Nun müssen Sie in der Lage sein, die zum Durchlaufen des Graphen zweimal an der gleichen Zeit im selben thread. Einstellung ein flag ist ein standard-Weg, dies zu tun, ja, aber es ist auch eine schlechte Idee. Traversierung eines Graphen sollte nicht mutieren, es.
- Das sind spezielle Fälle. Ich habe gerade eine Allgemeine Lösung, die funktionieren sollte, für den häufigsten Fall: ein thread Traversierung eines Graphen einmal. Kompliziertere Situationen erfordern andere Lösungen.
- Ich beachten Sie auch, dass diese Lösung verbraucht O(n) zusätzlichen Speicher, der überlebt die Lebensdauer des Graphen, in der Erwägung, dass Lösungen, die die Verwendung von externen Speicher O(n) zusätzlichen Speicher, der freigegeben wird, nachdem der Traversierung.
InformationsquelleAutor Vivin Paliath
3

Dies ist ein häufiges problem, aber der beste Ansatz hängt vom Szenario ab. Ein zusätzliches problem ist, dass in vielen Fällen nicht ein problem Besuch das gleiche Objekt zweimal - das bedeutet nicht, Rekursion - zum Beispiel, betrachten Sie den Baum:
```
A
=> B
   => C
=> D
   => C
```
Dies kann gültig sein (denke XmlSerializer, das würde einfach schreiben, das C Beispiel zweimal), so ist es oft notwendig, um push/pop-Objekte auf einen Stapel zu prüfen, für echte Rekursion. Das Letzte mal, das ich umgesetzt habe "Besucher", ich hielt eine "Tiefe" entgegen, und nur aktiviert werden, der stack-überprüfung ab einem bestimmten Grenzwert, das bedeutet, dass die meisten Bäume einfach am Ende dabei einige ++/--, mehr aber auch nicht teuer. Sie können sehen, der Ansatz, den ich nahm hier.
- ach. der link ist nun tot.
- auch in diesem Beispiel-Baum ist nicht rekursiv
- es nicht behauptet werden; es ist darauf hinzuweisen, dass das tracking besuchter Knoten nicht notwendigerweise Rekursion (wenn überarbeitet)
InformationsquelleAutor Marc Gravell
2

Ich bin mir nicht genau sicher, was Sie hier zu tun versuchen, aber Sie könnten nur erhalten eine hashtable mit allen bisher besuchten Knoten, wenn Sie tun Sie Ihre Breite-zuerst-Suche von depth-first-Suche.

InformationsquelleAutor rui
0

Veröffentlichte ich einen Beitrag, der im detail erklärt mit Beispielen, wie zu tun, Objekt-traversal durch rekursive Reflexion und auch erkennen und vermeiden rekursive Verweise zu verhindern, dass ein stack over flow Ausnahme: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/

In diesem Beispiel habe ich eine depth-first-traversal mit der rekursiven Reflexion und beibehalten ich ein HashSet von besuchten Knoten für Referenz-Typen. Eine Sache, vorsichtig zu sein, ist die Initialisierung Ihrer HashSet mit Ihrem benutzerdefinierten Gleichheit comparer welche mit der Objekt-Referenz für die hash-Berechnung, die im Grunde die GetHashCode () - Methode implementiert, indem das Basis-Objekt-Klasse selbst, und nicht eine überladene Versionen von GetHashCode (), weil wenn die Typen von Eigenschaften, die Sie durchqueren, überlast GetHashCode-Methode, können Sie erkennen, false, hash-Kollisionen und denke, dass Sie erkannt, dass eine rekursive Referenz, die in der Realität könnte sein, dass die überladene version von GetHashCode produzieren die gleichen hash-Wert über einige Heuristiken und verwirrend die HashSet, alles, was Sie brauchen, um festzustellen, ist zu prüfen, ob es irgendwelche Eltern-Kind-irgendwo in der Baumansicht zeigen auf den gleichen Speicherort im Arbeitsspeicher.

InformationsquelleAutor Dogu Arslan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.