estoy usando el algoritmo Lengauer y Tarjan con la compresión de ruta para calcular el árbol dominador de 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 ha sido eliminado del gráfico.¿Manera eficiente de calcular recursivamente el árbol dominador?
Mi pregunta es si existe una solución eficaz a este que hace uso de la información dominador inmediata ya calculado 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.
Naively 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.
cierto al igual que a un lado: es extraño que el tema de los árboles de dominación es "propiedad" de la gente del compilador y no hay ninguna mención de ella en los libros sobre la teoría de grafos clásico. 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 árbol similar. 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. árboles Dominator le permiten <ejem> ve 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 enlaces de regreso por el momento :)
Sí, eso puede ayudar, gracias. Me preocupa la otra parte del algoritmo, que generalmente toma el mismo orden de tiempo que el dfs pero a veces es peor (y es por eso que definitivamente necesitas la compresión del camino). –