# Un algorithme de recherche des prédominateurs dans un graphe orienté

Laurent Hyafil

► To cite this version:

Laurent Hyafil. Un algorithme de recherche des prédominateurs dans un graphe orienté. [Rapport de recherche] IRIA-RR-008, IRIA. 1973, pp.7. hal-04715940

HAL Id: hal-04715940

https://inria.hal.science/hal-04715940v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Tél. 01964

RR8

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

# Un algorithme de recherche des prédominateurs dans un graphe orienté

Laurent Hyafil

<figure><img src="image_2.png" /></figure>

Rapport de Recherche n° 8

février 1973
# UN ALGORITHME DE RECHERCHE DES PRÉDOMINATEURS DANS UN GRAPHE ORIENTÉ

L. Hyafil

(présenté par J. Vuillemin)

## Résumé :

Lowry et Medlock [1] ont introduit la notion de prédominateur pour optimiser le code généré par un compilateur. Purdom et Moore [3] ont proposé un algorithme de recherche des prédominateurs dont le temps de calcul est de l'ordre de $O(n)$ (n nombre de noeuds, s nombre d'arêtes) donc $O(n^3)$ dans le pire des cas.

L'algorithme que nous proposons ici recherche les prédominateurs dans un graphe en un temps proportionnel au temps nécessaire pour multiplier deux matrices booléennes n x n (actuellement $O(n^\alpha)$ avec $\alpha = \log_2 7 \approx 2,81$, grâce à la méthode de Strassen [4]).
## Introduction

