Построение диаграммы Хассе

[B@R5uk]

В связи с последними моими изысками у меня возникла следующая интересная подзадача.

Имеется некоторый направленный граф, вершины которого соответствуют множествам, а направленные рёбра — соотношениям включения между этими множествами. То есть если множество A является подмножеством множества B, то от вершины A к вершине B ведёт ребро (направленное). Требуется по этому графу построить диаграмму Хассе. Корректность исходного графа гарантируется. Диаграмма Хассе — это весьма похожий граф, но у него выполнено ключевое условие: если из вершины A в вершину B ведёт ребро (обозначение: $A\to B$), то не существует такой вершины C, что бы $A\to C\to B$. Нестрого говоря, диаграмма Хассе — это максимально прореженный граф включений без потери информации.

Мой вопрос в том, если какие-нибудь красивые и/или проработанные алгоритмы для решения этой задачи? Моё наивное решение мне видится таким: перебирать все вершины из каждой вершины искать все возможные пути и удалять все найденные пути, длиннее, чем одно ребро. Кажется, слишком трудоёмко. Может есть возможность строить диаграмму Хассе на лету без предварительного полного графа включений?

[Xaositect]

Это называется топологическая сортировка, есть специальные алгоритмы.

[arseniiv]

(Оффтоп)

Ого, до меня раньше не доходило, что две вещи, которые я про себя называл «детранзитивация» (частичного порядка до какого-то минимального отношения, транзитивное замыкание которого даст порядок) и «линеаризация» (как раз название получше, на мой взгляд, для топологической сортировки — ведь если начинать с частичного порядка, получаем какой-нибудь из линейных, содержащих его, а если начинать с какого-то другого отношения без циклов, то можно вместо него брать его транзитивное замыкание) делаются практически одинаково, именно из-за того что я везде представлял частичный порядок. Немного странно, что мы по сути можем одновременно находить и транзитивное замыкание, и притом получать параллельно такой скелетик. И честно говоря я сейчас так и не понял, как это друг с другом увязывается.

[B@R5uk]

Xaositect, топологическая сортировка, если верить вики, — это немного другое (хоть и связанное) понятие: она используется для того, чтобы отсортировать вершины графа в линейную последовательность. Мне же надо из полного графа отношений выкинуть часть рёбер (являющихся следствием других отношений), то есть результатом работы требующегося мне алгоритма будет всё так же направленный граф, а не последовательность. Или я что-то не правильно понял?

[arseniiv]

B@R5uk
Можно вместо выдачи каждой вершины добавлять вершину в новый изначально пустой граф-результат, соединяя её со всеми подходящими ранее добавленными туда. Тогда получится красота, если ничего не упускаю.

-- Вт апр 07, 2020 18:43:24 --

Ну или можно оперировать над тем же графом, используя рёбра разных цветов, чтобы не запутаться.

[Xaositect]

Да, я, похоже, немного поторопился и все не слишком тривиально (хотя достаточно просто, как arseniiv говорит). Алгоритм топологической сортировки можно модифицировать для Вашей задачи: при добавлении очередной вершины $u_k$ в сортированный список $u_1, \dots, u_{k-1}$ смотрим на все ребра $(u_i, u_k)$ и помечаем те из них, которые лишние ($\exists j\colon (u_i, u_j) \in E, (u_j, u_k) \in E$). В самом конце удаляем все помеченные ребра.

[B@R5uk]

arseniiv в сообщении #1452349 писал(а):

соединяя её со всеми подходящими ранее добавленными туда.

Ключевой вопрос в том, как определить какие из них подходящие? Топологическая сортировка просто гарантирует то, что все потомки в списке окажутся справа от вершины, а все предки — слева. Если я ничего не упустил при анализе этого алгоритма, то он никак не помечает являются ли потомки и предки непосредственными или же разделены одним или большим числом поколений. За то этот алгоритм корректно отрабатывает исключение в случае, если в графе есть циклы.

-- 08.04.2020, 19:53 --

Xaositect в сообщении #1452354 писал(а):

смотрим на все ребра $(u_i, u_k)$ и помечаем те из них, которые лишние ($\exists j\colon (u_i, u_j) \in E, (u_j, u_k) \in E$).

Судя по всему надо будет городить новый алгоритм. Тем более, что мне не нужно упорядочивание, так как я знаю, какая вершина является корнем, какая — "макушкой" этого ветвистого графа.

[B@R5uk]

