Detectar ciclos em um gráfico genealógico durante uma pesquisa em profundidade

Question

Estou carregando dados genealógicos de cavalos de forma recursiva.Para alguns conjuntos de dados errados, minha recursão nunca para...e isso ocorre porque existem ciclos nos dados.

Como posso detectar esses ciclos para parar de se repetir?

Pensei em manter recorrentemente uma hashTable com todos os cavalos "visitados".Mas isso encontrará alguns falsos positivos, porque um cavalo PODE estar duas vezes em uma árvore.

O que não pode acontecer é que um cavalo apareça como pai ou avô ou bisavô dele mesmo.

Answer 1

Pseudo-código:

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

A idéia básica é manter uma lista de todos os nós que já vimos em nosso caminho para o nó atual; Se estava voltando a um nó pelo qual já passamos, você sabe que formamos um ciclo (e devemos pular o valor ou fazer o que precisa ser feito)

Answer 2

Mantenha uma pilha de todos os elementos que levam à raiz da árvore.

Toda vez que você avançar na árvore, procure a pilha para o elemento filho. Se você encontrar uma combinação, descobriu um loop e deve pular essa criança. Caso contrário, empurre a criança para a pilha e prossiga. Sempre que você voltará a subir a árvore, tire um elemento da pilha e descarte.

(No caso de dados genealógicos, um nó "filho" na árvore é presumivelmente o pai biológico do nó "pai".)

Answer 3

Este parece ser um caso em que você pode finalmente aplicar aquela pergunta trivial da entrevista:encontre um ciclo em uma lista vinculada usando apenas memória O(1).

Nesse caso, sua “lista vinculada” é a sequência de elementos que você enumera.Use dois enumeradores, execute um na metade da velocidade e, se o mais rápido esbarrar no mais lento, você terá um loop.Este também será o tempo O(n) em vez do tempo O(n^2) necessário para verificar uma lista 'vista'.A desvantagem é que você só descobre o loop depois que alguns nós foram processados ​​várias vezes.

No exemplo, substituí o método 'metade da velocidade' pelo método 'descartar marcadores', mais simples de escrever.

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

Uma maneira muito simples de detectar isso é verificando essa restrição:

O que não pode acontecer é que um cavalo aparece como pai, avô ou bisavô de si mesmo.

Sempre que você inserir um nó em sua árvore, atravesse a árvore na raiz para garantir que o cavalo não exista como nenhum tipo de pai.

Para acelerar isso, você pode associar uma hashtable a cada nó, onde você armazena em cache a resposta dessa pesquisa. Então você não precisa pesquisar o caminho inteiro na próxima vez que inserir um cavalo sob esse nó.

Answer 5

Sua solução de tabela de hash deve funcionar se você acompanhar os nós em vez de cavalos. Apenas certifique -se de que toda vez que você lê um novo cavalo, cria um novo nó, mesmo que o valor/cavalo seja o mesmo que o valor/cavalo de um nó anterior.

Answer 6

Você está lidando com um Gráfico acíclico direcionado, não uma árvore. Não deve haver ciclos, pois o descendente de um cavalo também não pode ser seu ancestral.

Sabendo disso, você deve aplicar técnicas de código específicas aos gráficos aciclicos direcionados.