Si G est un graphe orienté dont les noeuds sont numérotés de 1 à n (les arêtes de ce graphe représentent le cheminement du contrôle entre les blocs d'un programme, la première instruction du programme correspondant au noeud numéroté 1), nous dirons que le noeud p prédomine le noeud q si et seulement si, tous les chemins de 1 à q passent par p.

L'algorithme que nous proposons s'inspire de la méthode employée par Munro [2] pour chercher la fermeture transitive d'un graphe. L'idée est de couper le graphe en deux et de résoudre le problème pour chacun des deux sous-graphes. Ceci fait, une solution au problème posé est construite en utilisant un nombre fini de produits de matrices et de recherches de fermetures transitives.

## Justification de l'algorithme

Soit A un arbre extrait du graphe G, ayant pour sommet le noeud 1 et contenant tous les noeuds du graphe qui peuvent être atteints depuis le noeud 1 (les autres noeuds du graphe G sont supprimés). Les noeuds de G peuvent être renumérotés de façon que $p < q$ implique qu'il n'existe pas de chemin sur A qui aille de q vers p.

Soit $G_1$ (resp. $G_2$) le sous graphe de G contenant tous les points de 1 à $\lfloor n/2 \rfloor$ (resp. $\lfloor n/2 \rfloor + 1$ à n).

La numérotation que nous avons faite à partir de A implique que les prédominateurs des noeuds de $G_1$ sont dans $G_1$.

Construisons un graphe $G'_2$ en ajoutant à $G_2$ un noeud s et une arête (s,y) pour tout $y \in G_2$ chaque fois qu'il existe dans G une arête (x,y) (avec $x \in G_1$).
**Proposition 1 :**

Un noeud $p \in G_2$ prédomine dans $G$ un noeud $q \in G_2$ si seulement si, le noeud $p$ prédomine le noeud $q$ dans $G'_2$ en prenant s comme noeud d'entrée.

**Preuve**

Soit $p \in G_2$ un prédominateur de $q \in G_2$ dans $G$. Supposons qu'il existe dans $G'_2$ un chemin $C$ de $s$ vers $q$ qui ne passe pas par $p$. A sa première arête $(s,y)$ correspond dans $G$ une arête $(x,y)$ (avec $x \in G'_1$, $y \in G_2$). Le chemin constitué par $<C>$ le chemin de $l$ vers $x$ sur $A$, $l$-arête $(x,y)$, le chemin de $y$ vers $q$ sur $C$ ne passe pas par $p$ ce qui est contraire à l'hypothèse.

Réciproquement, si $p$ prédomine $q$ dans $G'_2$ et si il existe dans $G$ un chemin $C$ qui ne passe pas par $p$, il existe une dernière arête $(x,y)$ de $C$ avec $x \in G'_1$ et $y \in G_2$. Le chemin $C'$ de $y$ vers $q$ sur $C$ est contenu dans $G_2$ et ne passe pas par $p$. Alors le chemin $(<C, C')$ ne passe pas par $p$ ce qui est contraire à l'hypothèse. ■

Pour tout $y$ appartenant à $G_2$ nous appelons $P(y)$ un ensemble de noeuds $x \in G'_1$ tels qu'il existe un $z \in G_2$, une arête $(x,z)$ et un chemin dans $G_2$ de $z$ vers $y$.

**Proposition 2 :**

Un noeud $p \in G'_1$ prédomine un noeud $q \in G_2$ si et seulement si $p$ prédomine tous les noeuds de $P(q)$.

**Preuve**

Un chemin de $l$ vers $q \in G_2$ qui ne passe pas par $p \in G'_1$ contient un chemin de $l$ vers $x$ avec $x \in P(q)$ qui ne passe pas par $p$. Donc si $p$ ne prédomine pas $q$, il ne prédomine pas tous les noeuds de $P(q)$.
Réciproquement, soit $p \in G_1$ prédominant $q \in G_2$. Si $p$ ne prédominait pas $y$ avec $y \in P(q)$, il existerait un chemin de $1$ vers $y$ ne passant pas par $p$ ; mais ceci est impossible puisqu'il existe un chemin de $y$ vers $q$ qui ne passe pas par $p$. ■

## Description de l'algorithme

La première étape de notre algorithme consiste à extraire l'arbre $A$ et à renuméroter les sommets de $G$. Nous séparons alors le graphe en deux sous graphes $G_1$ et $G_2$ et nous construisons $G'_2$.

Par récurrence nous pouvons ensuite calculer les prédominateurs de $G_1$ et de $G'_2$. Il ne reste plus qu'à trouver les prédominateurs de $G_2$ qui sont dans $G_1$.

Supposons que le graphe $G$, renuméroté en suivant $A$ soit représenté par la matrice booléenne $M$

$$M = \begin{pmatrix} C & D \\ E & F \end{pmatrix}$$

où $C$ [resp: $F$] est la sous matrice carrée correspondant au graphe $G_1$ [resp. $G_2$]. Les sous matrices $E$ et $D$ représentent les connections entre $G_1$ et $G_2$.

Pour toute matrice $X$, désignons par $X^*$ la matrice dont les éléments $x_{ij}$ sont égaux à 1 si et seulement si $j$ prédomine $i$ dans le graphe décrit par $X$.

Nous avons alors

$$M^* = \begin{pmatrix} C^* & S \\ P & F'^* \end{pmatrix}$$

Remarquons que $S$ est nulle puisque les prédominateurs de $G_1$ sont dans $G_1$. La matrice $C^*$ a été calculée par récurrence à partir de $C$. La matrice $F'^*$ se déduit de la matrice $G'_2^*$ du graphe $G'_2$ en retirant la première ligne et la première colonne (Proposition 1).
L'algorithme de Munro [2] permet de calculer $\tilde{F}$ fermeture transitive de F. Calculons alors $Q = D \boxplus \tilde{F}$ où $\boxplus$ représente le produit booléen de matrices. L'élément $q_{ij}$ de Q vaut 1 si et seulement si $i \in P(j+\lfloor \frac{n}{2} \rfloor)$ par définition de P(x). Calculons $R = tQ \boxplus \overline{C^*}$ (où t représente la transposition et — la complémentation booléenne). Alors l'élément $r_{ij}$ de R est nul si et seulement si j est prédominateur de tous les points de $p(i+\lfloor \frac{n}{2} \rfloor)$ donc de $i+\lfloor \frac{n}{2} \rfloor$ (Proposition 2). Nous pouvons alors calculer $P = \overline{R}$.

## Estimation du temps de calcul

Soit $f(n)$ le temps nécessaire pour rechercher les prédominateurs d'une matrice $n \times n$. On a

$$f(n) \le k_1 n^2 + f(\frac{n}{2}) + f(\frac{n}{2}+1) + k_2 (\frac{n}{2})^\alpha + 2k_3 (\frac{n}{2})^\alpha + 2k_4 n^2$$
où $k_1, k_2, k_3, k_4$ sont des constantes dépendant de la machine utilisée.

En effet, le temps nécessaire pour la recherche et la rénumérotation de l'arbre est $O(n^2)$ ; pour un produit de matrice ou une fermeture transitive ce temps est de $O(n^\alpha)$ en utilisant les méthodes indiquées et une complémentation se fait en $O(n^2)$.

Il est alors aisé d'en déduire que $f(n) = O(n^\alpha)$ ce qui réduit donc la complexité du calcul des prédominateurs à celle du calcul d'un nombre fixe de produits de matrices.
Remerciements
---

L'auteur remercie Joël Coffy et Jean Vuillemin pour leur aide
au cours de ce travail.

Bibliographie
---

[1] LOWRY, E.S. and MEDLOCK, C.W. "Objet Code Optimization" Comm. ACM 12,1 (Jan 1969), 13-22.

[2] MUNRO, J.I. "Some Results in the Study of Algorithms" Technical report n° 32 October,1971 University of Toronto.

[3] PURDOM, P.W. and MOORE E.F. "Immediate predominators in a directed graph" Comm. ACM 15,8 (Aug. 1972)

[4] STRASSEN, V. "Gaussian Elimination is not Optimal" Numer. Math. 13, 354-356 (1969).