Получается, для каждой вершины надо пройти в глубину на два уровня и пометить все рёбра, что ведут из обрабатываемой вершины в потомки второго поколения. Помеченные рёбра будут следствием транзитивности. Получается три вложенных цикла. Корректность гарантируется тем, что исходных граф полный. Интересно, это можно упростить до двух циклов или реализовать ещё как-нибудь?

[Dmitriy40]

А нельзя ли из вершины пустить обратную волну по рёбрам против стрелочек? Тогда при приходе в вершину проверять не прошла ли по ней уже волна и если да, то удалять последнее ребро. Т.е. останутся только кратчайшие пути от каждой вершины до корня.

[B@R5uk]

Dmitriy40 в сообщении #1452942 писал(а):

по рёбрам против стрелочек

На самом деле нет никакой разницы между направлениями: стрелки можно обратить. Или хранить для каждой вершины не только список потомков, но и список родителей.

Dmitriy40 в сообщении #1452942 писал(а):

Т.е. останутся только кратчайшие пути от каждой вершины до корня.

Смысл как раз в обратном: от корня к каждой вершине идёт по стрелочке, надо из них выкинуть лишние. Равно как от каждой вершины к макушке идёт по стрелочке, часть из них — так же лишние.

B@R5uk в сообщении #1452902 писал(а):

Получается три вложенных цикла.

Набросал пока тестовый вариант с массивами (в основной программе у меня динамические структуры данных):

Используется синтаксис Java

import java.util.*;

public class Study_Hasse_Diagram {
        
        private static Scanner scanner = new Scanner(System.in);
        private static int[][] graph;
        private static boolean[][] flags;
        
        public static void main(String[] args) {
                int k, l, m, n, nodesNumber, childrenNumber, grandchildrenNumber;
                boolean[] nodesFlags;
                boolean displayFlag;
                System.out.println("Input data:");
                nodesNumber = scanner.nextInt();
                graph = new int[nodesNumber][];
                flags = new boolean[nodesNumber][];
                for (k = 0; nodesNumber > k; ++k) {
                        childrenNumber = scanner.nextInt();
                        graph[k] = new int[childrenNumber];
                        flags[k] = new boolean [childrenNumber];
                        for (l = 0; childrenNumber > l; ++l) {
                                graph[k][l] = scanner.nextInt();
                        }
                }
                scanner.close();
                for (k = 0; nodesNumber > k; ++k) {
                        childrenNumber = graph[k].length;
                        nodesFlags = new boolean[nodesNumber];
                        for (l = 0; childrenNumber > l; ++l) {
                                m = graph[k][l];
                                grandchildrenNumber = graph[m].length;
                                for (n = 0; grandchildrenNumber > n; ++n) {
                                        nodesFlags[graph[m][n]] = true;
                                }
                        }
                        for (l = 0; childrenNumber > l; ++l) {
                                if (nodesFlags[graph[k][l]]) {
                                        flags[k][l] = true;
                                }
                        }
                }
                System.out.println("\nFull graph:");
                for (k = 0; nodesNumber > k; ++k) {
                        System.out.print(String.format("%d", k));
                        childrenNumber = graph[k].length;
                        displayFlag = false;
                        for (l = 0; childrenNumber > l; ++l) {
                                if (displayFlag) {
                                        System.out.print(String.format(", %d", graph[k][l]));
                                } else {
                                        displayFlag = true;
                                        System.out.print(String.format(" -> %d", graph[k][l]));
                                }
                        }
                        System.out.println('.');
                }
                System.out.println("\nHasse graph:");
                for (k = 0; nodesNumber > k; ++k) {
                        System.out.print(String.format("%d", k));
                        childrenNumber = graph[k].length;
                        displayFlag = false;
                        for (l = 0; childrenNumber > l; ++l) {
                                if (!flags[k][l]) {
                                        if (displayFlag) {
                                                System.out.print(String.format(", %d", graph[k][l]));
                                        } else {
                                                displayFlag = true;
                                                System.out.print(String.format(" -> %d", graph[k][l]));
                                        }
                                }
                        }
                        System.out.println('.');
                }
        }
}
 

Примеры работы:

(Раз)

Input data:
15
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 10 11
2 10 12
7 1 7 10 11 12 13 14
2 10 13
7 2 6 10 11 12 13 14
2 10 12
2 10 11
2 10 13
7 4 8 10 11 12 13 14
0
1 10
1 10
1 10
4 10 11 12 13

