Un moyen efficace de calculer récursivement l'arbre dominateur?

Question

J'utilise l'algorithme de Lengauer et Tarjan avec compression de chemin pour calculer l'arbre dominateur pour un graphe où il y a des millions de nœuds. L'algorithme est assez complexe et je dois admettre que je n'ai pas pris le temps de bien le comprendre, je l'utilise juste. Maintenant, j'ai besoin de calculer les arbres dominateurs des enfants directs du nœud racine et éventuellement recurrencer le graphique à une certaine profondeur en répétant cette opération. C'est à dire. Quand je calcule l'arbre dominateur pour un enfant du nœud racine, je veux prétendre que le nœud racine a été retiré du graphique.

Ma question est de savoir s'il existe une solution efficace qui utilise des informations dominantes immédiates déjà calculées dans l'arbre dominateur initial pour le nœud racine? En d'autres termes, je ne veux pas partir de zéro pour chacun des enfants parce que tout le processus prend beaucoup de temps. Naïvement, il semble que cela doit être possible car il y aura beaucoup de nœuds en profondeur dans le graphique qui ont des idoms juste un peu au-dessus d'eux et ne sont pas affectés par les changements en haut du graphique.

BTW à part: il est bizarre que le sujet des arbres dominateurs soit "détenu" par les compilateurs et il n'y a aucune mention de cela dans les livres sur la théorie classique des graphes. L'application pour laquelle je l'utilise - mon analyseur de tas java FindRoots - n'est pas liée à la théorie du compilateur. Clarification: Je parle de graphiques dirigés ici. La "racine" à laquelle je me réfère est en fait le nœud ayant la plus grande accessibilité. J'ai mis à jour le texte ci-dessus en remplaçant les références à "arbre" par "graphique". J'ai tendance à penser à eux comme des arbres parce que la forme est principalement comme des arbres. Le graphique est en fait des objets dans un tas Java et comme vous pouvez l'imaginer est raisonnablement hiérarchique. J'ai trouvé l'arbre dominateur utile lors de l'analyse des fuites du MOO, car ce qui vous intéresse est "qu'est-ce qui maintient cet objet en vie?" et la réponse est finalement son dominateur. Dominator arbres vous permettent de voir le bois plutôt que les arbres. Mais parfois, beaucoup de jonques flottent au sommet de l'arbre, de sorte que vous avez une racine avec des milliers d'enfants directement en dessous. Pour de tels cas, je voudrais expérimenter avec le calcul des arbres dominateurs enracinés à chacun des enfants directs (dans le graphe original) de la racine et puis peut-être aller au niveau suivant et ainsi de suite. (J'essaie de ne pas m'inquiéter de la possibilité de liens de retour pour l'instant :)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs pourrait aider.

Answer 2

A en juger par l'absence de commentaires, je suppose qu'il n'y a pas beaucoup de gens sur Stackoverflow avec l'expérience pertinente pour vous aider. Je fais partie de ces gens, mais je ne veux pas qu'une question aussi intéressante soit entendue avec un bruit sourd, alors je vais essayer de donner un coup de main. Ma première pensée est que si ce graphique est généré par d'autres compilateurs, cela vaut-il la peine de regarder un compilateur open-source, comme GCC, pour voir comment il résout ce problème? Ma deuxième pensée est que le point principal de votre question semble être d'éviter de recalculer le résultat pour la racine de l'arbre.

Ce que je voudrais faire est de créer un wrapper autour de chaque noeud qui contient le noeud lui-même et toutes les données précalculées associées à ce noeud. Un nouvel arbre serait ensuite reconstruit à partir de l'ancien arbre de manière récursive en utilisant ces classes wrapper. Lorsque vous construisez cet arbre, vous commencez à la racine et vous vous frayez un chemin vers les nœuds feuilles. Pour chaque nœud, vous stockez le résultat du calcul pour tous les ancêtres jusqu'à présent. De cette façon, vous devriez seulement avoir à regarder le nœud parent et les données de nœud actuelles que vous traitez pour calculer la valeur de votre nouveau nœud.

J'espère que cela aide!

Answer 3

Pourriez-vous élaborer sur quel genre de graphique vous commencez? Je ne vois pas comment il y a une différence entre un graphe qui est un arbre et l'arbre dominateur de ce graphe. Le parent de chaque nœud devrait être son idom, et il serait bien sûr dominé par tout ce qui se trouve au-dessus dans l'arbre.

Answer 4

Je ne comprends pas complètement votre question, mais il me semble que vous voulez avoir une fonction de mise à jour incrémentielle. J'ai fait des recherches il y a quelques temps sur les algorithmes, mais il me semblait qu'il n'y avait pas de moyen connu pour que les grands graphes le fassent rapidement (du moins d'un point de vue théorique).

Il se peut que vous cherchiez simplement "incrémental updates dominator tree" pour trouver des références.

Je suppose que vous êtes au courant the Eclipse Memory Analyzer utilise-t-arbres Dominator, donc ce sujet n'est pas complètement « possédée » par la communauté du compilateur plus :)