Handling Cycles in Family Tree Graphs in C++ and Qt

By the end of this page, you will understand why family trees should be treated as graphs rather than simple trees, how cycles can appear in ancestry data, and how to redesign validation logic so your C++/Qt code remains correct without relying on invalid assumptions like “this structure can never loop.”

A family tree is often not a true tree in the computer science sense.

A tree has strict rules:

• One path between any two nodes
• No cycles
• Each node usually has exactly one parent in the structure being modeled

But real family relationships do not always fit that model. In genealogy software, the data is better represented as a graph:

• A person is a node
• A parent-child relationship is a directed edge
• A person can have multiple connections
• Different paths may lead to the same ancestor or descendant

In unusual but valid real-world cases, a person may be related to another person in more than one way. That means assumptions such as:

• "A father cannot also be a grandfather"
• "Following parent links will never revisit someone"
• "There is only one ancestry path between two people"

are not safe.

What matters is separating valid data rules from invalid structural assumptions.

For example, these may still be valid checks:

• A person should not be their own biological parent
• A parent-child link should connect two distinct people
• Required fields should exist before saving

But these are not universally valid:

• A person must have only one relationship path to another person
• The ancestry graph must be cycle-free in the broader kinship sense
• Someone cannot hold multiple kinship roles relative to the same individual

In real programming, this matters because many domains look tree-like at first but are actually graphs:

• Organizational hierarchies with cross-links
• Package dependency graphs
• Social networks
• Workflow systems
• Genealogy systems

If you model a graph as a tree, traversal, validation, and UI logic will eventually break.

Think of a real tree in nature versus a road map.

A tree data structure is like a perfect branching plant:

• one trunk
• branches split cleanly
• no branch loops back into another branch

A family relationship graph is more like a road map:

• many routes can connect the same places
• some places are reachable by more than one path
• you must keep track of where you have already been during navigation

If your code assumes it is walking a perfect plant, but the data behaves like a road network, then pathfinding logic, role calculations, and assertions will fail.

So the key mindset is:

• Store people and relationships as a graph
• Traverse with visited tracking
• Validate impossible links, not simplistic relationship labels

Basic graph model in C++

A simple way to model this is to store people and directed parent-child relationships.

#include <QString>
#include <QVector>
#include <QSet>

struct Person {
    int id;
    QString name;
    QVector<Person*> parents;
    QVector<Person*> children;
};

This model does not assume the data is a tree. It only stores relationships.

Example: checking whether one person is an ancestor of another

bool isAncestor(Person* possibleAncestor, Person* person, QSet<int>& visited) {
    if (!person || visited.contains(person->id)) {
        return false;
    }

    visited.insert(person->id);

    for (Person* parent : person->parents) {
        if (parent == possibleAncestor) {
            return true;
        }
        if (isAncestor(possibleAncestor, parent, visited)) {
            return true;
        }
    }

    return false;
}

Usage:

QSet<int> visited;
bool result = isAncestor(alice, bob, visited);

Why this works

• It follows parent links recursively.
• It uses visited to avoid processing the same person repeatedly.
• It does not assume that there is only one path.
• It works even when multiple relationship paths exist.

Example: safe validation rule

Instead of asserting that someone cannot be both father and grandfather, validate only truly invalid direct links:

bool isValidParentLink(Person* parent, Person* child) {
    if (!parent || !child) {
        return false;
    }

    if (parent == child) {
        return false;
    }

    return true;
}

This is safer because it checks the direct data rule rather than making a broader assumption about all possible kinship paths.

Trace example

Consider this simplified example:

bool isAncestor(Person* possibleAncestor, Person* person, QSet<int>& visited) {
    if (!person || visited.contains(person->id)) {
        return false;
    }

    visited.insert(person->id);

    for (Person* parent : person->parents) {
        if (parent == possibleAncestor) {
            return true;
        }
        if (isAncestor(possibleAncestor, parent, visited)) {
            return true;
        }
    }

    return false;
}

Suppose:

• A is a parent of B
• B is a parent of C
• A is also reachable through another path because of overlapping family relationships

Now call:

QSet<int> visited;
isAncestor(A, C, visited);

Execution flow

1. Start with person = C
2. C is not null and not visited
3. Add C to visited
4. Loop through C.parents
5. Suppose one parent is B
6. B != A, so recurse: isAncestor(A, B, visited)
7. B is not visited, so add B
8. Loop through B.parents
9. Suppose one parent is A
10. A == possibleAncestor, so return true
11. That true propagates back up the call stack

Why visited matters

If another path leads back to a person already explored, the visited set stops repeated traversal. Without it, graph traversal code can:

• recurse forever
• repeat work unnecessarily
• trigger false assertions after revisiting the same nodes

Genealogy software

This is the direct use case. Family data may include:

• multiple marriages
• adoption
• shared ancestors
• endogamy
• unusual but real biological relationships

Relationship calculators

If your software computes labels like:

• father
• cousin
• grandparent
• great-grandparent

then it must allow multiple valid labels for the same pair of people.

Data import tools