Full graph:
0 -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.
1 -> 10, 11.
2 -> 10, 12.
3 -> 1, 7, 10, 11, 12, 13, 14.
4 -> 10, 13.
5 -> 2, 6, 10, 11, 12, 13, 14.
6 -> 10, 12.
7 -> 10, 11.
8 -> 10, 13.
9 -> 4, 8, 10, 11, 12, 13, 14.
10.
11 -> 10.
12 -> 10.
13 -> 10.
14 -> 10, 11, 12, 13.

Hasse graph:
0 -> 3, 5, 9.
1 -> 11.
2 -> 12.
3 -> 1, 7, 14.
4 -> 13.
5 -> 2, 6, 14.
6 -> 12.
7 -> 11.
8 -> 13.
9 -> 4, 8, 14.
10.
11 -> 10.
12 -> 10.
13 -> 10.
14 -> 11, 12, 13.

(Два)

Input data:
18
17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2 12 13
2 12 14
7 1 8 12 13 14 15 16
2 12 15
2 12 15
9 2 4 5 7 12 13 14 15 16
2 12 14
2 12 13
6 12 13 14 15 16 17
6 12 13 14 15 16 17
14 1 2 3 4 5 6 7 8 12 13 14 15 16 17
0
1 12
1 12
1 12
4 12 13 14 15
5 12 13 14 15 16

Full graph:
0 -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17.
1 -> 12, 13.
2 -> 12, 14.
3 -> 1, 8, 12, 13, 14, 15, 16.
4 -> 12, 15.
5 -> 12, 15.
6 -> 2, 4, 5, 7, 12, 13, 14, 15, 16.
7 -> 12, 14.
8 -> 12, 13.
9 -> 12, 13, 14, 15, 16, 17.
10 -> 12, 13, 14, 15, 16, 17.
11 -> 1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 16, 17.
12.
13 -> 12.
14 -> 12.
15 -> 12.
16 -> 12, 13, 14, 15.
17 -> 12, 13, 14, 15, 16.

Hasse graph:
0 -> 9, 10, 11.
1 -> 13.
2 -> 14.
3 -> 1, 8, 16.
4 -> 15.
5 -> 15.
6 -> 2, 4, 5, 7, 16.
7 -> 14.
8 -> 13.
9 -> 17.
10 -> 17.
11 -> 3, 6, 17.
12.
13 -> 12.
14 -> 12.
15 -> 12.
16 -> 13, 14, 15.
17 -> 16.

(Три)

Input data:
40
39 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
3 29 30 31
2 29 32
11 1 19 21 23 29 30 31 32 33 34 35
3 29 33 36
3 29 34 37
3 29 32 38
3 29 32 39
3 29 34 39
3 29 32 36
3 29 30 38
7 2 29 30 32 33 34 35
3 29 33 39
3 29 34 36
3 29 32 37
3 29 33 37
11 4 9 13 25 29 30 32 33 34 35 36
3 29 30 37
3 29 34 38
3 29 31 32
11 5 14 15 17 29 30 32 33 34 35 37
3 29 31 33
11 7 8 12 27 29 30 32 33 34 35 39
3 29 31 34
3 29 33 38
3 29 30 36
11 6 10 18 24 29 30 32 33 34 35 38
3 29 30 39
13 2 6 7 9 14 19 29 31 32 36 37 38 39
0
1 29
1 29
1 29
1 29
1 29
5 29 30 32 33 34
1 29
1 29
1 29
1 29

Full graph:
0 -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39.
1 -> 29, 30, 31.
2 -> 29, 32.
3 -> 1, 19, 21, 23, 29, 30, 31, 32, 33, 34, 35.
4 -> 29, 33, 36.
5 -> 29, 34, 37.
6 -> 29, 32, 38.
7 -> 29, 32, 39.
8 -> 29, 34, 39.
9 -> 29, 32, 36.
10 -> 29, 30, 38.
11 -> 2, 29, 30, 32, 33, 34, 35.
12 -> 29, 33, 39.
13 -> 29, 34, 36.
14 -> 29, 32, 37.
15 -> 29, 33, 37.
16 -> 4, 9, 13, 25, 29, 30, 32, 33, 34, 35, 36.
17 -> 29, 30, 37.
18 -> 29, 34, 38.
19 -> 29, 31, 32.
20 -> 5, 14, 15, 17, 29, 30, 32, 33, 34, 35, 37.
21 -> 29, 31, 33.
22 -> 7, 8, 12, 27, 29, 30, 32, 33, 34, 35, 39.
23 -> 29, 31, 34.
24 -> 29, 33, 38.
25 -> 29, 30, 36.
26 -> 6, 10, 18, 24, 29, 30, 32, 33, 34, 35, 38.
27 -> 29, 30, 39.
28 -> 2, 6, 7, 9, 14, 19, 29, 31, 32, 36, 37, 38, 39.
29.
30 -> 29.
31 -> 29.
32 -> 29.
33 -> 29.
34 -> 29.
35 -> 29, 30, 32, 33, 34.
36 -> 29.
37 -> 29.
38 -> 29.
39 -> 29.

