Algorithmes de normalisation d'un système

Chapter 9

Algorithmes de normalisation d'un système

Quelle que soit la politique de normalisation choisie (i.e. globale ou par profondeurs) le problème central reste le même. À savoir transformer une récurrence définie par plusieurs équations (ou clauses) en une récurrence définie par une seule équation (ou clause). Seuls deux outils sont autorisés : la substitution et la fusion. La fusion n'est utilisée qu'en dernier ressort quand la normalisation par substitutions échoue. Par la suite un système qui peut être transformé, à l'aide de substitutions, en un système normalisé sera appelé système normalisable.

Ce chapitre utilise quelques notions de la théorie des graphes. Nous avons adopté le vocabulaire de C. Berge [8], en particulier la notion de circuit qui représente un cycle dont toutes les arcs sont orientés dans le même sens (i.e. l'extrémité terminale de chaque arc correspond à l'extremité initiale de l'arc suivant). Un cas particulier de circuit est la boucle qui ne comporte qu'un seul arc donc qu'un seul sommet. Berge définit aussi la notion de base de circuits : tout circuit d'un graphe peut être construit par addition et soustraction des circuits de la base (additionner deux graphes revient à faire l'union des arcs des deux graphes, soustraire deux graphes revient à faire la différence entre les arcs des deux graphes).

9.1

Une approche par la théorie des graphes

Considérons le problème de la normalisation du point de vue de la théorie des graphes, i.e. raisonnons sur le graphe du système. Si la normalisation se fait à la profondeur p seuls les arcs représentant une référence de pseudo-profondeur supérieure ou égale à p seront représentés. Notre but est d'appliquer des substitutions au système de telle manière que le graphe du système résultant n'ait d'autre circuit que des boucles. Sur un graphe, une substitution consiste à supprimer un certain nombre q d'arcs sortant d'un sommet donné v₀ et à ajouter les prédécesseurs de v₀ aux sommets destinations des arcs sortants (voir la figure ci-dessous).

Les sommets (v_i)_iÎ_N_{_q}^_* du nouveau graphe ont un nombre de prédécesseurs k'_i non connu a priori. En effet il peut y avoir des prédécesseurs communs à v₀ et à un v_i (i³ 1) dans le graphe initial. Donc k'_i est compris entre max(k₀,k_i) et k₀+k_i. Cette modélisation de la substitution est appelée substitution de graphe. Par analogie avec un système d'équations, un graphe sera dit normalisable si, à l'aide de substitutions de graphe, il est possible de le transformer en un graphe dont les seuls circuits sont des boucles. La modélisation montre bien qu'il est inutile d'effectuer une substitution si la source (v₀) porte une boucle. Dans ce cas de figure, les (v_i)_iÎ_N_{_q}^_* ont forcément v₀ comme prédécesseur dans le graphe final et aucun des arcs sortant de la source n'est coupé.

Cette modélisation de la substitution n'est pas tout à fait exacte. Prenons d'abord le cas où le graphe des équations a été choisi comme graphe représentatif du système. La modélisation suppose que tout prédécesseur de v₀ dans le graphe initial est un prédécesseur des (v_i)_iÎ_N_{_q}^_* dans le graphe final. Or, lors d'une substitution, certaines des nouvelles clauses créées peuvent avoir un domaine de définition vide (voir section 7.3). Ce qui signifie que certaines références de la source n'apparaissent pas dans la destination. Donc en toute rigueur, seul un sous-ensemble des prédécesseurs de v₀ devrait être ajouté à un v_i (i³ 1) donné. Comme il est impossible de déterminer ce sous-ensemble au niveau du graphe, nous nous contentons d'une modélisation approximative (il s'agit, en fait, de la modélisation de la substitution sans simplification des domaines de définition). L'approximation est conservative dans le sens où elle conduit à déclarer non-normalisables des systèmes qui le sont mais ne conduit pas à déclarer normalisable des systèmes qui ne le sont pas. Dans le cas où c'est le graphe des clauses qui représente le système, l'approximation est encore plus sévère. En effet dans ce graphe une substitution a généralement pour effet d'augmenter le nombre des sommets (voir 7.3.2). Or la modélisation travaille avec un nombre constant de sommets. Cette modélisation peut tout de même s'appliquer, il suffit de considérer qu'après chaque substitution sur le graphe un sommet v_i ne représente plus une clause mais l'ensemble des clauses issues du v_i initial. Là encore l'approximation est conservative.

Preuve:: Si le graphe est normalisable il est possible d'obtenir, par une série s de substitutions de graphe, un graphe dont les seuls circuits sont des boucles. Le graphe final G_f n'est pas exactement le graphe des clauses du système correspondant (i.e. obtenu par une série de substitutions de clause équivalente à s) car un sommet correspond à plusieurs clauses. Une boucle dans ce graphe peut donc correspondre à un circuit dans le vrai graphe des clauses. Heureusement, il s'agit d'un circuit entre clauses issues d'une même autre clause. Ces clauses définissent la même variable du système et donc les auto-références sont explicites. Il est donc valide de détecter les récurrences par simple examen des expressions des clauses si le graphe final G_f n'a que des boucles pour circuits.

L'approximation vient du fait qu'un sommet peut représenter un ensemble de clauses. Un circuit dans ce type de graphe peut être fictif comme montré sur la figure ci-dessous :

La normalisation basée sur le graphe des clauses reste plus précise que celle basée sur le graphe des équations même avec cette modélisation de la substitution. En effet le graphe de départ contient moins de circuits dans le premier cas que dans le second.

9.2

Critère pour reconnaître un graphe normalisable

Pour simplifier le problème, il suffit de remarquer qu'un graphe est normalisable ssi toutes ses composantes fortement connexes sont normalisables. Dans ce contexte, un critère pour reconnaître un graphe normalisable est de vérifier s'il existe un sommet commun à tous les circuits. Les théorèmes suivants montrent qu'il s'agit d'une condition suffisante et nécessaire.

Théorème 1 Critère de normalisation -- condition suffisante
Si tous les circuits d'un graphe fortement connexe ont au moins un sommet commun alors le graphe est normalisable.

Preuve:

Montrons que si un tel sommet v₀ existe alors le graphe est normalisable. Supprimons les arcs sortants de ce sommet, le graphe G devient un graphe G' acyclique. Il est possible d'effectuer un tri topologique sur G' qui classe les sommets de G' (donc ceux de G) suivant les ensembles ( E_i)_iÎ_N_{_s}^_*. Le dernier ensemble E_s ne contient qu'un sommet, v₀. Tous les sommets du premier ensemble E₁ n'ont qu'un seul prédécesseur, v₀. Ceci implique que :

ces sommets ne portent pas de boucles, donc, par substitution dans leurs successeurs, tous leurs arcs sortants sont supprimés ;
après les substitutions, les sommets de E₂ n'ont que v₀ comme prédécesseur.

L'étape de substitution peut être répétée pour chaque ensemble E_i, jusqu'à i=s. À ce point, plus aucun circuit ne peut passer par un sommet autre que v₀ (car ces sommets n'ont plus d'arc sortant). Un résultat annexe est que le seul prédécesseur de v₀ est lui même ; ce sommet porte donc obligatoirement une boucle.

Théorème 2 Critère de normalisation -- condition nécessaire
Un graphe fortement connexe est normalisable seulement si tous ses circuits ont au moins un sommet commun.

Preuve:

Le principe de la preuve est le suivant : nous partons d'un graphe G fortement connexe et tel que pour tout sommet v il comporte au moins un circuit n'incluant pas v. Nous montrons qu'un graphe G' obtenu à partir de G par l'application de substitutions simultanées inclut forcément une composante fortement connexe possédant les mêmes propriétés que G. Cette propriété est donc transitive. De plus une composante fortement connexe comportant pour chacun de ses sommets un circuit n'incluant pas le sommet en question est constituée d'au moins deux sommets. Les graphes obtenus par substitutions ne seront donc jamais normalisés.

Pour rendre cette partie plus facile à lire, les différentes étapes de la démonstration sont données sous forme de lemmes illustrés par des schémas (les substitutions y sont matérialisées par des croix en pointillés sur les arcs qu'elles suppriment). Dans ces lemmes le graphe G représente un graphe fortement connexe et G' un graphe obtenu à partir de G par un nombre quelconque de substitutions simultanées.

Lemme 3 Conservation des chemins par substitutions

S'il existe un chemin dans G alors il existe dans G' un sous-chemin partant du premier (voir l'exemple avec 2 substitutions simultanées) ou du second sommet (voir l'exemple avec 4 substitutions simultanées) et aboutissant au dernier sommet.

Preuve:

Commençons par montrer que pour tout sommet v de G et pour tout prédécesseur v^- de v dans G alors, soit v^- est un prédécesseur de v dans G', soit les prédécesseurs de v^- dans G sont les prédécesseurs de v dans G'. En effet :

soit aucune substitution ne coupe l'arc (v^-,v) ;
soit l'arc (v^-,v) est coupé par la substitution de source v^- et de destination v. Dans ce cas les prédécesseurs de v^- dans G sont aussi des prédécesseurs de v dans G'.

Donc s'il existe un chemin µ=(v₁,v₂,...,v_p) dans G, il existe un chemin de v₁ ou de v₂ vers v_p dans G' n'empruntant que des sommets de µ (car tout sommet v_i a comme prédécesseur, dans G' restreint aux sommets de µ, soit v_i-1 soit v_i-2).

Corollaire 4 Conservation des circuits par substitutions

S'il existe un circuit dans G alors il existe au moins un circuit dans G' (dit circuit issu) ne comprenant que des sommets du circuit de G (le second exemple montre qu'il peut exister 2 circuits issus).

Preuve:: Considérons le circuit µ=(v₁,v₂,...,v_p) de G tel que v₁=v_p-1 et v₂=v_p. D'après le lemme 3, le graphe G' possède au moins un circuit constitué uniquement de sommets de µ. De plus, quel que soit le sommet v de µ, il existe dans G' un chemin d'un de ces nouveaux circuits vers v.

Lemme 5 Conservation des chemins inter-circuits par substitutions

Soit deux circuits µ₁ et µ₂ de G, pour chaque circuit µ₂' issu de µ₂ il existe un chemin d'un des circuits issus de µ₁ vers µ₂' (dans l'exemple il s'agit de µ₁').

Preuve:: Considérons deux circuits µ₁ et µ₂ de G. Comme ce graphe G est fortement connexe, il est toujours possible de trouver un chemin (v₁,v₂,...,v_p) avec v₁ et v₂ éléments de µ₁ et v_p élément de µ₂. D'après le corrolaire 4, il existe donc un chemin, dans G', de v₁ ou de v₂ vers v_p. De plus il existe un chemin, dans G', d'un des nouveaux circuits issus de µ₁, vers v₁ (de même pour v₂). En résumé, pour tout sommet v de µ₂, il existe un chemin, dans G', d'un des nouveaux circuits issu de µ₁ vers v. En particulier, pour tout nouveau circuit µ₂' issu de µ₂, il existe un chemin, dans G', d'un nouveau circuit issu de µ₁ vers µ₂'.

Lemme 6 Conservation des circuits dans les composantes fortement connexes

Il existe dans G' une composante fortement connexe comprenant, au moins, un des circuits issus de chaque circuit de G (dans ce schéma les circuits engendrés par le même circuit sont regroupés dans une ellipse en pointillés).

Preuve:: Construisons un nouveau graphe G_c dont chaque sommet est un circuit issu d'un circuit de G et dont les arcs sont les chemins entre ces circuits. Soit (V_i) la partition de l'ensemble des sommets de G_c telle que deux circuits sont dans un même V_i s'ils sont issus du même circuit de G. Chaque sommet de G_c a, au moins, un prédécesseur dans chaque V_i. Comme, de plus, le nombre de V_i est fini, il existe un circuit dans G_c incluant au moins un sommet de chaque V_i.

Les lemmes précédents suffisent pour achever la démonstration de la partie nécessaire du critère de normalisation. En particulier, ils permettent d'affirmer que pour tout sommet v de la composante fortement connexe C de G' (obtenue par le lemme 6), il existe au moins un circuit de cette composante ne comprenant pas v. En effet, puisque v est absent d'au moins un des circuits µ de la composante fortement connexe de G, il l'est, a fortiori, du circuit engendré par µ et inclus dans C. Le schéma suivant illustre ce résultat.

Dans cet exemple v est forcement absent de µ' car ce circuit est issu de µ qui ne le contient pas.

En conclusion, si dans G tous les circuits ne possèdent pas un sommet commun, alors tout graphe dérivé de G par des substitutions possède une composante fortement connexe dont les circuits ont la même propriété. Comme une telle composante a au moins deux sommets reliés par un circuit (voir l'exemple ci-dessous), la composante possède au moins un circuit qui n'est pas une boucle.

Le graphe G n'est pas normalisable.

Ce résultat formalise un fait intuitif : les récurrences ne peuvent être résolues uniquement par des substitutions.

9.3

Liens avec les problèmes classiques de la théorie des graphes

Vérifier que tous les circuits d'un graphe passent par le même sommet est en relation avec plusieurs problèmes classiques de la théorie des graphes. L'algorithme le plus direct consiste à chercher tous les circuits élémentaires du graphe et à regarder si ces circuits ont des sommets communs. Il est indispensable de trouver tous les circuits élémentaires et non uniquement une base de circuits élémentaires. En effet, si la déconnexion d'un sommet coupe tous les circuits de la base cela ne signifie pas que tous les circuits sont coupés (voir le contre-exemple ci-dessous).

Or il n'existe pas d'algorithme connu pour trouver les circuits élémentaires d'un graphe en temps polynomial. Des algorithmes existent comme celui présenté dans [61] mais leur temps d'exécution est de l'ordre de O(n!) où n est le nombre de sommets du graphe.

Notre problème est aussi lié au problème de la recherche d'un transversal de cardinal inférieur ou égal à k dans l'hypergraphe des circuits d'un graphe donné. Pour comprendre cet énoncé, certaines définitions sont nécessaires. Tout d'abord la notion d'hypergraphe est une extension de la notion de graphe où les arêtes ne sont plus des couples mais des sous-ensembles de l'ensemble des sommets (cf [9]). Les hypergraphes sont donc des graphes dont les arêtes ne relient plus seulement deux sommets mais un ensemble quelconque de sommets. L'hypergraphe des circuits d'un graphe donné est l'hypergraphe dont les sommets sont ceux du graphe et les arêtes les ensembles de sommets des circuits élémentaires du graphe. D'autre part, un transversal d'un hypergraphe est un ensemble de sommets qui possède au moins un sommet en commun avec chaque arête de l'hypergraphe. Un transversal de l'hypergraphe des circuits est donc un ensemble de sommets par lesquels passent tous les circuits du graphe. Ainsi, s'il existe un transversal de l'hypergraphe des circuits de cardinal 1, tous les circuits passent par un même sommet et le graphe est normalisable. Malheureusement, il est prouvé qu'il n'existe aucun algorithme en temps polynomial capable de résoudre le problème général (cf [32]). Cela ne signifie pas que notre problème ne peut être résolu en temps polynomial car c'est une instance du problème général avec k=1.

9.4

Heuristiques et algorithmes de normalisation

Il existe des procédés plus réalistes pour normaliser un graphe. Si la rapidité de l'analyse est primordiale (par exemple dans le cas de compilateurs commerciaux) une heuristique peut être utilisée. Cette heuristique repose sur le fait que si un graphe est acyclique il est a fortiori sans circuits. Or il est très facile de déterminer si un graphe est acyclique, il suffit de vérifier que son nombre cyclomatique est nul. Si n est le nombre de sommets dans le graphe G, si m est le nombre d'arcs de G et si p est son nombre de composantes connexes, le nombre cyclomatique est n(G)=m-n+p. Le principe de l'heuristique est de considérer un sommet v d'un graphe fortement connexe et de supprimer ses arcs sortants. Le graphe obtenu est un graphe connexe. Donc, si le nombre d'arcs sortants est m_v alors son nombre cyclomatique est m-m_v-n+1. Dans le cas où ce nombre est nul le graphe est acyclique donc sans circuits et le sommet considéré est inclus dans tous les circuits du graphe initial. Bien sûr, si le nombre n'est pas nul cela signifie simplement qu'il existe des cycles, pas forcément des circuits. Vérifier que m-m_v-n+1 est nul n'est donc qu'une condition suffisante pour qu'un sommet v soit inclus dans tous les cycles, ce n'est pas une condition nécessaire. La complexité de l'heuristique est faible puisqu'il suffit de faire un calcul trivial pour chaque sommet. L'algorithme peut donc être exécuté en un temps linéaire en fonction du nombre de sommets du graphe. Son efficacité est bonne car les cas où l'heuristique ne trouve pas de sommet inclus dans tous les circuits, alors qu'il en existe, sont rares (en fait aucun des exemples réels traités pendant la mise au point des prototypes n'a mis en défaut l'heuristique).

Le programme ci-dessous permet de donner un exemple d'utilisation de l'heuristique.
DO i=1,n
 a(i)=f(v(i-1))        (v1)
 b(i)=g(v(i-1),a(i))   (v2)
 v(i)=h(b(i))          (v3)
END DO
Le graphe des équations du système correspondant est :

Le nombre cyclomatique associé à v1 est 1 et le graphe connexe comporte bien un circuit entre v2 et v3. Le nombre cyclomatique associé à v2 est là aussi 1 mais le graphe connexe comporte uniquement un cycle, pas un circuit. Heureusement le dernier sommet v3 a un nombre cyclomatique associé nul et, effectivement, tous les circuits passent par v3.

Cette heuristique peut être utilisée conjointement à une méthode exacte (comme celles décrites ci-dessous) pour éliminer les cas triviaux.

La plus simple des méthodes exactes est semblable à l'heuristique mis à part qu'au lieu d'un simple calcul de nombre cyclomatique, un parcours en profondeur est effectué pour vérifier qu'aucun circuit n'existe dans le graphe modifié. Le coût d'un parcours en profondeur est de l'ordre du nombre d'arcs du graphe, donc la complexité complète de la méthode est de l'ordre du nombre de sommets du graphe multiplié par le nombre d'arcs du graphe.

Il existe une seconde méthode avec une complexité plus faible. Il s'agit d'effectuer des substitutions de graphe, jusqu'à reporter (si cela est possible) tous les circuits sur un unique sommet. Seules les substitutions simples, c'est-à-dire dont la source ne possède qu'un seul successeur autre qu'elle-même sont utilisées (i.e. seules les équations ou les clauses référencées une seule fois sont substituées). Le schéma ci-dessous décrit l'effet d'une telle substitution :

Les prédécesseurs de v₀ sont ajoutés à ceux de v₁, ce sommet possède donc k₁' prédécesseurs compris entre max(k₀,k₁) et k₀+k₁. Une propriété importante de ces substitutions est que, si le graphe initial est fortement connexe, après la substitution :

plus aucun circuit ne passe par v₀ ;
le graphe résultant restreint à tous les sommets sauf v₀ est lui aussi fortement connexe.

Preuve:: Le sommet v₀ ne possède plus de successeur donc aucun circuit ne peut le traverser. Montrons qu'il existe un chemin d'un sommet v_i avec i>0 vers un sommet v_j avec j>0 dans le graphe modifié. Comme le graphe initial est fortement connexe il existe un chemin de v_i vers v_j dans ce graphe. Si le chemin ne passe pas par v₀, il existe encore dans le graphe modifié. Sinon le chemin passe, successivement, par v₀^-, un prédécesseur de v₀, puis par v₀ et par v₀⁺ un successeur de v₀. Or, dans le graphe modifié les prédécesseurs de v₀ sont aussi ceux de v₀⁺ donc il existe un arc entre v₀^- et v₀⁺ et en conséquence un chemin de v_i vers v_j.

Il en résulte que lorsque plus aucune de ces substitutions ne peut être appliquée au graphe :

soit, la composante fortement connexe est réduite à un sommet, et dans le graphe initial, tous les circuits passent par ce sommet ;
soit, la composante fortement connexe comporte plusieurs sommets et le graphe n'est pas normalisable.

Preuve:: Comme le graphe initial est modifié par des substitutions, le critère de normalisation implique que si, dans le graphe final, les seuls circuits sont des boucles alors dans le graphe initial tous les circuits passent par un même sommet. De plus la démonstration du critère indique que pour chaque circuit µ du graphe initial il existe un circuit dans le graphe modifié passant uniquement par des sommets du circuits µ. En conséquence le sommet de la composante fortement connexe finale appartient à tous les circuits du graphe initial.

Montrons que si plusieurs sommets restent dans la composante fortement connexe finale alors il n'existe pas de sommet commun aux circuits du graphe initial. Il faut commencer par montrer que si un graphe modifié possède une composante fortement connexe telle que pour chacun de ses sommets elle possède un circuit ne l'incluant pas, alors il en est de même pour le graphe initial. Remarquons d'abord que si l'un des circuits du graphe modifié n'est pas dans le graphe initial, c'est qu'il comporte forcément un nouvel arc (v_i,v_j). Or, d'après la définition d'une substitution dans un graphe, ce nouvel arc ne peut exister que si le graphe initial comprend un sommet v_k et des arcs (v_i,v_k) et (v_k,v_j). Ce graphe possède donc un circuit presque identique à celui du graphe modifié mais passant par v_i, v_k ,v_j au lieu de sauter directement de v_i à v_j. De plus le sommet v_k n'a qu'un successeur v_j. Comme une seule substitution est effectuée pour modifier le graphe, v_k est le seul sommet supplémentaire qui peut se trouver dans les circuits du graphe initial. En outre, tout circuit incluant v_k inclut aussi v_j. Comme tous les circuits du graphe modifié n'incluent pas v_j il en est de même pour v_k. En résumé si la composante fortement connexe du graphe modifié est telle que tous ses circuits ne passent pas par un même sommet, il en est de même pour le graphe initial.

Par ailleurs s'il reste, dans la composante fortement connexe finale, plusieurs sommets, alors tous ses circuits ne passent pas par un même sommet. En effet, si aucune substitution ne peut plus être effectuée c'est que tous les sommets ont au moins deux successeurs. Donc si un sommet est déconnecté, alors les sommets restants possèdent encore au moins un successeur. Donc il existe un circuit ne passant pas par ce sommet. En conséquence, le graphe de départ n'est pas normalisable.

En conclusion, si le graphe est normalisable, l'application de substitutions simples permet de trouver le sommet par lequel passent tous les circuits du graphe. Ce résultat signifie qu'une séquence de substitutions simples est aussi puissante (en ce qui concerne la normalisation de systèmes d'équations) qu'une séquence de substitutions simultanées. La méthode peut être implantée efficacement si à chaque sommet v du graphe est associée la liste triée de ses prédécesseurs pred(v). L'algorithme peut s'écrire comme suit :

Algorithme 7 Recherche du sommet commun

Pour chaque sommet v, calculer (à partir des listes pred) le nombre de successeurs de v, ns(v) et stocker un de ses successeurs dans succ(v).
Initialiser la pile p et empiler tous les sommets ayant un seul successeur.
Terminer si la pile p est vide ou s'il ne reste plus qu'un sommet dans la composante fortement connexe.
Dépiler v de p. Notons v⁺ le successeur de v mémorisé dans succ(v).
Effectuer un tri-fusion de pred(v) et de pred(v⁺), à chaque fois qu'un doublon v^- est trouvé, décrémenter son nombre de successeurs ns(v^-) d'une unité. Si ce nombre est égal à 1 empiler v^- sur p.
Affecter le résultat du tri-fusion à pred(v⁺) et pour tous ces prédécesseurs v^- déclarer que le successeur privilégié succ(v^-) est v⁺.
Aller à l'étape 3.

Puisqu'à chaque itération un sommet est éliminé de la composante fortement connexe et que le tri-fusion est linéaire, la complexité au pire de l'algorithme est en O(n× d^-) où n est le nombre de sommets du graphe et d^- la taille maximale des listes pred. Au pire la complexité est en O(n²) ; dans certains cas de figure elle est même linéaire (par exemple si le graphe ne comporte qu'un circuit). Cette méthode est donc meilleure que celle utilisant un parcours en profondeur. En effet dans un graphe fortement connexe il existe entre n et n² arcs donc la complexité de la méthode précédente est en O(n³) au pire.

Montrons, sur un exemple, comment notre algorithme basé sur des substitutions simples trouve les sommets par lesquels passent tous les circuits d'une composante fortement connexe. Le graphe de départ est donné ci-dessous.

Il faut noter que l'heuristique échoue sur ce graphe à cause des cycles parasites. Tous les tableaux utilisés par l'algorithme (7) sont donnés ici comme une liste de couples constitués d'un indice et de la valeur correspondante. Le tableau des prédécesseurs pred est donc :
pred={ (v1,{v4}) (v2,{v1}) (v3,{v1}) (v4,{v5 v6})
       (v5,{v2}) (v6,{v3 v7}) (v7,{v5}) }
Le tableau du nombre de successeurs ns initial est :
ns={ (v1,2) (v2,1) (v3,1) (v4,1) (v5,2) (v6,1) (v7,1) }
Quand au tableau succ il peut être initialisé à :
succ={ (v1,v2) (v2,v5) (v3,v6) (v4,v1) (v5,v4) (v6,v4) (v7,v6) }
Au vu de ns les valeurs empilées dans p sont :
p={ v7 v6 v4 v3 v2 }
Le premier sommet avec un seul successeur que l'algorithme considère est v7. Sa liste de prédécesseurs ne comporte pas d'élément commun avec celle de son successeur v6. Les nouveaux tableaux des prédécesseurs et du successeur privilégié sont :
pred={ (v1,{v4}) (v2,{v1}) (v3,{v1}) (v4,{v5 v6}) (v5,{v2}) (v6,{v3 v5}) }
succ={ (v1,v2) (v2,v5) (v3,v6) (v4,v1) (v5,v6) (v6,v4) }
Intuitivement le sommet v7 vient d'être retiré de la composante fortement connexe comme indiqué sur le schéma ci-dessous :

Le nouveau sommet considéré est v6, la liste de ses prédécesseurs comprend un élément qui se retrouve dans celle de v4, il s'agit du sommet v5. En conséquence le nombre de successeurs de v5 passe à 1 et v5 est empilé sur p. Les nouvelles variables de l'algorithme sont :
pred={ (v1,{v4}) (v2,{v1}) (v3,{v1}) (v4,{v3 v5}) (v5,{v2}) }
ns={ (v1,2) (v2,1) (v3,1) (v4,1) (v5,1) }
succ={ (v1,v2) (v2,v5) (v3,v4) (v4,v1) (v5,v4) }
p={ v5 v4 v3 v2 }
Le sommet v6 à été éjecté de la composante fortement connexe :

Notons qu'à ce niveau de l'algorithme l'heuristique découvre que v1 est un transversal. Le sommet à traiter est désormais v5. Sa liste pred ne contient pas d'élément commun avec celle de son successeur v4, le tableau ns est donc inchangé. Les nouveaux tableaux pred et succ sont :
pred={ (v1,{v4}) (v2,{v1}) (v3,{v1}) (v4,{v2 v3}) }
succ={ (v1,v2) (v2,v4) (v3,v4) (v4,v1) }
La composante fortement connexe réduit encore :

Les dernières étapes sont données sur le schéma ci-dessous :

Finalement seul le sommet v1 reste dans la composante fortement connexe : c'est le transversal minimal du graphe initial.

9.5

Les substitutions dans un système d'équations

Notre but est de ramener, sur une seule équation (ou clause), les récurrences portant sur plusieurs équations. Nous avons vu, dans les sections précédentes, qu'il existe plusieurs algorithmes pour trouver l'équation (ou la clause) sur laquelle peuvent se concentrer les récurrences. Il reste à déterminer lequel de ces algorithmes est le plus adapté en gardant en mémoire qu'une seconde phase de traitement est nécessaire pour appliquer les substitutions dans le système d'équations.

9.5.1

Choix de la méthode de recherche du transversal

En fait la complexité de la méthode de recherche d'un transversal n'est pas fondamentale. En effet la complexité de la phase de substitutions dans le système est en théorie exponentielle. Parmi toutes les méthodes polynomiales, il convient de prendre la plus efficace en le sens où :

s'il existe un transversal de cardinal 1 il est détecté ;
s'il n'existe pas de transversal de taille 1, un petit transversal (pas forcément un transversal minimal mais un transversal de faible taille) est trouvé.

Ainsi, si les récurrences d'un sous-système peuvent être concentrées sur une seule équation elle le sont, et la phase de reconnaissance de forme peut être appliquée. Dans le cas contraire, les récurrences sont concentrées sur un petit ensemble d'équations. Dans le cas où les équations proviennent d'un même nid de boucles, il est possible de les transformer en une équation opérant sur un vecteur et non plus sur des scalaires, la phase de reconnaissance de forme peut, là aussi, être appliquée. Enfin dans le pire des cas, un gain est encore possible : la réduction du nombre d'équations possédant des références croisées réduit très sensiblement le temps de calcul de l'ordonnancement du système d'équations (voir l'exemple de la section 11.5).

L'algorithme direct utilisant le parcours en profondeur trouve toujours les transversaux réduits à un sommet mais n'est pas capable de trouver des petits transversaux de cardinal strictement supérieur à 1. L'algorithme D de Shamir ne peut pas être utilisé car s'il trouve le plus souvent des petits transversaux, il ne trouve pas toujours les transversaux de cardinal 1. Une solution est d'utiliser l'algorithme de normalisation avec substitutions qui vérifie les deux critères d'efficacité. L'algorithme de contraction décrit dans [42] est lui aussi bien adapté. Sa programmation est plus difficile, car il utilise plus de transformations sur les graphes que la simple substitution. Sa complexité est un peu plus élevée que celle de notre algorithme. Mais le fait qu'il obtienne des transversaux minimaux pour de nombreux graphes compense ces aspects négatifs.

9.5.2

Application des substitutions au système

Une fois le transversal trouvé, il est facile d'appliquer au système d'équations des substitutions pour faire en sorte que toutes les récurrences soient reportées sur les équations du transversal. Si la normalisation se fait au niveau des équations, il suffit d'effectuer (comme dans la démonstration du critère de normalisation) un tri topologique sur les sommets de la composante fortement connexe qui ne sont pas dans le transversal. Il faut alors substituer les équations de premier niveau dans celles de second niveau, et ainsi de suite. Si la normalisation se fait au niveau des clauses, l'algorithme se complexifie un peu car lors de la substitution des clauses d'un niveau n dans celles de niveau n+1, de nouvelles clauses apparaissent. La solution est de considérer ces nouvelles clauses comme des clauses de niveau n+1 et de les substituer dans celles de niveau n+2.

La complexité de ces opérations est théoriquement exponentielle et à deux niveaux : au niveau du nombre d'opérations sur les convexes à effectuer et au niveau de ces opérations elle-mêmes. En effet une substitution (que ce soit une substitution d'équation, ou que ce soit, dans une moindre mesure, une substitution de clause) tend à augmenter le nombre de clauses, donc à augmenter le nombre d'intersections entre domaines de clauses et de simplifications de ces domaines. De plus ces opérations d'intersection et de simplification sont implantées à l'aide d'algorithmes potentiellement exponentiels (comme l'algorithme de Chernikova, voir [31]). En pratique l'explosion exponentielle de la complexité est limitée. Pour la bibliothèque d'opérations sur les convexes que nous utilisons (voir [64]), la complexité d'une fonction est de l'ordre de a^ë^d/2^û avec a le nombre d'inéquations linéaires définissant les convexes et d la dimension de l'espace dans lequel sont plongés les convexes. Cette dimension est la profondeur maximale des nids de boucles du programme initial. En pratique d est de l'ordre de 3 ou 4 ; la complexité de ce genre d'opérations peut donc être considérée comme polynomiale en le nombre a d'inéquations définissant les convexes. Par ailleurs les simplifications des domaines des clauses gardent le nombre d'inéquations assez bas, de même qu'elles ont tendance à réduire le nombre de clauses en détectant celles dont les domaines de définition sont vides. En conclusion la complexité de la phase d'application des substitutions est élevée mais des composantes fortement connexes de l'ordre de 100 équations peuvent être traitées en des temps raisonnables.

9.5.3

Augmenter l'efficacité de la normalisation

N'oublions pas que la modélisation de la substitution par la théorie des graphes n'est qu'approximative : elle génère certains arcs qui ne correspondent pas forcément à une référence. Ceci à cause de la simplification des domaines des clauses qui peuvent conduire à des domaines vides, donc à la suppression de clauses. De plus, si la normalisation se fait au niveau des clauses la modélisation de la substitution traite les clauses par ``paquets'' dès la seconde substitution de graphe. La méthode de la recherche d'un transversal minimal de l'hypergraphe des circuits conduit donc à des normalisations imparfaites. La méthode la plus efficace est d'appliquer l'algorithme des substitutions simples (voir section 8.4) directement sur le système d'équations plutôt que sur des graphes qui correspondent de moins en moins à la réalité au fur et à mesure de l'application des substitutions de graphe. Le graphe du système est alors régénéré après chaque substitution réelle (i.e. d'équation ou de clause). Parmi les méthodes de contraction de graphe, seule la méthode des substitutions peut être utilisée ainsi car elle seule garantit la transformation en un système équivalent. Ce n'est cependant pas la solution idéale car le graphe du système est calculé de l'ordre de n fois (avec n le nombre d'équations du système). Même avec une modification incrémentale du graphe la complexité explose car de nombreuses manipulations de convexes sont nécessaires.

9.6

La fusion des équations

Lorsque la normalisation d'un système par substitutions échoue, il reste encore une carte à jouer : la fusion des équations. Le principe est d'essayer de remplacer les équations d'un sous-système fortement connexe par une seule équation opérant non plus sur des scalaires mais sur des vecteurs. La fusion d'équations n'est pas toujours valide ; en effet chaque vecteur calculé par la nouvelle équation doit être une entité indivisible. Cela signifie que les composantes d'un vecteur doivent pouvoir être calculées de façon indépendante. De plus, pour que la fusion puisse se faire aisément en pratique, d'autres contraintes sont ajoutées :

le sous-système fortement connexe considéré ne contient que quelques équations (deux ou trois, le but étant de détecter principalement les opérations sur les complexes ou sur des matrices de très faible taille) ;
les équations doivent calculer le même type de scalaires (e.g. un vecteur constitué d'un réel et d'un booléen n'est pas facile à gérer au niveau de la génération de code) ;
les domaines de définition des équations doivent être identiques, sinon il serait nécessaire de remplir certaines composantes avec des valeurs inutiles.

Les domaines des équations étant identiques, il sont définis par le même nombre n de variables. La condition de validité de la fusion est alors qu'il ne doit pas y avoir de dépendances de profondeur n entre les différentes équations ; dans ce cas les diverses composantes des vecteurs seront bien indépendantes. Cette condition est facile à vérifier. Par contre la transformation sur le système d'équations demande quelques calculs. Il faut d'abord créer la nouvelle équation. Le point délicat est le calcul des domaines de définition des nouvelles clauses. En effet, si le domaine des équations est identique, les domaines des clauses peuvent différer. L'algorithme à appliquer est de considérer deux équations du sous-système, d'intersecter deux à deux les domaines des clauses de ces équations, puis de recommencer avec les domaines obtenus et les domaines des clauses d'une autre équation, et ainsi de suite. La fusion augmente donc le nombre de clauses ; pour éviter ce problème, il est possible d'imposer que les domaines des clauses des équations soient identiques. La seconde modification sur le système consiste à remplacer les références aux anciennes équations par des références à des composantes de la nouvelle équation. Cela nécessite l'introduction d'un opérateur de projection que nous noterons proj. La fonction proj prend en argument un vecteur et le numéro de la composante à extraire.

Considérons le calcul d'un produit de matrices 2x2 :
v1 : { i | 1 <= i <= n } of real ;
v2 : { i | 1 <= i <= n } of real ;
v3 : { i | 1 <= i <= n } of real ;
v4 : { i | 1 <= i <= n } of real ;
v1[i] = case
         { i | i = 1 }  : a[1,1] ; 
         { i | i >= 2 } : v1[i-1]*a[1,1]+v2[i-1]*a[1,2] ; 
        esac ;
v2[i] = case
         { i | i = 1 }  : a[1,2] ; 
         { i | i >= 2 } : v1[i-1]*a[1,1]+v2[i-1]*a[1,2] ; 
        esac ;
v3[i] = case
         { i | i = 1 }  : a[2,1] ; 
         { i | i >= 2 } : v3[i-1]*a[2,1]+v4[i-1]*a[2,2] ; 
        esac ;
v4[i] = case
         { i | i = 1 }  : a[2,2] ; 
         { i | i >= 2 } : v3[i-1]*a[2,1]+v4[i-1]*a[2,2] ; 
        esac ;
Même le graphe des clauses d'un tel système n'est pas normalisable par des substitutions :

En effet les circuits de la composante fortement connexe formée de v1.1 et de v2.1 ne passent pas par un même sommet. Idem pour la composante incluant v3.1 et v4.1. Par contre, les quatre équations ont le même domaine de définition (c'est logique puisqu'elles proviennent du même nid de boucles) et les dépendances sont toutes de profondeur 0. Il est donc valide de fusionner v1 et v2, ainsi que v3 et v4. Il n'y a pas de problème de génération des domaines des clauses pour les nouvelles équations car les domaines des clauses des anciennes équations sont analogues. Si x est un opérateur qui forme des couples à partir de deux vecteurs de scalaires, le système après fusion s'écrit :
u1 : { i | 1 <= i <= n } of real x real ;
u2 : { i | 1 <= i <= n } of real x real ;
u1[i] = case
         { i | i = 1 }  : a[1,1] x a[1,2] ;
         { i | i >= 2 } :
           ( proj(u1[i-1],1)*a[1,1]+proj(u1[i-1],2)*a[1,2] ) x
           ( proj(u1[i-1],1)*a[1,1]+proj(u1[i-1],2)*a[1,2] ) ;
        esac ;
u2[i] = case
         { i | i = 1 }  : a[2,1] x a[2,2] ;
         { i | i >= 2 } :
           ( proj(u2[i-1],1)*a[2,1]+proj(u2[i-1],2)*a[2,2] ) x
           ( proj(u2[i-1],1)*a[2,1]+proj(u2[i-1],2)*a[2,2] ) ;
        esac ;
Le système est alors en forme normale ; pour s'en convaincre il suffit de regarder le graphe du système :

La reconnaissance de forme peut donc être appliquée sur l'expression de u1.1 et sur celle de u2.1. Si une règle sur le produit matrice-vecteur est prévue, la détection de la multiplication de matrices se fait sous la forme de deux de ces produits.

Une remarque importante est que la fusion de clauses est impossible ; en effet les références dans le système d'équations se font aux variables définies par les équations. Il n'est donc pas possible de changer uniquement le type des valeurs calculées par une clause ; il faut changer le type des valeurs pour toute l'équation.

9.7

Liens avec les autres méthodes de réduction de graphes

L'algorithme utilisant les substitutions au niveau des graphes entre dans la classe des algorithmes de réduction de graphes. Ces algorithmes ont en commun de partir d'un graphe et de tenter de le ramener à un unique sommet par le jeu de transformations simples. Si le graphe peut être ramené à un seul sommet il est appelé graphe réductible. Ces algorithmes sont utilisés pour l'analyse du flot des données de programmes impératifs (cf [2]), pour la structuration de tels programmes (suppression des goto, voir [4]) et surtout pour la recherche de transversaux minimaux (cf [42]). Les transformations sur les graphes utilisées par ces algorithmes sont décrites par le schéma suivant :

Pour les algorithmes d'analyse du flot des données et de structuration de programmes les sommets représentent des blocs d'instructions et les arcs des branchements entre les blocs. Ils utilisent les transformations Boucle-faible et 1-pred. L'algorithme de recherche de transversaux minimaux utilise toutes les transformations sauf la Boucle-faible. Enfin, l'algorithme de normalisation à base de substitutions utilise la transformation 1-succ. Il est intéressant de comparer les relations entre les différentes classes de graphe réductibles. En s'appuyant sur les notations de [42] appelons graphes flot-réductibles les graphes réductibles au sens des algorithmes concernant les programmes impératifs et graphes contractibles les graphes réductibles au sens de l'algorithme de recherche de transversaux. Enfin appelons graphes normalisables les graphes réductibles au sens de notre algorithme basé sur les substitutions. Les ensembles des graphes flot-réductibles et des graphes normalisables ne sont pas comparables au sens de l'inclusion. En effet, il est évident que des graphes non normalisables sont flot-réductibles puisque cette dernière réduction comporte une transformation supplémentaire, la transformation Boucle-faible.

Considérons le système d'équation ci-dessous.
v1 : { i | 1 <= i <= n } of real ;
v2 : { i | 1 <= i <= n } of real ;
v1[i] = case
         { i | i = 1 }  : cst1 ;
         { i | i >= 2 } : v1[i-1] + v2[i-1] ;
        esac
v2[i] = case
         { i | i = 1 }  : cst2 . (i -> ) ;
         { i | i >= 2 } : 2 * v1[i-1] + v2[i-1] ;
        esac
Considérons aussi le programme impératif suivant.
label v1:  Ia ; if Pa then goto v1 else goto v2
label v2:  Ib ; if Pb then goto v2 else goto v1
Ces deux entités possèdent la même représentation graphique :

mais le système n'est pas normalisable alors que le programme est flot-réductible. En effet, le programme peut être structuré comme montré ci-dessous.
label v1:  do { do Ia while Pa ; do Ib while Pb } while true

Il existe aussi des graphes non flot-réductibles qui sont normalisables. Cela tient au fait que pour la normalisation, la transformation 1-succ est appliquée en ne tenant compte que des arcs de la composante fortement connexe alors que dans le cas de la flot-réduction tous les arcs sont considérés.

Considérons le système d'équation ci-dessous.
x : { i | 1 <= i <= n } of real ;
y : { i | 1 <= i <= n } of real ;
v1 : { i | 1 <= i <= n } of real ;
v2 : { i | 1 <= i <= n } of real ;
v3 : real ;
v3 = 1 ;
v1[i] = case
         { i | i = 1 }  : v3 ;
         { i | i >= 2 } : v2[i-1] + x[i] ;
        esac
v2[i] = case
         { i | i = 1 }  : v3 ;
         { i | i >= 2 } : v1[i-1] + y[i] ;
        esac
Considérons aussi le programme impératif suivant.
label v3: if Pc then goto v1 else goto v2
label v1: Ia ; goto v2
label v2: Ib ; goto v1
Ils ont la même représentation graphique :

mais le programme n'est pas flot-réductible alors que le système est normalisable. La raison intuitive en est que les arcs sortant de v3 ne sont pas considérés pour la normalisation. Les raisons plus profondes sont que :

il est impossible, sans duplication de code, de structurer le programme (une boucle n'a qu'un point d'entrée, sa première instruction) ;
le système ne comporte qu'une seule récurrence définie par deux équations v1 et v2 ; il est donc normalisable par substitution de v1 dans v2 ou réciproquement.

Par ailleurs, il est montré dans [42] que la classe des graphes contractibles contient la classe des graphes flot-réductibles. Il est plus difficile de situer la classe des graphes normalisables par rapport à la classe des graphes contractibles. Vu que la transformation 1-succ utilisée pour la normalisation est aussi utilisée pour la contraction, la classe des graphes normalisables devrait être incluse dans la classe des graphe contractibles. Stricto sensu c'est faux car la normalisation ne considère que les arcs dans la composante fortement connexe. Cependant la classe des graphes pour lesquels l'algorithme de recherche de transversaux de l'hypergraphe des circuits donne un transversal minimum peut être aisément étendue au delà de la classe des graphes contractibles. Il suffit de remarquer que l'union des transversaux minimaux des composantes fortement connexes d'un graphe est un transversal minimal pour ce graphe.

Preuve:: Notons (G_i)_iÎ_N_{_n}^_* les composantes fortement connexes du graphe G. Si les (T_i)_iÎ_N_{_n}^_* sont des transversaux de ces composantes alors T=È_iÎ_N_{_n}^_* T_i est un transversal de G. Sinon, il existerait un circuit non coupé par la déconnexion de T, donc un circuit incluant au moins deux sommets de composantes fortement connexes distinctes : une contradiction. De même si T est un transversal de G alors les (T_i=TÈ G_i)_iÎ_N_{_n}^_* sont des transversaux des composantes. Sinon, il existerait un circuit, dans une composante, non coupé par la déconnexion du T_i correspondant. Comme au moins un sommet de ce circuit est dans T et que les (G_i)_iÎ_N_{_n}^_* sont une partition de G, alors un sommet de ce circuit serait dans une autre composante : une contradiction. Supposons que les (T_i)_iÎ_N_{_n}^_* sont des transversaux minimaux pour les (G_i)_iÎ_N_{_n}^_* alors T=È_iÎ_N_{_n}^_* T_i est minimal pour G. Sinon il existerait un transversal T' de cardinal strictement inférieur à T. Notons (T'_i=T'È G_i)_iÎ_N_{_n}^_* les transversaux induits par T' sur les composantes. Forcement, il existerait un T'_i de cardinal strictement inférieur au T_i correspondant : une contradiction sur la minimalité de T_i.

Il suffit donc d'appliquer l'algorithme de recherche des transversaux aux composantes fortement connexes (ce qui ne pénalise pas l'algorithme de [42], puisqu'il existe un algorithme de recherche des composantes fortement connexes linéaire en le nombre d'arcs). Cette fois la classe des graphes dont les composantes fortement connexes sont contractibles inclus la classe des graphes normalisables. L'algorithme de [42], appliqué après une phase de calcul des composantes fortement connexes, convient donc pour la normalisation car tous les transversaux de cardinal 1 sont trouvés. La complexité de cet algorithme est de l'ordre de m× log(n) (m désigne le nombre d'arcs du graphe et n son nombre de sommets). Elle est donc, au pire, de l'ordre de n²× log(n).

Notons qu'il existe un algorithme linéaire en le nombre de sommets (connu sous le nom d'algorithme D de Shamir) qui trouve le transversal minimal pour tous les graphes fortement quasi-réductible. Cet algorithme n'est d'ailleurs pas un algorithme de contraction de graphe ; il repose sur le parcours en profondeur du graphe (voir [58]). Malheureusement la classe des graphes fortement quasi-réductibles n'inclut pas la classe des graphes normalisables (et cette fois il en est de même pour la classe des graphes dont les composantes fortement connexes sont fortement quasi-réductibles).

Considérons le graphe fortement connexe suivant :

Tous les circuits passent par le même sommet v2, donc le graphe est normalisable. Par contre l'algorithme D de Shamir échoue à trouver un transversal minimal.