В DAG, как найти вершины, где сходятся пути?

Question

У меня есть тип направленного ациклического c графа с некоторыми ограничениями.

1. Существует только одна "входная" вершина
2. Может быть несколько листовых вершин
3. После разделения пути все, что находится под этим путем, не может попасть на другой путь (это станет яснее с некоторыми примерами ниже)
4. Может быть любое количество «расщепленных» вершин. Они могут быть вложенными.
5. «Разделенная» вершина может быть разбита на любое количество путей. В приведенных ниже примерах показаны только 2 пути для каждого, но их может быть больше.

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

Пример A:

пример a

В этом примере вершина A это вершина "расщепления", и ее "вершина переподключения" - это F.

Пример B:

пример b

Здесь есть две расщепленные вершины: A и E. Для обеих из них вершина G является вершиной переподключения.

Пример C:

пример c

Теперь есть три расщепленные вершины: A, D и E. Соответствующие вершины переподключения:

• A -> K
• D -> K
• E -> J

Пример D:

пример d

Здесь мы снова имеем три расщепленных вершины: A, D и E. Но на этот раз у вершины E нет вершины переподключения, потому что один из путей заканчивается рано.

Answer 1

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

Если на графике нет циклов, то решение (a), предложенное @ matt-timmermans, будет работать.

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

1. в каждом узле разбиения, вводить уникальный токен в граф вдоль каждого исходящего ребра и
2. распространять токены через граф с учетом этого ограничения: если узел n доступен из разделенного узла m, то токены, поступающие в узел m, проходят через узел n, только если все токены узла m прибыли в узел n.

В конце узел n после доминирует над узлом m, если все токены узла m достигли узла n.

Answer 2

Похоже на то, что вы хотите:

1. Соединить каждую вершину с нулевой степенью 0 с одной терминальной вершиной
2. Построить доминатор дерево графа с обратным ребром. Связанная статья в википедии указывает на пару алгоритмов для этого.
3. «Переподключенная вершина» для расщепленной вершины является ее непосредственным доминирующим элементом в графе с обратным ребром, то есть его родителем в этом дереве доминирующих элементов. Это называется «постдоминатор» в вашем исходном графике. Если это конечная вершина, которую вы добавили, то у нее нет вершины переподключения в исходном графе.