Hasse graph:
0 -> 3, 11, 16, 20, 22, 26, 28.
1 -> 30, 31.
2 -> 32.
3 -> 1, 19, 21, 23, 35.
4 -> 33, 36.
5 -> 34, 37.
6 -> 32, 38.
7 -> 32, 39.
8 -> 34, 39.
9 -> 32, 36.
10 -> 30, 38.
11 -> 2, 35.
12 -> 33, 39.
13 -> 34, 36.
14 -> 32, 37.
15 -> 33, 37.
16 -> 4, 9, 13, 25, 35.
17 -> 30, 37.
18 -> 34, 38.
19 -> 31, 32.
20 -> 5, 14, 15, 17, 35.
21 -> 31, 33.
22 -> 7, 8, 12, 27, 35.
23 -> 31, 34.
24 -> 33, 38.
25 -> 30, 36.
26 -> 6, 10, 18, 24, 35.
27 -> 30, 39.
28 -> 2, 6, 7, 9, 14, 19.
29.
30 -> 29.
31 -> 29.
32 -> 29.
33 -> 29.
34 -> 29.
35 -> 30, 32, 33, 34.
36 -> 29.
37 -> 29.
38 -> 29.
39 -> 29.

Работать работает, но вопрос о более рациональном алгоритме пока открыт.

-- 09.04.2020, 08:37 --

Dmitriy40 в сообщении #1452942 писал(а):

А нельзя ли из вершины пустить обратную волну по рёбрам против стрелочек?

Вообще, идея интересная. Можно начать с корня, идти по стрелочкам и каждому следующему поколению присваивать на единицу большую величину. Тогда искомыми рёбрами диаграммы Хассе будут стрелочки, соединяющие вершины с разницей присвоенных величин в единицу. Однако, у такого подхода есть подвох в случае, если две ветви графа содержат разное число поколений, например:

$$0\to 1,\;0\to 2,\;1\to 3,\;2\to 4,\;3\to 4$$

[Sender]

Стоп, разве это не задача нахождения остовного дерева в орграфе?
Хотя у вас же изначально граф без циклов, так что речь скорее о транзитивном сокращении. https://en.wikipedia.org/wiki/Transitive_reduction
Вот что вики пишет по поводу алгоритма:

Цитата:

It had already been shown that transitive closure and multiplication of Boolean matrices of size n × n had the same complexity as each other,[4] so this result put transitive reduction into the same class. The fastest known exact algorithms for matrix multiplication, as of 2015, take time $O(n^{2.3729})$,[5] and this gives the fastest known worst-case time bound for transitive reduction in dense graphs.

-- Чт апр 09, 2020 12:32:00 --

arseniiv в сообщении #1452339 писал(а):

И честно говоря я сейчас так и не понял, как это друг с другом увязывается.

Кстати, в той статье на вики есть пара слов и об этом.

[arseniiv]

Sender
Спасибо! И за термин «транзитивное сокращение».

Алгоритм с построением сокращения по замыканию вообще гениальный. В принципе довольно очевидный, но пока ещё додумаешься?

B@R5uk в сообщении #1453003 писал(а):

Работать работает, но вопрос о более рациональном алгоритме пока открыт.

Я может чуть позже не смотря на ваш код запилю что-то этакое и можно будет сравнить для интереса.

P. S. Ага, я посмотрел ту страницу и теперь не знаю, осталось ли желание использовать модифицированную топ. сортировку по сравнению с другими подходами к получению замыкания (тупо Флойдом—Уоршеллом). Теперь вопрос больше другой: насколько много рёбер в графах, получающихся у B@R5uk, то есть имеет ли смысл использовать алгоритм для разреженных графов? Самый оптимистичный случай — группа, все собственные подгруппы которой не сравнимы, тогда рёбер $2(|V| - 2)$, итого сложность будет $O(|V|^2)$. Насколько близкие к таким группы часты среди рассматриваемых?..

[Dmitriy40]

B@R5uk в сообщении #1453003 писал(а):

Вообще, идея интересная. Можно начать с корня, идти по стрелочкам и каждому следующему поколению присваивать на единицу большую величину. Тогда искомыми рёбрами диаграммы Хассе будут стрелочки, соединяющие вершины с разницей присвоенных величин в единицу. Однако, у такого подхода есть подвох в случае, если две ветви графа содержат разное число поколений, например:

