C#: unikaj nieskończonej rekurencji podczas przechodzenia wykresu obiektów

Co za zbieg okoliczności; to jest temat mojego bloga w najbliższy poniedziałek. Zobacz go po więcej szczegółów. Do tego czasu, oto kod, który da ci pomysł, jak to zrobić:

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

Metoda przyjmuje dwie rzeczy: element i relację, która tworzy zbiór wszystkiego, co przylega do elementu. Tworzy ona Depth-first traversal of the transitive and reflexive closure of the adjacency relation on the items . Niech liczba elementów na wykresie będzie n, A maksymalna głębokość wynosi 1

Zauważ, że szczytowe wykorzystanie pamięci tego algorytmu wynosi oczywiście O(n + d) = O (n).

Więc dla przykład:

foreach(Node node in Traversal(myGraph.Root, n => n.Children))
  Console.WriteLine(node.Name);

Ma sens?

Jeśli robisz przemierzanie wykresu, możesz mieć flagę" odwiedzony " na każdym węźle. Zapewnia to, że nie odwiedzisz ponownie węzła i prawdopodobnie utkniesz w nieskończonej pętli. Uważam, że jest to standardowy sposób wykonywania grafu.

Nie jestem do końca pewien, co próbujesz zrobić tutaj, ale możesz po prostu utrzymać hashtable ze wszystkimi wcześniej odwiedzonymi węzłami, gdy robisz swoje szerokość pierwsze wyszukiwanie głębi pierwsze wyszukiwanie.

Jest to częsty problem, ale najlepsze podejście zależy od scenariusza. Dodatkowym problemem jest to, że w wielu przypadkach nie jest to problem dwukrotnego odwiedzenia tego samego obiektu - co nie implikuje rekurencji-na przykład rozważ drzewo:

A
=> B
   => C
=> D
   => C

Może to być poprawne (pomyśl XmlSerializer, które po prostu zapisywałyby instancję C dwa razy), więc często konieczne jest wypychanie / pop obiektów na stosie, aby sprawdzić prawdziwą rekurencję. Ostatnim razem, kiedy wprowadziłem "gościa", zachowałem " głębię" licznik, i tylko włączone sprawdzanie stosu poza określonym progiem-oznacza to, że Większość drzew po prostu kończy się wykonywaniem niektórych ++/--, ale nic droższego. Możesz zobaczyć podejście, które zastosowałem tutaj .

Opublikowałem post wyjaśniający szczegółowo za pomocą przykładów kodu, jak wykonać object traversal przez rekurencyjne odbicie, a także wykrywać i unikać rekurencyjnych odniesień, aby zapobiec wyjątkowi stosu nad przepływem: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/

W tym przykładzie zrobiłem najpierw głębię, używając rekurencyjnego odbicia i utrzymałem HashSet odwiedzanych węzłów dla typów referencyjnych. Należy uważać, aby zainicjować Twój HashSet z niestandardowym porównaniem Równości, który wykorzystuje odniesienie do obiektu do obliczenia hash, w zasadzie metoda GetHashCode () zaimplementowana przez samą klasę obiektu bazowego, a nie przeciążone wersje GetHashCode (), ponieważ jeśli typy właściwości, które przemierzasz, przeciążają metodę GetHashCode, możesz wykryć fałszywe kolizje hash i pomyśleć, że wykryłeś rekurencyjne odniesienie, które w rzeczywistości może być, że przeciążona wersja GetHashCode produkująca tę samą wartość hash przez niektóre heurystyki i mylące HashSet, wszystko, co musisz wykryć, to sprawdzić, czy w dowolnym miejscu w drzewie obiektów znajduje się jakieś dziecko-rodzic wskazujące na to samo miejsce w pamięci.