如何改造Python Registry类实现不等式的自动传递性传播？

需要构建支持对象间不等式传递性传播的Python算法：已知A < B和B < C时，系统需自动推断A < C。现有Registry类仅能处理直接添加的不等式，无法推导间接传递关系，需改造该类以适配任意数量的线段与不等式。

现有代码如下：

class Registry:
    """
        A registry of line segments and inequalities
    """

    def __init__(self):
        """
            A registry of all the line segments and inequalities 
            that have been added to the system.
        """
        self.line_segments = []
        self.inequalities = []

    def add_line_segment(self, name):
        """
            Add a line segment to the registry.
             - name: the name of the line segment
        """
        for ls in self.line_segments:
            if ls == name:
                assert False, f"Line segment {name} already exists in the registry."
        self.line_segments.append(name)
    
    def add_inequality(self, m, n):
        """
            Add an inequality to the registry.
             - m: the name of the first line segment
             - n: the name of the second line segment
        """

        for ineq in self.inequalities:
            if ineq == (m, n):
                assert False, f"Inequality {m} < {n} already exists in the registry."
            if ineq == (n, m):
                assert False, f"Inequality {n} < {m} already exists in the registry."
        self.inequalities.append((m, n))

    def question_inequality(self, m, n):
        """
            Question whether an inequality holds in the registry.
             - m: the name of the first line segment
             - n: the name of the second line segment
        """
        for ineq in self.inequalities:
            if ineq == (m, n):
                return True
            if ineq == (n, m):
                return False
        assert False, f"Inequality {m} < {n} is not in the registry."

def main():
    """
        A simple test of the registry.
    """
    
    R = Registry()
    R.add_line_segment("A")
    R.add_line_segment("B")
    R.add_line_segment("C")
    R.add_inequality("A", "B")
    R.add_inequality("B", "C")
    if R.question_inequality("A", "B"):
        print("A < B")
    if R.question_inequality("B", "C"):
        print("B < C")
    # Currently false, but the goal is to make this true through propagation of inequalities.
    if R.question_inequality("A", "C"):
        print("A < C")
    else:
        print("A < C is not in the registry.")
        
if __name__ == "__main__":
    main()

推荐的数据结构与算法 #

• 邻接表：替代原有的不等式列表，用字典存储直接的m < n关系（即有向边m → n），便于遍历和扩展传递关系。
• 传递性判断方案：
  • 小规模场景：用BFS/DFS动态查询，在每次查询时遍历邻接表查找从m到n的路径，判断是否存在传递关系。
  • 大规模频繁查询场景：用Floyd-Warshall算法预计算传递闭包，提前生成所有节点间的可达性矩阵，查询时直接返回结果。

改造后的实现 #

方案1：邻接表+BFS动态查询 #

适合小规模节点、查询频率较低的场景，实现简单直观：

class Registry:
    """
    A registry of line segments and inequalities with transitive propagation
    """

    def __init__(self):
        # 邻接表：key为线段名，value为直接小于的线段列表
        self.adjacency = {}
        # 存储所有线段名，快速校验存在性
        self.segments = set()

    def add_line_segment(self, name):
        """Add a line segment to the registry."""
        if name in self.segments:
            assert False, f"Line segment {name} already exists in the registry."
        self.segments.add(name)
        self.adjacency[name] = []
    
    def add_inequality(self, m, n):
        """Add an inequality m < n to the registry."""
        if m not in self.segments or n not in self.segments:
            assert False, f"Line segment {m} or {n} does not exist in the registry."
        # 检查反向传递关系是否存在（避免矛盾）
        if self._has_path(n, m):
            assert False, f"Inequality {n} < {m} already holds (directly or indirectly)."
        # 检查直接关系是否已存在
        if n in self.adjacency[m]:
            assert False, f"Inequality {m} < {n} already exists in the registry."
        # 添加直接边
        self.adjacency[m].append(n)

    def _has_path(self, start, end):
        """Use BFS to check if there's a path from start to end (start < end)."""
        if start == end:
            return False  # 自身不能小于自身
        visited = set()
        queue = [start]
        visited.add(start)
        while queue:
            current = queue.pop(0)
            for neighbor in self.adjacency[current]:
                if neighbor == end:
                    return True
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return False

    def question_inequality(self, m, n):
        """Check if inequality m < n holds (directly or indirectly)."""
        if m not in self.segments or n not in self.segments:
            assert False, f"Line segment {m} or {n} does not exist in the registry."
        if self._has_path(m, n):
            return True
        if self._has_path(n, m):
            return False
        assert False, f"Inequality {m} < {n} cannot be determined from the registry."