$$0\to 1,\;0\to 2,\;1\to 3,\;2\to 4,\;3\to 4$$

Это и есть волна. Только пример у Вас неправильный, из вершины $0$ выходят стрелки с разным поколениями, правильнее будет так:
начнём с исходного графа:
$A \to B,\; B \to C,\; C \to D,\; A \to E,\; E \to D$
присваиваем вершинам поколения:
$A_0 \to B_1,\; A_0 \to E_1,\; B_1 \to C_2,\; E_1 \to D_2,\; C_2 \to D_3$
получили противоречие для вершины $D$, одну из стрелок удаляем, логичнее удалять более длинный путь $C_2 \to D_3$, разумеется это можно и нужно делать сразу в момент присвоения, когда видим что $D$ уже имеет меньший номер поколения чем хотим присвоить, в итоге получится граф:
$A_0 \to B_1,\; A_0 \to E_1,\; B_1 \to C_2,\; E_1 \to D_2$
И на циклы и множественность путей тут совершенно наплевать, оно как раз и исключается волной.
Но, это совершенно не Хассе, чтобы получить её надо делать именно как Вы и предположили, удалять все рёбра между вершинами, отличающимися поколениями более чем на 1. Собственно ничего удалять и не надо, достаточно лишь перенумеровать все вершины по поколениям и тут же получим нужную диаграмму.

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

[B@R5uk]

arseniiv в сообщении #1453079 писал(а):

Теперь вопрос больше другой: насколько много рёбер в графах?

Чтобы не таить никаких секретов, сразу скажу, что мои графы являются графами отношения порядка на множестве всех подгрупп какой-либо заданной группы. На счёт много ли рёбер в таких графах, сказать ничего не могу, так как не с чем сравнивать (да и занятие это весьма не простое). Одно могу сказать точно: в любом графе есть две выделенные вершины, соответствующие несобственным подгруппам: из единичной стрелки ведут в каждую вершину, а из каждой вершины — в вершину, соответствующей всей группе.

Sender в сообщении #1453034 писал(а):

It had already been shown that transitive closure and multiplication of Boolean matrices of size n × n had the same complexity as each other,[4] so this result put transitive reduction into the same class.

То есть, получается, что мой алгоритм выше уже является вполне себе успешным, так как простое умножение матриц как раз и имеет кубическую сложность?

-- 09.04.2020, 14:29 --

Dmitriy40 в сообщении #1453080 писал(а):

одну из стрелок удаляем

Нельзя этого делать. Циферками у меня были обозначены не номера поколений, а названия вершин. И это уже редуцированный граф, в нём нельзя ничего удалять. Если вам нравятся буквы (впрочем, они даже лучше, я цифрами пользуюсь, потому что компьютеру проще вершины нумеровать, но это можно переделать), то полный граф для

$$A\to B,\;B\to C,\;C\to D,\;A\to E,\;E\to D$$

будет таким:

$$A\to B,\;A\to C,\;A\to D,\;A\to E,\;B\to C,\;B\to D,\;C\to D,\;E\to D$$

-- 09.04.2020, 14:34 --

Dmitriy40 в сообщении #1453080 писал(а):

Итог работы зависит от выбора корня.

Ну, в моём случае корнем является вершина, из которой рёбра только выходят, входящих нет. Её существование и единственность гарантируются групповыми аксиомами.

[arseniiv]

B@R5uk в сообщении #1453084 писал(а):

Чтобы не таить никаких секретов, сразу скажу, что мои графы являются графами отношения порядка на множестве всех подгрупп какой-либо заданной группы.

Да, вы вроде так в начале и написали, это понятно, а вот группы бывают весьма разные. Например какая-нибудь $\mathbb Z_3^n$ будет иметь графом подгрупп булеву алгебру (хотя стоп, мы включаем туда изоморфные подгруппы или собираем их в одну? забыл).

B@R5uk в сообщении #1453084 писал(а):

То есть, получается, что мой алгоритм выше уже является вполне себе успешным, так как простое умножение матриц как раз и имеет кубическую сложность?

Да, я бы так думал. Теперь если выбирать из кубических алгоритмов, а не оптимизировать сложность дальше (связанные с умножением матриц вроде с самого начала страшные идут, хотя вы вроде реализовывали умножение Штрассена где-то… но я нет и меня бы писать его самому немного пугало наверно), то наверно выбирать какой-нибудь более красивый из всех и легче избавляемый от потенциальных ошибок.