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

Question

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

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

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

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

Уточнение: я говорю о ориентированных графах здесь. & Quot; root & Quot; Я имею в виду, что это узел с наибольшей достижимостью. Я обновил текст выше, заменив ссылки на & Quot; tree & Quot; с " graph " ;. Я склонен думать о них как о деревьях, потому что форма в основном похожа на дерево. График на самом деле состоит из объектов в куче Java и, как вы можете себе представить, является достаточно иерархическим. Я обнаружил, что дерево доминаторов полезно при анализе утечек OOM, потому что вас интересует & Quot; что поддерживает этот объект живым? & Quot; и ответ, в конечном счете, является его доминирующим. Деревья доминаторов позволяют вам & Lt; ahem & Gt; увидеть дерево, а не деревья. Но иногда много мусора всплывает на вершину дерева, так что у вас есть корень с тысячами детей прямо под ним. В таких случаях я хотел бы поэкспериментировать с вычислением деревьев-доминантных корней у каждого из прямых потомков (в исходном графике) корня, а затем, возможно, перейти на следующий уровень вниз и так далее. (Я стараюсь не беспокоиться о возможности обратных ссылок в настоящее время:)

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

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

Вы можете просто выполнить поиск " инкрементное обновление дерева доминирования " найти некоторые ссылки.

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