家族树软件中的循环问题

技术背景

在家族树软件的开发中，传统认为家族树是树状结构，但实际上它往往是有向无环图（DAG）。这是因为在现实生活中，存在表亲结婚等情况，会使家族树产生循环。同时，GEDCOM 格式在定义家族关系方面存在局限性，不兼容同性关系、乱伦关系等，而这些情况在现实中对于追溯更久远的家族历史可能会出现。

实现步骤

数据结构选择

选择合适的数据结构至关重要，通常图结构比树结构更适合处理家族树中的循环问题。例如使用有向图，可以避免因循环带来的困扰。

循环检测与处理

在加载数据时，采用标记祖先路径的方法检测循环。对于遍历到的个体，标记其到每个祖先的路径。若新路径包含当前路径作为子路径，则为循环，可将该边标记为“弱”边，而非真正断开连接。

显示处理

当遇到循环时，可将循环中的父节点视为“幽灵”节点。例如，当一个人既是另一个人的父亲又是祖父时，祖父节点正常显示，父亲节点则显示为“幽灵”节点，标注“见祖父”并指向祖父节点。

软件功能决策

定义循环为超出范围：决定软件不处理罕见的循环情况。当出现此类情况时，提示用户使用其他产品，并添加良好的导入和导出功能。
允许手动关系：允许用户添加手动关系，软件不检查这些关系，但要避免过度配置导致“软编码”问题。
使数据模型更灵活：采用完整的图结构，允许存在循环，但要广泛测试软件，使用测试数据生成器检查异常测试用例，并找出尽可能多的不变量进行测试。

核心代码

以下是使用Python模拟检测循环和标记边为“弱”边的示例代码：

class FamilyGraph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def add_edge(self, from_node, to_node):
        if from_node not in self.nodes:
            self.nodes.add(from_node)
        if to_node not in self.nodes:
            self.nodes.add(to_node)
        if from_node not in self.edges:
            self.edges[from_node] = []
        self.edges[from_node].append(to_node)

    def detect_cycle(self):
        for node in self.nodes:
            visited = set()
            path = []
            if self._dfs(node, visited, path):
                return True
        return False

    def _dfs(self, node, visited, path):
        visited.add(node)
        path.append(node)
        if node in self.edges:
            for neighbor in self.edges[node]:
                if neighbor not in visited:
                    if self._dfs(neighbor, visited, path):
                        return True
                elif neighbor in path:
                    # 标记为“弱”边，这里简单标记为-1
                    self.edges[node][self.edges[node].index(neighbor)] = -1
                    return True
        path.pop()
        return False


# 创建家族图实例
family = FamilyGraph()
# 添加边
family.add_edge('A', 'B')
family.add_edge('B', 'C')
family.add_edge('C', 'A')
# 检测循环
print(family.detect_cycle())