¿Manera eficiente de calcular recursivamente el árbol dominador?

Question

Estoy usando el algoritmo de Lengauer y Tarjan con compresión de ruta para calcular el árbol dominador para un gráfico donde hay millones de nodos. El algoritmo es bastante complejo y debo admitir que no me he tomado el tiempo para entenderlo completamente, solo lo estoy usando. Ahora tengo la necesidad de calcular los árboles dominadores de los hijos directos del nodo raíz y, posiblemente, repetir el gráfico hasta una cierta profundidad repitiendo esta operación. Es decir. cuando calculo el árbol dominador para un hijo del nodo raíz, quiero fingir que el nodo raíz se ha eliminado del gráfico.

Mi pregunta es si existe una solución eficiente para esto que haga uso de la información del dominador inmediato ya calculada en el árbol del dominador inicial para el nodo raíz. En otras palabras, no quiero comenzar desde cero para cada uno de los niños porque todo el proceso lleva bastante tiempo.

Parece ingenuo que debe ser posible ya que habrá muchos nodos en el fondo del gráfico que tienen idoms un poco más arriba y no se ven afectados por los cambios en la parte superior del gráfico.

Por cierto, aparte de eso: es extraño que el tema de los árboles dominantes sea " propiedad de " por personas compiladoras y no se menciona en los libros sobre teoría clásica de gráficos. La aplicación para la que lo estoy usando, mi analizador de montón de Java FindRoots, no está relacionada con la teoría del compilador.

Aclaración: estoy hablando de gráficos dirigidos aquí. El & Quot; raíz & Quot; Me refiero a que en realidad es el nodo con la mayor accesibilidad. He actualizado el texto anterior reemplazando las referencias a & Quot; tree & Quot; con " gráfico " ;. Tiendo a pensar en ellos como árboles porque la forma es principalmente similar a un árbol. El gráfico es en realidad de los objetos en un montón de Java y, como puede imaginar, es razonablemente jerárquico. He encontrado que el árbol dominador es útil al hacer análisis de fugas OOM porque lo que le interesa es & "; ¿Qué mantiene vivo este objeto? &"; y la respuesta en última instancia es su dominador. Los árboles de dominador le permiten & Lt; ejem & Gt; ver el bosque en lugar de los árboles. Pero a veces, mucha basura flota hasta la parte superior del árbol, por lo que tiene una raíz con miles de niños directamente debajo. Para tales casos, me gustaría experimentar con el cálculo de los árboles dominadores enraizados en cada uno de los hijos directos (en el gráfico original) de la raíz y luego tal vez pasar al siguiente nivel hacia abajo y así sucesivamente. (Estoy tratando de no preocuparme por la posibilidad de enlaces de retroceso por el momento :)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs podría ayudar.

Answer 2

A juzgar por la falta de comentarios, supongo que no hay mucha gente en Stackoverflow con la experiencia relevante para ayudarlo. Soy una de esas personas, pero no quiero que se haga una pregunta tan interesante con un ruido sordo, así que intentaré echar una mano.

Mi primer pensamiento es que si este gráfico es generado por otros compiladores, ¿valdría la pena echar un vistazo a un compilador de código abierto, como GCC, para ver cómo resuelve este problema?

Mi segundo pensamiento es que, el punto principal de su pregunta parece ser evitar volver a calcular el resultado para la raíz del árbol.

Lo que haría es crear un contenedor alrededor de cada nodo que contenga el nodo en sí y cualquier dato precalculado asociado con ese nodo. Luego se reconstruiría un árbol nuevo a partir del árbol viejo de forma recursiva utilizando estas clases de contenedor. A medida que construyes este árbol, comenzarías desde la raíz y llegarías a los nodos de hoja. Para cada nodo, almacenaría el resultado del cálculo para todos los ancestros hasta el momento. De esa manera, solo debería tener que mirar el nodo principal y los datos del nodo actual que está procesando para calcular el valor de su nuevo nodo.

¡Espero que eso ayude!

Answer 3

¿Podría explicar en qué tipo de gráfico está comenzando? No veo cómo hay alguna diferencia entre un gráfico que es un árbol y el árbol dominador de ese gráfico. El padre de cada nodo debería ser su idom y, por supuesto, estaría dominado por todo lo que está arriba en el árbol.

Answer 4

No entiendo completamente su pregunta, pero me parece que desea tener alguna función de actualización incremental. Investigué hace un tiempo qué algoritmos son, pero me pareció que no hay una forma conocida de gráficos grandes para hacer esto rápidamente (al menos desde un punto de vista teórico).

Puede buscar " actualizaciones incrementales del árbol dominador " para encontrar algunas referencias

Supongo que sabe que el analizador de memoria Eclipse usa árboles dominadores, por lo que este tema es no completamente " propiedad de " por la comunidad del compilador :) :)