ARTICLE AD BOX
I am trying to build a Python algorithm that can transitively propagate inequalities between objects. For example, if I know that A < B and B < C, I want the system to automatically infer that A < C.
I have a simple Registry class that tracks line segments and inequalities. A simple test of the current implementation shows that direct inequalities like A < B and B < C work correctly, but indirect inequalities like A < C are not automatically inferred.
Here is my Registry class and a simple test of the implementation:
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()I want a way for the registry to automatically propagate inequalities transitively so that querying A < C after adding A < B and B < C would return True. I would like this to scale for an arbitrary number of line segments and inequalities. I am looking for advice on what data structure or algorithm would work well for this in Python and how I could modify the Registry class to support this behavior.
