C#: Evitar recurrencia infinita cuando se atraviesa el gráfico de objetos

Question

Tengo un gráfico de objetos en el que cada objeto secundario contiene una propiedad que hace referencia a su elemento primario. ¿Hay alguna buena estrategia para ignorar las referencias principales a fin de evitar la recursión infinita? He considerado agregar un atributo especial [Parent] a estas propiedades o usar una convención de nomenclatura especial, pero tal vez haya una mejor manera.

Answer 1

Si los bucles se pueden generalizar (puede tener cualquier número de elementos que componen el bucle), puede realizar un seguimiento de los objetos que ya ha visto en un HashSet y detener si el objeto ya está en el conjunto cuando visitarla. O agregue una bandera a los objetos que establece cuando la visita (pero luego tiene que volver atrás & desarmar todas las banderas cuando haya terminado, y el gráfico solo puede atravesarse con un solo hilo a la vez).

Alternativamente, si los bucles solo volverán al elemento principal, puede mantener una referencia al elemento principal y no repetir las propiedades que hacen referencia a él.

Para simplificar, si conoce la referencia de los padres tendrá un cierto nombre, usted podría no han de enlazarse en esa propiedad :)

Answer 2

Si estás haciendo un recorrido gráfico, puede tener un "visitada" bandera en cada nodo. Esto garantiza que no vuelva a visitar un nodo y posiblemente se quede atascado en un bucle infinito. Creo que esta es la forma estándar de realizar un cruce de gráficos.

Answer 3

No estoy exactamente seguro de lo que estás tratando de hacer aquí, pero podrías mantener una tabla hash con todos los nodos previamente visitados cuando estés haciendo tu primera búsqueda de profundidad de la primera búsqueda.

Answer 4

Qué casualidad; este es el tema de my blog este próximo lunes. Véalo para más detalles. Hasta entonces, aquí hay un código para darle una idea de cómo hacer esto:

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

El método tiene dos cosas: un elemento y una relación que produce el conjunto de todo lo que está al lado del elemento. Produce un recorrido en profundidad de del cierre transitivo y reflexivo de la relación de adyacencia en el artículo. Deje que el número de elementos en el gráfico sea n, y la profundidad máxima sea 1 < = d < = n, suponiendo que el factor de bifurcación no está limitado. Este algoritmo usa una pila explícita en lugar de recursión porque (1) la recursividad convierte en este caso lo que debería ser un algoritmo O (n) en O (nd), que es algo entre O (n) y O (n^2). y (2) recursión excesiva puede explotar la pila si la d es más que algunos cientos de nodos.

Tenga en cuenta que el uso máximo de la memoria de este algoritmo es, por supuesto, O (n + d) = O (n).

Así, por ejemplo:

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

sentido?

Answer 5

Este es un problema común, pero el mejor enfoque depende del escenario. Un problema adicional es que en muchos casos no es un problema visitar el mismo objeto dos veces - que no implica la recursividad - por ejemplo, considere el árbol:

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

Esto puede ser válido (piensa XmlSerializer , lo que simplemente escribiría la instancia C dos veces), por lo que a menudo es necesario insertar objetos en una pila para verificar la verdadera recursión.La última vez que implementé un "visitante", mantuve un contador de "profundidad", y solo habilité la verificación de la pila más allá de un cierto umbral - eso significa que árboles más simplemente terminan haciendo algo de ++/--, pero nada más caro. Puedes ver el enfoque que tomé here.

Answer 6

I publicó un post explicando en detalle con ejemplos de código de cómo hacer traversal objeto por reflexión recursiva y también detectar y evitar referencias recursivas para prevenir una pila sobre excepción flujo: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/

En ese ejemplo hice una profundidad primero recorrido transversal usando reflexión recursiva y mantuve un HashSet de nodos visitados para tipos de referencia. Una cosa a tener en cuenta es inicializar su HashSet con su comparador de igualdad personalizado que utiliza la referencia de objeto para el cálculo de hash, básicamente el método GetHashCode() implementado por la clase de objeto base en sí y no cualquier versión sobrecargada de GetHashCode() porque si los tipos de propiedades atraviesa el método GetHashCode sobrecarga, puede detectar falsas colisiones hash y cree que ha detectado una referencia recursiva que en realidad podría ser que la versión sobrecargada de GetHashCode produzca el mismo valor hash a través de algunas heurísticas y confunda el HashSet, todo lo que necesita detectar es comprobar si hay algún hijo principal en cualquier parte del árbol de objetos que apunta a la misma ubicación en la memoria.