Эффективный способ рекурсивного вычисления дерева доминант?

Question

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

Мой вопрос заключается в том, существует ли эффективное решение для этого, которое использует информацию о непосредственном доминирующем элементе, уже рассчитанную в исходном дереве доминирующих для корневого узла? Другими словами, я не хочу начинать с нуля каждого из детей, потому что весь процесс довольно трудоемкий.

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

Кстати, точно так же, как это ни странно: странно, что тема деревьев-доминант "принадлежит" людям, занимающимся компиляцией, и об этом нет упоминаний в книгах по классической теории графов. Приложение, для которого я его использую - мой анализатор кучи Java FindRoots - не связано с теорией компилятора.

Уточнение: я говорю о ориентированных графах здесь. «Корень», на который я ссылаюсь, - это узел с наибольшей достижимостью. Я обновил текст выше, заменив ссылки на «дерево» на «график». Я склонен думать о них как о деревьях, потому что форма в основном подобна дереву. График на самом деле состоит из объектов в куче Java и, как вы можете себе представить, является достаточно иерархическим. Я обнаружил, что дерево доминаторов полезно при анализе утечек OOM, потому что вас интересует «что поддерживает этот объект?» и ответ, в конечном счете, является его доминирующим. Деревья Dominator позволяют видеть дерево, а не деревья. Но иногда много мусора всплывает на вершину дерева, так что у вас есть корень с тысячами детей прямо под ним. В таких случаях я хотел бы поэкспериментировать с вычислением деревьев-доминантных корней у каждого из прямых потомков (в исходном графике) корня, а затем, возможно, перейти на следующий уровень вниз и так далее. (Я стараюсь пока не беспокоиться о возможности обратных ссылок:)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs может помочь.

Answer 2

Судя по отсутствию комментариев, я думаю, что на Stackoverflow не так много людей, которые могли бы вам помочь. Я один из тех людей, но я не хочу, чтобы такой интересный вопрос решался с глухим стуком, поэтому я попытаюсь протянуть руку.

Моя первая мысль: если этот граф генерируется другими компиляторами, стоило бы взглянуть на компилятор с открытым исходным кодом, например, GCC, чтобы посмотреть, как он решает эту проблему?

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

Что я хотел бы сделать, это создать оболочку вокруг каждого узла, которая содержит сам узел и любые предварительно вычисленные данные, связанные с этим узлом. Затем новое дерево будет реконструировано из старого дерева рекурсивно с использованием этих классов-обёрток. Когда вы строите это дерево, вы начинаете с корня и продвигаетесь к конечным узлам. Для каждого узла вы сохраните результат вычисления для всех предков. Таким образом, вам нужно будет только взглянуть на родительский узел и данные текущего узла, которые вы обрабатываете, чтобы вычислить значение для вашего нового узла.

Надеюсь, это поможет!

Answer 3

Не могли бы вы уточнить, с какого графика вы начинаете? Я не вижу никакой разницы между графом, который является деревом, и доминантным деревом этого графа. Родителем каждого узла должен быть его idom, и, конечно, над ним будет доминировать все, что находится над ним в дереве.

Answer 4

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

Вы можете просто выполнить поиск "дерева доминирующих обновлений обновлений", чтобы найти некоторые ссылки.

Полагаю, вы знаете, Eclipse Memory Analyzer использует деревья-доминаторы, так что эта тема больше не полностью "принадлежит" сообществу компиляторов:)