Индексирование частично упорядоченного множества

Если множество конечно, то диаграмма Хассе.

и да

No document with DOI "10.1.1.88.6760"

В гугле забил «efficient storage of partially ordered sets», вторая ссылка. Ща, кстати, первую посмотрю.

Диаграмма Хассе не даёт быстрого ответа на вопрос «сравнимы ли А и Б» и кто из них больше. Также неплохо бы иметь процедуру, которая пополняет уже построенное хранилище новым элементом, добавляя его в «индекс».

Блин, это диссер какой-то, причём от 2013 года. Что, наука не доросла что ли ещё до осознания частично упорядоченных множеств? Я думал уже есть стандартная библиотечка, с которой я просто ещё пока что не сталкивался. Блин :(

Хотя на лиспе что-то нагуглилось по редкому слову poset:

https://bitbucket.org/mt/biobike/src/0776fd5740a5900534620e3310cb238ac1fc5e4b...

Простите меня за возможную глупость, но индексом, в данном случае, возможно будет упорядоченное множество, отсортируйте его.

https://stackoverflow.com/questions/14510148/c-c-graph-interface-for-represen...

Хрена ж себе, XXI век...

О, нашёл тег, завтра гляну:

https://stackoverflow.com/questions/tagged/partial-ordering

Нашлось такое:

... Using this algorithm, we design a succinct data structure for representing a poset that, given two elements, can report whether one precedes the other in constant time. ...

В общем, если брать дуболомный способ, то это называется «орграф», где стрелки указывают отношение «следующий». Если записать это в виде матрицы, где по столбцам и строкам идут вершины, а в ячейках - единицы там, где есть стрелка, то это будет матрица смежности.

Её за время О(число_вершин^3) можно достроить до матрицы достижимости, которая как раз и даёт то, что я просил - это «алгоритм Флойда - Уоршелла», который придумал и опубликовал первым, как ни странно, Бернард Рой :)

Есть и другие алгоритмы вычисления матрицы достижимости (находим по википедии), которые в каких-то случаях работают быстрее.

Накопал в ходе поисков сайт e-maxx.ru с описанием алгоритмов

Но, как оказалось, мне нужно не совсем это... А целая куча всяких действий над графами. Тем не менее, вопрос решён. Ещё была полезной книжка Новиков «дискретная математика для программистов».

Дуболомность способа в данном случае состоит в том, что не используется антисимметричность. Плюс, в моём случае заданы только вершины, а не рёбра, поэтому заполнение матрицы смежности требует N^2 сравнений, и уже сразу получается матрица достижимости. Плюс нельзя строить инкрементно, при изменении (например, при удалении ребра) всё нужно переделывать заново. Так что свою частную задачу я вроде решил, но в целом тема не раскрыта. Возможно, по ссылкам, к-рые тут накидали, приведены хорошие алгоритмы - я этого не проверял.