Rileva i cicli in un grafico genealogico durante una ricerca approfondita

Question

Sto caricando i dati genealogici del cavallo in modo ricorsivo. Per alcuni set di dati errati la mia ricorsione non si ferma mai ... e questo perché ci sono cicli nei dati.

Come posso rilevare quei cicli per interrompere ricorrenti?

Ho pensato di ricorrere mantenendo un hashTable con tutti i cavalli "visitati". Ma troveranno alcuni falsi positivi, perché un cavallo può essere due volte su un albero.

Ciò che non può accadere è che un cavallo appaia come padre o nonno o bisnonno di STESSO.

Answer 1

pseudo codice:

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen) 
{ 
    if(seen.Contains(currentNode)) return; 
    // Or, do whatever needs to be done when a cycle is detected 

    ProcessHorse(currentNode.Horse); // Or whatever processing you need 

    seen.Push(currentNode); 

    foreach(GenTreeNode childNode in currentNode.Nodes) 
    { 
     ProcessTree(childNode, seen); 
    } 

    seen.Pop(); 
} 

L'idea di base è quella di mantenere un elenco di tutti i nodi che abbiamo già visto sul nostro percorso verso il nodo corrente; se tornassi a un nodo che avevamo già attraversato, allora sai che abbiamo formato un ciclo (e dovremmo ignorare il valore o fare tutto ciò che deve essere fatto)

Answer 2

Conservare una pila di tutti gli elementi che portano alla radice dell'albero.

Ogni volta che si avanza lungo la struttura, eseguire la scansione della pila per l'elemento figlio. Se trovi una corrispondenza, hai scoperto un ciclo e dovresti saltare quel bambino. Altrimenti, spingi il bambino in pila e procedi. Ogni volta che fai il backtrack dell'albero, fai scoppiare un elemento fuori dalla pila e scartalo.

(Nel caso di dati genealogici, un nodo "figlio" nell'albero è presumibilmente il genitore biologico del nodo "padre".)

Answer 3

Un modo molto semplice per rilevare questo, è controllando che vincolo stesso:

Ciò che non può accadere è che un cavallo appare come padre o nonno o bisnonno di STESSO.

Ogni volta che si inserisce un nodo nell'albero, attraversare l'albero fino alla radice per assicurarsi che il cavallo non esista come un qualsiasi tipo di genitore.

Per accelerare, è possibile associare una tabella hash a ciascun nodo, in cui si memorizza nella cache la risposta di tale ricerca. Quindi non dovrai cercare l'intero percorso la volta successiva che inserisci un cavallo sotto quel nodo.

Answer 4

La tua soluzione di hash table dovrebbe funzionare se tieni traccia dei nodi invece dei cavalli. Assicurati solo che ogni volta che leggi un nuovo cavallo, crei un nuovo nodo anche se il valore/cavallo è uguale al valore/cavallo del nodo precedente.

Answer 5

Hai a che fare con un directed acyclic graph, non un albero. Non dovrebbero esserci cicli, poiché il discendente di un cavallo non può essere anche il suo antenato.

Conoscendo questo, è necessario applicare tecniche di codice specifiche per i grafici aciclici diretti.

Answer 6

Questo suona come un caso in cui è finalmente possibile applicare quella domanda di domande trivia: trovare un ciclo in una lista collegata utilizzando solo memoria O (1).

In questo caso la "lista collegata" è la sequenza di elementi che enumeri.Usa due enumeratori, eseguine uno a metà velocità e se il più veloce si imbatte in quello lento, allora hai un ciclo. Questo sarà anche il tempo O (n) invece del tempo O (n^2) richiesto per controllare un elenco 'visto'. Lo svantaggio è che si scopre solo il loop dopo che alcuni nodi sono stati elaborati più volte.

Nell'esempio, ho sostituito il metodo "mezza velocità" con il metodo "drop marker" più semplice da scrivere.

class GenTreeNode { 
    ... 

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary> 
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) { 
     long cur_track_count = 0; 
     long high_track_count = 1; 
     T post = default(T); 
     foreach (var e in sub_enumerable) { 
      yield return e; 
      if (++cur_track_count >= high_track_count) { 
       post = e; 
       high_track_count *= 2; 
       cur_track_count = 0; 
      } else if (object.ReferenceEquals(e, post)) { 
       throw new Exception("Infinite Loop"); 
      } 
     } 
    } 

    ... 

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary> 
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() { 
     yield return this; 
     foreach (var child in this.nodes) 
      foreach (var e in child.tree_nodes_unchecked()) 
       yield return e; 
    } 
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary> 
    public IEnumerable<GenTreeNode> tree_nodes() 
    { 
     return CheckedEnumerable(tree_nodes_unchecked()); 
    } 

    ... 

    void ProcessTree() { 
     foreach (var node in tree_nodes()) 
      proceess(node); 
    } 
}