Подтвердить что ты не робот

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

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

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

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

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

Разъяснение: Я говорю о ориентированных графах здесь. "Корень", на который я ссылаюсь, на самом деле является node с наибольшей достижимостью. Я обновил текст выше, заменив ссылки на "tree" на "graph". Я склонен думать о них как о деревьях, потому что форма в основном похожа на дерево. Граф фактически представляет собой объекты в куче java, и, как вы можете себе представить, является достаточно иерархичным. Я нашел дерево доминанта полезным при анализе утечки OOM, потому что вас интересует "что поддерживает этот объект?" и ответ, в конечном счете, является его главенством. Доминирующие деревья позволяют вам < гем > видеть дерево, а не деревья. Но иногда много нежелательных поплавков на вершине дерева, поэтому у вас есть корень с тысячами детей прямо под ним. В таких случаях я бы хотел поэкспериментировать с вычислением деревьев доминантных корней у каждого из прямых детей (в исходном графе) корня, а затем, возможно, перейти на следующий уровень вниз и так далее. (Я стараюсь не беспокоиться о возможности обратных ссылок на данный момент:)

4b9b3361

ОТВЕТЫ

Ответ 2

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

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

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

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

Я надеюсь, что это поможет!

Ответ 3

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

Ответ 4

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

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

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