Recherche de la hauteur de tous les nœuds d'une forêt

J'ai une forêt, c'est-à-dire des nœuds avec des bords dirigés et aucun cycle (dirigé ou non). Je définis la hauteur d'un sommet$v$ comme 0 s'il n'a pas d'arêtes entrantes, ou le nombre maximum d'arêtes à parcourir en sens inverse pour atteindre un sommet de hauteur 0.

Je sais également que le degré moyen d'un nœud est une petite constante, disons environ 2. Pour trouver la hauteur de tous les sommets, je peux penser à deux algorithmes:

Algorithme de marche

1. Parcourez et marquez $h=0$ pour les sommets sans arêtes entrantes.
2. Pour chaque sommet avec $h=0$, suivez les bords sortants, en mettant à jour la hauteur de chaque sommet rencontré si sa hauteur précédente est plus petite.

Algorithme de frontière

1. Parcourez et marquez $h=0$ pour les sommets sans arêtes entrantes, et marquez-les comme frontière.
2. Pour chaque sommet de frontière, voyez si son parent a des enfants à la frontière ou en dessous. Si c'est le cas, marquez le parent comme ayant $1$plus la plus grande hauteur parmi ses enfants. Marquez le parent comme étant à la frontière.
3. Répétez 2 jusqu'à ce qu'il n'y ait rien au-delà de la frontière.

Mes questions:

1. Y a-t-il un nom pour ce problème et une solution la plus rapide bien connue?
2. J'ai tendance à penser simplement en remontant de toutes les $h=0$vertices est la solution la plus rapide. Ai-je raison?

Tout d'abord, cela dépend un peu de la façon dont vous pouvez accéder à vos données pour dire quels algorithmes fonctionnent le mieux.

Quoi qu'il en soit, je suggère de déterminer les hauteurs de manière descendante plutôt que de bas en haut. Personnellement, je pense qu'une approche descendante est conceptuellement plus agréable et plus facile à analyser. Pour tout sommet$v$ dans la forêt il est vrai que

Vous pouvez donc rechercher toutes les racines, puis déterminer les hauteurs en divisant une conquête. Vous toucherez chaque sommet au maximum deux fois (recherche des racines + traversée). Dans l'approche que vous avez suggérée, vous devrez peut-être toucher plusieurs fois certains sommets.

Btw, puisque vous avez une forêt, vous avez moins d'arêtes que de sommets, donc vous savez que vous avez un degré moyen inférieur à deux (et donc vous pouvez tester les racines en temps linéaire).

Je ne sais pas si ce problème a un nom officiel ou non. Votre titre résume assez bien. Monter à partir des nœuds de hauteur 0 sera rapide, à condition de prendre soin d'éviter les travaux en double. Supposons que vous ayez un nœud avec de nombreux enfants et un long chemin au-dessus de ce nœud jusqu'à la racine. Supposons également que les hauteurs de chacun des enfants soient différentes. Chaque enfant peut mettre à jour la hauteur du nœud en question. C'est bon. Mais vous devez également éviter de mettre à jour le long chemin au-dessus de ce nœud jusqu'à ce que tous ses enfants aient signalé leurs hauteurs.

L'algorithme résultant s'exécutera en temps linéaire et le pseudo-code ressemblerait à ceci:

initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q

Un problème si similaire qu'il pourrait être intéressant est «Préfixe parallèle sur les arbres dirigés enracinés». L'algorithme trouve le nombre d'arêtes à la racine de chaque nœud. Ainsi, les racines se retrouvent avec la valeur 0, tandis que par exemple le nœud en bas à droite se retrouverait avec une valeur de deux.

Notez que l'algorithme ci-dessous résout le problème plus général des bords pondérés, mais vous pouvez simplement initialiser le W (i) à 1 pour tout i. Et le successeur de chaque nœud i est donné par P (i) = j.

for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

L'image ci-dessous illustre la "réduction de moitié" des longueurs de trajet et rend le temps d'exécution logarithmique facile à comprendre. Il ne montre cependant pas les hauteurs de nœud calculées.

(extrait de "Introduction to Parallel Algorithms" de Joseph Jaja).

Utilisant plusieurs processeurs, il est résoluble en temps O (lg n), mais utilise des opérations O (n lg n). Il existe un hack pour le ramener au travail linéaire, mais il est légèrement impliqué.