Я ищу структуру данных для хранения poset, которая поддерживает следующие операции с большой сложностью (это часто делается):
- определение того, может ли данный элемент быть последовательноупорядочено перед другим (высший приоритет над другими)
- добавление новых ограничений упорядочения
- возвращение всех элементов, которые можно упорядочить перед данным элементом
Структура данных должнатакже поддерживает генерацию полностью упорядоченного набора из poset, но это нужно сделать только один раз для вывода после того, как алгоритм уже запущен.
До сих пор я полагался на простую реализацию poset, но яДостигнув точки, когда это уже невозможно.
Я посмотрел на https://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements, и в ответах есть несколько интересных статей, но большинство этих структур данных (например, ChainMerge), похоже,быть оптимизированным с учетом сортировки, где для меня это наименее важный шаг.