GEDCOM or other imported genealogy data may contain repeated links, merged people, or unexpected relationship structures. Import code should validate carefully without assuming perfect tree shape.

Graph visualization

A UI that draws family relationships needs graph-aware layout logic. Tree-only rendering may duplicate nodes incorrectly or break when one person appears through multiple paths.

Rule engines and reports

Reports like “show all ancestors” or “detect close biological relationships” must use graph traversal with cycle protection.

In real projects, developers usually solve this by changing both data modeling and validation strategy.

Common patterns

1. Model relationships explicitly

Instead of embedding assumptions in traversal code, store relationships directly:

• parent of
• child of
• spouse of
• adoptive parent of

This makes the domain clearer and avoids overloading a tree structure.

2. Use guard clauses

if (!parent || !child) return false;
if (parent == child) return false;

Guard clauses keep low-level validation simple and local.

3. Separate direct constraints from derived facts

Direct constraint:

• a person cannot be linked as their own parent

Derived fact:

• someone may be both father and grandfather through different paths

Only direct constraints should usually become hard assertions.

4. Track visited nodes in traversals

For DFS or BFS over family relationships, always track visited nodes.

QSet<int> visited;

This protects reporting, searching, and relationship detection.

5. Return relationship sets, not single labels

A real codebase may compute all valid relationships between two people instead of just one.

For example:

• {"father", "grandfather"}
• {"cousin", "brother-in-law"}

This avoids bugs caused by assuming there is exactly one role.

6. Reserve assertions for programmer errors

Assertions are best for conditions that should never happen due to a coding bug, such as:

• null pointer after guaranteed initialization
• invalid enum state
• corrupted internal container assumptions

They are less appropriate for rejecting rare but valid real-world data.

1. Treating genealogy as a strict tree

Broken assumption:

Q_ASSERT(person->parents.size() <= 1);

Why it is wrong:

• biological and legal relationships can create more complex structures
• even when parent count is limited, ancestry paths are still not tree-shaped globally

2. Asserting role exclusivity

Broken example:

Q_ASSERT(!(isFather(x, y) && isGrandfather(x, y)));

Why it is wrong:

• one person can be related through multiple paths
• role labels are derived facts, not exclusive categories

Better approach:

• allow multiple relationship results
• only reject impossible direct links

3. Recursive traversal without visited tracking

Broken example:

bool hasAncestor(Person* target, Person* person) {
    for (Person* parent : person->parents) {
        if (parent == target || hasAncestor(target, parent)) {
            return true;
        }
    }
    return false;
}

Problem:

• repeated paths can revisit the same node
• deep graphs can cause excessive recursion or infinite loops if invalid self-links exist

4. Mixing validation with interpretation

Do not confuse:

• “This link is invalid”
• “This derived relationship feels unusual”

Software should reject structurally invalid records, not surprising but valid family situations.

5. Hardcoding one-path logic

If your code stops after finding the first path, it may miss additional valid relationships.

Avoid this when generating reports or labels.

Assertions vs validation

Quick reference

• Family data is usually a graph, not a strict tree.
• Person = node
• Parent-child relationship = directed edge
• Multiple paths between two people may be valid.
• A person can have multiple kinship roles relative to another person.

Safe rules to validate

parent != nullptr
child != nullptr
parent != child

Safe traversal pattern

bool walk(Person* p, QSet<int>& visited) {
    if (!p || visited.contains(p->id)) return false;
    visited.insert(p->id);
    // continue traversal
    return true;
}

Avoid these assumptions

• "This structure is always a tree"
• "There is only one path between two people"
• "A person cannot hold multiple relationship roles"

Prefer

• graph-based modeling
• visited sets for DFS/BFS
• direct-link validation
• derived relationship calculation as a separate step

Why is a family tree not always a real tree in programming?

Because a programming tree requires one unique path and no cycles, while genealogy data can have multiple valid paths between the same people.

Should I remove all assertions from my family tree software?

No. Keep assertions for internal programming errors, but replace invalid domain assumptions with proper validation rules.

Can one person really be both a father and a grandfather of the same person?

Yes. In unusual cases, multiple relationship paths can make more than one kinship label valid at the same time.

What data should I validate strictly?

Validate direct impossible links, such as null references, self-parent links, and malformed relationship records.

How do I prevent traversal bugs in a family graph?

Use graph traversal algorithms with a visited set or similar mechanism to avoid revisiting the same nodes repeatedly.

Should I store relationship names like grandfather directly?

Usually no. Store basic relationships like parent-child, then derive labels such as grandfather from graph traversal when needed.

• Graphs — Family relationships are better modeled as graphs than trees.
• Trees — Useful as a contrast, because many bugs come from assuming genealogy is a tree.
• Depth-first search (DFS) — Common for exploring ancestry and descendant relationships.
• Breadth-first search (BFS) — Useful for shortest relationship path calculations.
• Recursion — Often used to walk parent or child links.
• Data validation — Important for separating invalid records from valid but unusual cases.
• Assertions — Helps distinguish programmer errors from user data edge cases.
• Graph cycles — Relevant when reasoning about repeated paths and safe traversal.