algorithms algorithm graph-theory compiler-theory

algorithms - dfs graph algorithm



¿Manera eficiente de calcular recursivamente el árbol dominador? (4)

¿Podría explicar en qué tipo de gráfico está empezando? No veo cómo hay 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á sobre él en el árbol.

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 tengo que admitir que no me he tomado el tiempo para entenderlo completamente, solo lo estoy usando. Ahora tengo la necesidad de calcular los árboles dominantes de los hijos directos del nodo raíz y posiblemente recidivar en el gráfico hasta cierta profundidad repitiendo esta operación. Es decir, cuando calculo el árbol dominador para un hijo del nodo raíz, quiero pretender 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 de dominación inmediata ya calculada en el árbol 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.

Ingenuamente, parece que debe ser posible, ya que habrá muchos nodos en el fondo del gráfico que tendrán idoms un poco por encima de ellos y no se verán afectados por los cambios en la parte superior del gráfico.

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

Aclaración: estoy hablando de gráficos dirigidos aquí. La "raíz" a la que me refiero es en realidad el nodo con la mayor accesibilidad. He actualizado el texto anterior reemplazando las referencias a "árbol" por "gráfico". Tiendo a pensar en ellos como árboles porque la forma es principalmente de árbol. El gráfico es en realidad de los objetos en un montón de Java y, como se puede imaginar, es razonablemente jerárquico. He encontrado el árbol dominador ú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 Dominator te permiten <ahem> ver la madera en lugar de los árboles. Pero a veces, una gran cantidad de basura flota en la parte superior del árbol, por lo que tienes una raíz con miles de niños directamente debajo de ella. Para tales casos, me gustaría experimentar con el cálculo de los árboles dominantes enraizados en cada uno de los niños directos (en el gráfico original) de la raíz y luego tal vez pasar al siguiente nivel y así sucesivamente. (Estoy tratando de no preocuparme por la posibilidad de volver enlaces por el momento :)

A juzgar por la falta de comentarios, creo que no hay mucha gente en con la experiencia relevante para ayudarlo. Soy una de esas personas, pero no quiero que una pregunta tan interesante fracase con un golpe 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 se resuelve este problema?

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

Lo que haría sería crear un contenedor alrededor de cada nodo que contenga el nodo en sí y cualquier información precomputada asociada con ese nodo. A continuación, se reconstruiría un árbol nuevo a partir del árbol viejo recursivamente utilizando estas clases de envoltura. A medida que construyas este árbol, comenzarías en la raíz y llegarás a los nodos de las hojas. Para cada nodo, almacenarías el resultado del cálculo de todos los ancestros hasta el momento. De esta forma, solo deberá 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!

No entiendo completamente tu pregunta, pero me parece que quieres tener alguna característica de actualización incremental. Investigué hace un tiempo qué algoritmos son suyos, pero me pareció que no hay forma conocida para que los gráficos grandes lo hagan rápidamente (al menos desde un punto de vista teórico).

Puede buscar "actualizaciones dominator tree" para encontrar algunas referencias.

Supongo que sabe que el Eclipse Memory Analyzer utiliza árboles dominator, por lo que este tema ya no es "propiedad" de la comunidad de compiladores :)