Cycles dans les logiciels généalogiques : comment ça fonctionne sous le capot en C++

Introduction : pourquoi il n'y a pas de boucles temporelles dans un arbre généalogique

Imaginez : vous écrivez un programme pour construire un arbre généalogique. Tout se passe bien, jusqu'à ce qu'un utilisateur ajoute un lien : « Ivan est le père de Pierre, Pierre est le père d'Ivan ». Le programme se bloque, la récursion part à l'infini, et l'utilisateur obtient un Stack Overflow au sens littéral du terme. Une situation familière ? Cette question est l'une des plus populaires sur Stack Overflow (des milliers de vues), et ce n'est pas pour rien.

Dans cet article, nous allons voir comment fonctionnent les cycles dans un arbre généalogique sous le capot. Je vais vous montrer comment détecter et gérer ces situations en C++, afin que votre family tree software ne plante pas, mais fonctionne comme une horloge. Vous apprendrez non seulement la théorie des graphes, mais vous obtiendrez également un code prêt à l'emploi que vous pourrez adapter immédiatement à votre projet.

\n

Important : Cet article est rédigé pour le site éducatif pythonlib.ru, mais le code est entièrement en C++ — c'est un excellent exemple de la façon dont les algorithmes traversent les frontières des langages.

\n

Pourquoi les cycles sont-ils un problème pour les logiciels généalogiques ?

Un arbre généalogique est un graphe orienté (directed graph). Chaque nœud est une personne, chaque arête est une relation (parent → enfant). Dans la vie réelle, les cycles sont impossibles : personne ne peut être son propre ancêtre. Mais dans un programme, un utilisateur peut accidentellement créer un tel lien :

\n
• Alice est la mère de Bob
\n
• Bob est le père d'Alice
\n

Si votre algorithme de parcours (par exemple, pour afficher tous les ancêtres) ne vérifie pas les cycles, il va parcourir indéfiniment Alice → Bob → Alice → Bob... Cela entraîne :

\n
• Le blocage du programme
\n
• Un débordement de pile (stack overflow)
\n
• Une consommation de mémoire infinie
\n

C'est pourquoi la détection de cycles dans un graphe est une tâche fondamentale pour toute application généalogique sérieuse.

Structure de données : comment stocker un arbre généalogique en C++

Avant de parler d'algorithmes, il faut définir la représentation. Je propose d'utiliser une liste d'adjacence (adjacency list) — c'est efficace et clair.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // Chaque personne est un nœud avec un nom unique (ID)\n    // Arêtes : parent -> enfant\n    std::unordered_map<std::string, std::vector<std::string>> parentToChild;\n    \npublic:\n    void addRelation(const std::string& parent, const std::string& child) {\n        parentToChild[parent].push_back(child);\n        // Si l'enfant n'est pas encore dans le graphe, on ajoute une liste vide\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... méthodes de parcours\n};\n

Ici, chaque clé est le nom d'une personne, la valeur est la liste de ses enfants. C'est une structure de données pour arbre généalogique minimale mais fonctionnelle. Passons maintenant à l'essentiel.

Comment détecter un cycle : algorithme de parcours en profondeur (DFS)

La méthode standard pour trouver un cycle dans un graphe orienté est le parcours en profondeur (DFS) modifié. L'idée est simple : on marque les sommets avec trois couleurs :

\n
• Blanc (0) — non visité
\n
• Gris (1) — en cours de parcours (dans la pile de récursion actuelle)
\n
• Noir (2) — entièrement traité
\n

Si pendant le DFS on rencontre un sommet de couleur grise, c'est un cycle. Implémentons cela en C++.

#include <unordered_map>\n#include <string>\n#include <vector>\n\nenum class Color { WHITE, GRAY, BLACK };\n\nclass CycleDetector {\nprivate:\n    std::unordered_map<std::string, std::vector<std::string>>& graph;\n    std::unordered_map<std::string, Color> color;\n    \n    bool