def main():
    R = Registry()
    R.add_line_segment("A")
    R.add_line_segment("B")
    R.add_line_segment("C")
    R.add_inequality("A", "B")
    R.add_inequality("B", "C")
    if R.question_inequality("A", "B"):
        print("A < B")
    if R.question_inequality("B", "C"):
        print("B < C")
    # 现在会返回True并打印A < C
    if R.question_inequality("A", "C"):
        print("A < C")
    else:
        print("A < C is not in the registry.")
        
if __name__ == "__main__":
    main()

方案2：预计算传递闭包（Floyd-Warshall） #

适合大规模节点、查询频繁的场景，查询时O(1)返回结果：

class Registry:
    """
    A registry of line segments and inequalities with precomputed transitive closure
    """

    def __init__(self):
        self.segments = set()
        # 传递闭包矩阵：closure[m][n]为True表示m < n（直接或间接）
        self.closure = {}

    def add_line_segment(self, name):
        """Add a line segment to the registry."""
        if name in self.segments:
            assert False, f"Line segment {name} already exists in the registry."
        self.segments.add(name)
        # 初始化闭包矩阵
        self.closure[name] = {}
        for seg in self.segments:
            self.closure[name][seg] = False
            self.closure[seg][name] = False

    def _update_closure(self):
        """Update transitive closure using Floyd-Warshall algorithm."""
        segments = list(self.segments)
        for k in segments:
            for i in segments:
                for j in segments:
                    if self.closure[i][k] and self.closure[k][j]:
                        self.closure[i][j] = True

    def add_inequality(self, m, n):
        """Add an inequality m < n to the registry."""
        if m not in self.segments or n not in self.segments:
            assert False, f"Line segment {m} or {n} does not exist in the registry."
        if self.closure[n][m]:
            assert False, f"Inequality {n} < {m} already holds (directly or indirectly)."
        if self.closure[m][n]:
            assert False, f"Inequality {m} < {n} already exists in the registry."
        # 添加直接关系
        self.closure[m][n] = True
        # 更新传递闭包
        self._update_closure()

    def question_inequality(self, m, n):
        """Check if inequality m < n holds (directly or indirectly)."""
        if m not in self.segments or n not in self.segments:
            assert False, f"Line segment {m} or {n} does not exist in the registry."
        if self.closure[m][n]:
            return True
        if self.closure[n][m]:
            return False
        assert False, f"Inequality {m} < {n} cannot be determined from the registry."

def main():
    R = Registry()
    R.add_line_segment("A")
    R.add_line_segment("B")
    R.add_line_segment("C")
    R.add_inequality("A", "B")
    R.add_inequality("B", "C")
    if R.question_inequality("A", "B"):
        print("A < B")
    if R.question_inequality("B", "C"):
        print("B < C")
    if R.question_inequality("A", "C"):
        print("A < C")
    else:
        print("A < C is not in the registry.")
        
if __name__ == "__main__":
    main()

改造说明 #

1. 存储结构优化：用邻接表或传递闭包矩阵替代原有的不等式列表，提升关系处理效率。
2. 传递性支持：
   • 方案1通过BFS遍历邻接表，动态判断是否存在m到n的传递路径。
   • 方案2通过Floyd-Warshall算法预计算所有节点间的可达性，查询时直接返回结果。
3. 冲突校验增强：添加不等式时不仅检查直接冲突，还校验是否存在反向传递关系，避免逻辑矛盾。

内容的提问来源于stack exchange，提问作者Jasper