Эффективный способ рекурсивно вычислить дерево доминаторов?
Я использую алгоритм Ленгауэра и Тарьяна со сжатием пути, чтобы вычислить дерево доминаторов для графа с миллионами узлов. Алгоритм довольно сложный, и я должен признать, что не нашел времени, чтобы полностью его понять, я просто использую его. Теперь мне нужно вычислить деревья доминаторов прямых потомков корневого узла и, возможно, рекурсивно пройти вниз по графу до определенной глубины, повторяя эту операцию. Т.е. когда я вычисляю дерево доминаторов для дочернего элемента корневого узла, я хочу сделать вид, что корневой узел был удален из графа.
Мой вопрос в том, есть ли эффективное решение для этого, которое использует информацию о непосредственном доминирующем элементе, уже вычисленную в начальном дереве доминатора для корневого узла? Другими словами, я не хочу начинать с нуля для каждого из детей, потому что весь процесс занимает довольно много времени.
Наивно кажется, что это должно быть возможно, так как в глубине графа будет множество узлов, которые имеют идомы чуть выше и не затронуты изменениями в верхней части графа.
Кстати, в стороне: странно, что тема доминаторных деревьев «принадлежит» компиляторам, и об этом не упоминается в книгах по классической теории графов. Приложение, для которого я его использую - мой анализатор кучи Java FindRoots - не имеет отношения к теории компиляторов.
Уточнение: здесь я говорю о ориентированных графах. «Корень», о котором я говорю, на самом деле является узлом с наибольшей доступностью. Я обновил текст выше, заменив ссылки на «дерево» на «график». Я склонен думать о них как о деревьях, потому что форма в основном древовидная. График на самом деле представляет собой объекты в куче java, и, как вы понимаете, он достаточно иерархичен. Я обнаружил, что дерево доминаторов полезно при анализе утечек OOM, потому что вас интересует, "что поддерживает этот объект в живых?" и ответ, в конечном счете, - его господин. Деревья-доминаторы позволяют вам <ahem> видеть лес, а не деревья. Но иногда много мусора всплывает на вершину дерева, поэтому у вас есть корень с тысячами дочерних элементов прямо под ним. В таких случаях я хотел бы поэкспериментировать с вычислением деревьев доминаторов, укорененных в каждом из прямых потомков (в исходном графе) корня, а затем, возможно, перейти на следующий уровень ниже и так далее. (Стараюсь пока не беспокоиться о возможности обратных ссылок :)
Ответы 4
Судя по отсутствию комментариев, я полагаю, что в Stackoverflow не так много людей с соответствующим опытом, которые могли бы вам помочь. Я один из таких людей, но я не хочу, чтобы такой интересный вопрос звучал глухим стуком, поэтому я постараюсь протянуть руку помощи.
Моя первая мысль заключается в том, что если этот график создается другими компиляторами, стоит ли взглянуть на компилятор с открытым исходным кодом, такой как GCC, чтобы увидеть, как он решает эту проблему?
Моя вторая мысль заключается в том, что основной смысл вашего вопроса, похоже, заключается в том, чтобы избежать пересчета результата для корня дерева.
Я бы создал оболочку вокруг каждого узла, которая содержит сам узел и любые предварительно вычисленные данные, связанные с этим узлом. Затем новое дерево будет реконструировано из старого дерева рекурсивно с использованием этих классов-оболочек. Строя это дерево, вы начинаете с корня и продвигаетесь к листовым узлам. Для каждого узла вы должны сохранить результат вычислений для всех предков на данный момент. Таким образом, вам нужно будет смотреть только на родительский узел и данные текущего узла, которые вы обрабатываете, чтобы вычислить значение для вашего нового узла.
Надеюсь, это поможет!
Не могли бы вы уточнить, с какого типа графа вы начинаете? Я не понимаю, как есть разница между графом, который является деревом, и деревом доминаторов этого графа. Родитель каждого узла должен быть его идомом, и над ним, конечно же, будет доминировать все, что находится над ним в дереве.
Я не совсем понимаю ваш вопрос, но мне кажется, что вы хотите иметь некоторую функцию инкрементного обновления. Некоторое время назад я исследовал, какие у них алгоритмы, но мне показалось, что для больших графов нет известного способа сделать это быстро (по крайней мере, с теоретической точки зрения).
Вы можете просто выполнить поиск по запросу «дерево доминирования инкрементных обновлений», чтобы найти некоторые ссылки.
Думаю, вы знаете, что анализатор памяти Eclipse действительно использует деревья доминаторов, поэтому эта тема больше не полностью "принадлежит" сообществу компиляторов :)
Спасибо, Саймон. К сожалению, алгоритм чертовски сложен (по крайней мере, на мой взгляд) и не делает ничего такого простого, как простой рекурсивный спуск по дереву. Например, он следует цепочкам предков. Взгляните на это, чтобы почувствовать: cl.cam.ac.uk/~mr10/lengtarj.pdf.