Détecter des cycles dans un graphe de généalogie lors d'une recherche en profondeur d'abord

Question

Je charge les données généalogiques des chevaux de manière récursive. Pour certains ensembles de données erronés, ma récursivité ne s’arrête jamais ... c’est parce qu’il y a des cycles dans les données.

Comment puis-je détecter que ces cycles cessent de se reproduire?

J'ai pensé, tout en répétant, maintenir une table de hachage avec tous les éléments "visités". les chevaux. Mais il y aura des faux positifs, car un cheval peut être deux fois dans un arbre.

Ce qui ne peut pas arriver, c’est qu’un cheval apparaît en tant que père, grand-père ou arrière grand-père de LUI-MÊME.

Answer 1

Pseudo-code:

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'idée de base est de garder une liste de tous les nœuds que nous avons déjà vus en descendant jusqu'au nœud actuel; si vous revenez à un nœud que nous avons déjà traversé, alors vous savez que nous avons formé un cycle (et nous devrions ignorer la valeur ou faire ce qui doit être fait)

Answer 2

Conservez une pile de tous les éléments conduisant à la racine de l’arbre.

Chaque fois que vous avancez dans l'arborescence, analysez la pile pour rechercher l'élément enfant. Si vous trouvez une correspondance, alors vous avez découvert une boucle et devez ignorer cet enfant. Sinon, poussez l'enfant dans la pile et continuez. Chaque fois que vous revenez en arrière dans l'arborescence, retirez un élément de la pile et supprimez-le.

(Dans le cas de données généalogiques, un nœud "enfant" dans l'arborescence est vraisemblablement le parent biologique du nœud "parent".)

Answer 3

Cela ressemble à un cas où vous pouvez enfin appliquer cette question d’interview: trouvez un cycle dans une liste chaînée en utilisant uniquement la mémoire O (1).

Dans ce cas, votre " liste chaînée " est la séquence d'éléments que vous énumérez. Utilisez deux énumérateurs, lancez-en un à la moitié de la vitesse, et si le plus rapide se heurte au lent, vous avez une boucle. Ce sera également le temps O (n) au lieu du temps O (n ^ 2) requis pour vérifier une liste "visible". L'inconvénient est que vous ne saurez que sur la boucle après que certains des nœuds ont été traités plusieurs fois.

Dans l'exemple, j'ai remplacé la méthode 'half speed' par la méthode 'drop markers' plus simple à écrire.

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 moyen très simple de détecter cela consiste à vérifier la contrainte elle-même:

  

Ce qui ne peut pas arriver, c’est qu’un cheval apparaît comme un père, un grand-père ou un arrière-grand-père de soi-même.

Chaque fois que vous insérez un nœud dans votre arbre, parcourez-le jusqu'à la racine pour vous assurer que le cheval n'existe pas en tant que parent.

Pour accélérer le processus, vous pouvez associer une table de hachage à chaque nœud, dans lequel vous mettez en cache la réponse d'une telle recherche. Dans ce cas, vous n'avez pas à chercher dans tout le chemin lors de la prochaine insertion d'un cheval sous ce noeud.

Answer 5

Votre solution de table de hachage devrait fonctionner si vous gardez une trace des nœuds au lieu des chevaux. Assurez-vous simplement que chaque fois que vous lisez un nouveau cheval, vous créez un nouveau nœud, même si la valeur / le cheval est identique à la valeur / le cheval d'un nœud précédent.

Answer 6

Vous utilisez un graphe acyclique dirigé , et non un arbre. Il ne devrait pas y avoir de cycles, car le descendant d'un cheval ne peut pas être aussi son ancêtre.

Sachant cela, vous devez appliquer les techniques de code spécifiques aux graphes acycliques dirigés.