¿Cuál sería un buen algoritmo para una verificación circular de referencia en este caso?

Question

Dado que tiene la siguiente clase (malo C#, pero usted consigue la deriva):

public abstract class AmICircular 
{ 
    // assume Children is never null 
    private List<AmICircular> Children {get;set;} 

    // assume target is never null 
    public void Add(AmICircular target) 
    { 
    target.PerformCircularReferenceCheck(this); 
    Children.Add(target); 
    } 

    // throws when a circular reference is detected 
    protected abstract void PerformCircularReferenceCheck(AmICircular target); 
} 

¿Cómo poner en práctica PerformCircularReferenceCheck? Y, no, esto no es tarea.

La aplicación ingenua, imo, sería hacer una verificación de referencia sobre this y todos los niños, a continuación, llamar PerformCircularReferenceCheck en target, pasando this. Pero me pregunto si hay formas mejores y comprobadas para hacerlo, como agregar un método para contraer todo el árbol de referencias de Children para this y target y luego examinar los resultados (¿hay menos presión en la pila?), O quizás evite el cheque por completo mediante el uso de una colección diferente (¡tal vez autocomprobación!) que no sea la Lista < T>?

¿Cómo harías esto?

edit: Como Stefan señaló, sólo es necesario para determinar si este es alcanzable por el objetivo

Answer 1

En el caso donde nunca agrega objetos de autorreferencia (a ser definidos más adelante), su estructura de datos describe un gráfico acíclico dirigido (http://en.wikipedia.org/wiki/Directed_acyclic_graph), donde cada instancia de la clase IAmCircular describe un nodo con un conjunto de nodos sucesores directos = niños.

Asumiendo la condición previa de que hasta el momento, no se ha creado un ciclo, la función que desea, PerformCircularReferenceCheck, solo necesita comprobar si "this" es alcanzable desde "target". Si es así, debería devolver una excepción.

En cuanto a la teoría de la complejidad, este problema es la conectividad ST (http://en.wikipedia.org/wiki/St-connectivity) y se completa para la clase NL (http://en.wikipedia.org/wiki/NL_(complexity)), incluso cuando restringe la entrada a gráficos acíclicos (que es su caso).

En particular, el teorema de Savitch (http://en.wikipedia.org/wiki/Savitch%27s_theorem) proporciona una forma constructiva de crear un algoritmo de espacio O (log^2 n) (que se ejecuta en el tiempo O (n^2)), donde n es el número de nodos.

Además, al ser NL-completo, es poco probable que exista un algoritmo que se ejecute en el espacio O (log n) (es decir, use un número constante de punteros a nodos), ya que eso implicaría la improbable NL = L EDITAR: en particular, las pequeñas variaciones del algoritmo de liebre y tortuga sugeridas por alguien no funcionarían (porque usarían muy poco espacio).

Recomendaría implementar el algoritmo trivial O (n) time, O (n) space, que genera para "objetivo" su conjunto de sucesores (recursivamente) y verificar si "this" aparece en este conjunto.

Tenga cuidado, la construcción explícita del conjunto es importante. De lo contrario, si solo verifica recursivamente si "cualquier persona que suceda" puede alcanzar "esto", corre el riesgo de correr en tiempo exponencial.

He recomendado el algoritmo de O (n) tiempo/O (n) espacio porque es asintóticamente el mejor que puede hacer en cuanto al tiempo, y ya está utilizando O (n) espacio para su estructura de datos.

Answer 2

La solución iterativa es definir un conjunto R (accesible) y CR (hijos de Acesible).

Usted comienza con R = {this} y CR = {this.children}.

En cada paso, verifica si CR contiene this (o target, dependiendo de su objetivo). De lo contrario, agregue CR a R y establezca CR para los hijos de CR, y elimine los elementos de R de CR.

Si CR se vacía, R es el conjunto completo de elementos alcanzables desde this.