Алгоритм Python для автоматического транзитивного распространения неравенств ⇐ Python

[Anonymous]

Я пытаюсь создать алгоритм Python, который может транзитивно распространять неравенства между объектами. Например, если я знаю, что A < B и B < C, я хочу, чтобы система автоматически делала вывод, что A < C.
У меня есть простой класс реестра, который отслеживает сегменты линий и неравенства. Простой тест текущей реализации показывает, что прямые неравенства, такие как A < B и B < C, работают правильно, но косвенные неравенства, такие как A < C, не выводятся автоматически.
Вот мой класс реестра и простой тест реализации:

Код: Выделить всё

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()

Мне нужен способ автоматического транзитивного распространения неравенств в реестре, чтобы запрос A < C после добавления A < B и B < C возвращал значение True. Я хотел бы, чтобы это масштабировалось для произвольного количества отрезков линий и неравенств. Мне нужен совет о том, какая структура данных или алгоритм подойдут для этого в Python и как я могу изменить класс реестра для поддержки такого поведения.


Подробнее здесь: https://stackoverflow.com/questions/798 ... ansitively