Rileva i cicli in un grafico genealogico durante una ricerca di profondità

Question

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

Come posso rilevare quei cicli per smettere di ricorrere?

Ho pensato di mantenere una tabella hash ricorrendo a tutte le "visite" " cavalli. Ma questo troverà alcuni falsi positivi, perché un cavallo può essere due volte su un albero.

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

Answer 1

Codice pseudo:

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 scendendo al nodo corrente; se fosse tornato a un nodo che abbiamo già attraversato, allora sai che abbiamo formato un ciclo (e dovremmo saltare il valore o fare tutto ciò che deve essere fatto)

Answer 2

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

Ogni volta che avanzi nella struttura ad albero, scansiona la pila per l'elemento figlio. Se trovi una corrispondenza, allora hai scoperto un ciclo e dovresti saltare quel bambino. Altrimenti, spingere il bambino sulla pila e procedere. Ogni volta che fai un passo indietro sull'albero, fai uscire un elemento dalla pila e scarta.

(Nel caso di dati genealogici, un nodo "figlio" nella struttura è presumibilmente il genitore biologico del nodo "genitore".

Answer 3

Sembra un caso in cui puoi finalmente applicare quella domanda per l'intervista: trova un ciclo in un elenco collegato usando solo la memoria O (1).

In questo caso la tua "lista collegata" è la sequenza di elementi che elenchi. Usa due enumeratori, esegui uno a metà velocità e se quello veloce si imbatte in quello lento, hai un ciclo. Questo sarà anche il tempo O (n) invece del tempo O (n ^ 2) richiesto per controllare un elenco "visto". Il rovescio della medaglia è che scopri il ciclo solo dopo che alcuni dei nodi sono stati elaborati più volte.

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

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

Answer 4

Un modo molto semplice per rilevarlo è controllando quel vincolo stesso:

  

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

Ogni volta che inserisci un nodo nel tuo albero, attraversa l'albero verso la radice per assicurarti che il cavallo non esista come un qualsiasi tipo di genitore.

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

Answer 5

La soluzione della tabella hash dovrebbe funzionare se si tiene traccia dei nodi anziché 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 di un nodo precedente.

Answer 6

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

Sapendo questo, dovresti applicare tecniche di codice specifiche per i grafici aciclici diretti.