Cycles in Genealogy Software: How It Works Under the Hood in C++

Introduction: Why There Are No Time Loops in a Pedigree

Imagine: you are writing a program for building a family tree. Everything goes perfectly until a user adds a relationship: "Ivan is Peter's father, Peter is Ivan's father." The program freezes, recursion goes infinite, and the user gets a literal Stack Overflow. Sound familiar? This question is one of the most popular on Stack Overflow (thousands of views), and for good reason.

In this article, we will break down how cycles in a family tree work under the hood. I will show you how to detect and handle such situations in C++, so your family tree software doesn't crash but runs like clockwork. You will learn not only graph theory but also get ready-to-use code that you can immediately adapt for your project.

\n

Important: The article is written for the educational site pythonlib.ru, but the code is entirely in C++ — a great example of how algorithms cross language boundaries.

\n

Why Are Cycles a Problem for Genealogy Software?

A family tree is a directed graph. Each node is a person, each edge is a relationship (parent → child). In real life, cycles cannot exist: no one can be their own ancestor. But in a program, a user might accidentally create such a link:

\n
• Alice is Bob's mother
\n
• Bob is Alice's father
\n

If your traversal algorithm (e.g., for displaying all ancestors) does not check for cycles, it will endlessly iterate over Alice → Bob → Alice → Bob... This leads to:

\n
• Program freezing
\n
• Stack overflow
\n
• Infinite memory consumption
\n

Therefore, cycle detection in a graph is a fundamental task for any serious genealogy application.

Data Structure: How to Store a Family Tree in C++

Before discussing algorithms, we need to decide on a representation. I suggest using an adjacency list — it is efficient and intuitive.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // Each person is a node with a unique name (ID)\n    // Edges: parent -> child\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        // If the child is not yet in the graph, add an empty list\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... methods for traversal\n};\n

Here, each key is a person's name, and the value is a list of their children. This is a minimal but functional data structure for a family tree. Now let's move to the main part.

How to Detect a Cycle: Depth-First Search (DFS) Algorithm

The standard way to find a cycle in a directed graph is a modified Depth-First Search (DFS). The idea is simple: we mark vertices with three colors:

\n
• White (0) — not visited
\n
• Gray (1) — in the process of traversal (in the current recursion stack)
\n
• Black (2) — fully processed
\n

If during DFS we encounter a vertex with a gray color — that is a cycle. Let's implement this in 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