THEORIE DES JEUX ET GRAPHES

La théorie des jeux utilise des graphes, que ce soit des graphes d'états ou des graphes mathématiques classiques. Nous présentons dans une première partie quelques généralités sur les graphes avant d'appliquer ces connaissances à la théorie des jeux.

1. Généralités sur les Graphes

Les graphes sont des structures de données très utilisées car elles décrivent simplement des relations entre les éléments d'un même ensemble ; en particulier une structure hiérarchique peut être représentée par un arbre mathématique, lui-même considéré comme un graphe cyclique. Sans entrer à fond dans la théorie mathématique des arbres et des graphes, nous présentons ici quelques algorithmes classiques.

Un graphe G=(S,A) est défini par un ensemble S de sommets et un ensemble A d'arcs. Les sommets sont les éléments d'un ensemble E de départ, les arcs joignent des couples de sommets. On parle ainsi de l' arc <x,y> qui joint x à y. On peut généraliser ou raffiner : 

   - pour un graphe orienté on distingue <x,y> de <y,x>.

   - pour un graphe n-aire, x et y peuvent être joints de
   différents façons ;

   - il faut alors numéroter les arcs afférents aux mêmes
   couples de points.

   - pour  un  multigraphe,  on  gère des n-uplets comme
    au lieu de couples.
Pour simplifier notre vue des graphes, nous traiterons dans un premier temps des graphes unaires simples (= non mutliples) et non orientés. A titre d'exemple, nous prendrons le fichier suivant où seuls les arcs x y (pour x < y) sont indiqués, la liaison y x étant induite par la lecture du fichier. 

    1  2 <-- Arc numéro 1 dansle fichier BIGCROIS.GRF
    1  3     Arc numéro 2
    1  6     Arc numéro 3 etc.
    1  7     (seuls les arcs x y avec x < y sont indiqués)
    3  7     (le programme crée automatiquement l'arc y x)
    4  5     (car le graphe est non orienté)
    4  6
    5  6
    5  7
    7  8
    7 10
    7 12
    8  9
   10 11
   10 12
   10 13
   12 13
Deux représentation graphiques possibles du graphe montrent la différence entre forme et propriétés :

De façon à rendre les sorties d'algorithme plus lisibles, nous nommerons A le sommet 1, B le sommet 2 etc. Le premier algorithme classique est celui de la construction de la structure de graphe à partir de la liste des arcs. L'implémentation d'un graphe peut se faire par le biais de la matrice d'ajacence, la matrice de connectivité ou des listes de connectivité. Nous donnons ci- dessous ces trois structures pour notre exemple :

Matrice d'adjacence 

            A  B  C  D  E  F  G  H  I  J  K  L  M
         +-----------------------------------------+
Arc   1  ¦  1  1  0  0  0  0  0  0  0  0  0  0  0  ¦
Arc   2  ¦  1  0  1  0  0  0  0  0  0  0  0  0  0  ¦
Arc   3  ¦  1  0  0  0  0  1  0  0  0  0  0  0  0  ¦
Arc   4  ¦  1  0  0  0  0  0  1  0  0  0  0  0  0  ¦
Arc   5  ¦  0  0  1  0  0  0  1  0  0  0  0  0  0  ¦
Arc   6  ¦  0  0  0  1  1  0  0  0  0  0  0  0  0  ¦
Arc   7  ¦  0  0  0  1  0  1  0  0  0  0  0  0  0  ¦
Arc   8  ¦  0  0  0  0  1  1  0  0  0  0  0  0  0  ¦
Arc   9  ¦  0  0  0  0  1  0  1  0  0  0  0  0  0  ¦
Arc  10  ¦  0  0  0  0  0  0  1  1  0  0  0  0  0  ¦
Arc  11  ¦  0  0  0  0  0  0  1  0  0  1  0  0  0  ¦
Arc  12  ¦  0  0  0  0  0  0  1  0  0  0  0  1  0  ¦
Arc  13  ¦  0  0  0  0  0  0  0  1  1  0  0  0  0  ¦
Arc  14  ¦  0  0  0  0  0  0  0  0  0  1  1  0  0  ¦
Arc  15  ¦  0  0  0  0  0  0  0  0  0  1  0  1  0  ¦
Arc  16  ¦  0  0  0  0  0  0  0  0  0  1  0  0  1  ¦
Arc  17  ¦  0  0  0  0  0  0  0  0  0  0  0  1  1  ¦
         +-----------------------------------------+
Matrice de connectivité 

     A  B  C  D  E  F  G  H  I  J  K  L  M
  +-----------------------------------------+
A ¦  0  1  1  0  0  1  1  0  0  0  0  0  0  ¦
B ¦  1  0  0  0  0  0  0  0  0  0  0  0  0  ¦
C ¦  1  0  0  0  0  0  1  0  0  0  0  0  0  ¦
D ¦  0  0  0  0  1  1  0  0  0  0  0  0  0  ¦
E ¦  0  0  0  1  0  1  1  0  0  0  0  0  0  ¦
F ¦  1  0  0  1  1  0  0  0  0  0  0  0  0  ¦
G ¦  1  0  1  0  1  0  0  1  0  1  0  1  0  ¦
H ¦  0  0  0  0  0  0  1  0  1  0  0  0  0  ¦
I ¦  0  0  0  0  0  0  0  1  0  0  0  0  0  ¦
J ¦  0  0  0  0  0  0  1  0  0  0  1  1  1  ¦
K ¦  0  0  0  0  0  0  0  0  0  1  0  0  0  ¦
L ¦  0  0  0  0  0  0  1  0  0  1  0  0  1  ¦
M ¦  0  0  0  0  0  0  0  0  0  1  0  1  0  ¦
  +-----------------------------------------+
Listes de connectivité 
 Sommets connectés à  A  : B  C  F  G
 Sommets connectés à  B  : A
 Sommets connectés à  C  : A  G
 Sommets connectés à  D  : E  F
 Sommets connectés à  E  : D  F  G
 Sommets connectés à  F  : A  D  E
 Sommets connectés à  G  : A  C  E  H  J  L
 Sommets connectés à  H  : G  I
 Sommets connectés à  I  : H
 Sommets connectés à  J  : G  K  L  M
 Sommets connectés à  K  : J
 Sommets connectés à  L  : G  J  M
 Sommets connectés à  M  : J  L
Une fois le graphe constitué, on peut s'intéresser au parcours ("visite") des éléments du graphe. Le parcours peut se faire en profondeur d'abord (méthode DFS ou "Depth First Search") ou en largeur d'abord (méthode BFS ou "Breadth First Search"). Nous présentons les algorithmes correspondants. Enfin, pour des graphes orientés et pesants, on peut chercher le chemin de longueur minimale entre deux points, l'arbre d'extension minimale et les composantes connexes. Les algorithmes qui réalisent la création et le parcours des graphes seront traduits en un programme REXX afin de montrer la facilité de traduction que donnent les tableaux dynamiques à "initialisation systématique" et pour donner un exemple d'utilisation de la pile/queue interne de REXX. 
{ Création de la matrice A d'ajdacence }
# dans le fichier fgraph, on lit nbarc arcs
 ouvrir fgraph
 pour ka de1à nbarc
   lire x, y sur fgraph
   A[ k,x ] * 1
   A[ k,y ] * 1
 fin pour ka de1à nbarc
 fermer fgraph
Si le nombre d'arcs n'est pas connu, on peut en faire le comptage au fur et à mesure. C'est ce que nous proposons pour la création de la matrice de connectivité. 
 { Création de la matrice C de connectivité }
 # on parcourt le fichier fgraph et on en déduit
 # le nombre nbsom de sommets et
 # le nombre nbarc d'arcs
 ouvrir fgraph
 nbsom * 0
 nbarc * 0
 tant que non fin de fichier( fgraph )
   nbarc * nbarc + 1
   lire x, y sur fgraph
   si y > nbsom alors
      nbsom * y
   fin si y > nbsom
   C[ x,y ] * 1
   C[ y,x ] * 1
 fin tant que non fin de fichier( fgraph )
 fermer fgraph
La gestion des listes de connectivité se fait à l'aide de tableaux classiques nommés tet, keu, suivant. Ces tableaux (qu'on pourrait définir autrement, via des pointeurs notamment) implémentent des listes liées associées à chacun des sommets. 
 { Création des listes de connectivité }
 # il y a déjà nbsom sommets et nbarc arcs lus dans
fgraph
 pour s de1a nbsom
   tet[s] <-- 0
   keu[s] <-- 0
 finpour s de1a nbsom
 ouvrir fgraph
 pour ka de1à nbarc
   lire x, y sur fgraph
   ajoute(y,x)
   ajoute(x,y)
 fin pour ka de1à nbarc
 fermer fgraph
Le module ajoute qui met le premier paramètre dans la liste du second peut être défini comme suit 
Module Ajoute
   paramètres a b
   globales   tet,keu,suivant
Début du Module Ajoute
   { met a dans la liste de b }
   si tet[b] = 0
      alors tet[b] <-- a
      sinon suivant[ b, keu[b] ] <-- a
   fin si tet[b] = 0
   suivant[ b,a ] <-- 0
   keu[b] <-- a
Fin du Module Ajoute
L'affichage de la liste associée à x se fait naturellement par : 
 { Affichage de la liste de connectivité de x }

 k <-- tet[x]
 tant que k > 0
   écrire k
   k <-- suivant[x,k]
 fin tant que k > 0
Le parcours DFS est un parcours récursif qui met en jeu une pile implicite. La méthode consiste à numéroter dans le tableau NumOrd l'ordre de passage par les sommets à l'aide la variable numérique CV (comme Compte Visite). Trouver 0 dans NumrOrd[x] signifie que x n'a pas encore été visité, d'où l'algorithme qui passe d'un sommet visité à un autre non encore visité. 
{ Parcours DFS (récursif) }
cv <-- 0
pour is de1à nbsom
  numord[is] <-- 0
fin pour is de1à nbsom
pour is de1à nbsom
  si numord[is] = 0
     visiteDFS( is )
  fin si numord[is] = 0
fin pour is de1à nbsom
Le module de visite utilise la matrice de connectivité C et peut s'écrire 
Module VisiteDFS
 paramètre x
 globales  C, numord, cv, nbsom
 locale    as
Début du Module VisiteDFS
  { Implémentation de la visite DFS }
  cv <-- cv + 1
  numord[x] <-- cv
  pour as de1à nbsom
    si C[x,as] = 1 et numord[as] = 0
       alors visiteDFS(as)
    fin si C[x,as] = 1 et numord[as] = 0
  fin pour as de1à nbsom
Fin duModule VisiteDFS
Cet algorithme viendra donc visiter 1/A (quand CV vaut 1) puis ira en 2/B (CV vaudra alors 2) puis passera en 3/C avant d'aller en 7/G puis en 5/E et en 4/D etc. Nous encourageons le lecteur à faire l'exécution à la main, au moins pour les premières visites... Le parcours BFS est un parcours non récursif qui met en jeu une queue explicite. La méthode numérote aussi dans le tableau NumOrd l'ordre de passage par les sommets à l'aide la variable numérique CV (comme Compte Visite). Trouver -1 dans NumrOrd[x] signifie que x n'a pas encore été visité, y trouver 0 signifie que le sommet est en attente et devra être utilisé quand on aura épuisé le sommet courant. 
{ Parcours BFS (non récursif) }
cv <-- 0
initialise( Q )
pour is de1à nbsom
  numord[is] <-- (-1)
fin pour is de1à nbsom
pour is de1à nbsom
  si numord[is] = -1
     visiteBFS( is )
     tant que nonvide( Q )
          extraire( Q,ind )
          visiteBFS( ind )
     fin tant que nonvide( Q )
  fin si numord[is] = -1
fin pour is de1à nbsom
Le module de visite utilise les listes de connectivité C : 
Module VisiteBFS
 paramètre x
 globales  suivant, numord, cv, Q
 locale    suit, apres
Début du Module VisiteBFS
  { Implémentation de la visite BFS }
  cv <-- cv + 1
  numord[x] <-- cv
  suit <-- tet[ x ]
  tant que suit > 0
     si numord[suit] = -1 alors
        metdans(Q,suit]
        numord[suit] <-- 0
     fin si numrord[suit] = -1
     apres <-- suivant[x,suit]
     suit <-- apres
  fin tant que suit > 0
Fin duModule VisiteDFS
Cet algorithme viendra donc visiter 1/A (quand CV vaut 1) puis ira en 2/B (CV vaudra alors 2) puis passera en 3/C avant d'aller en 6/F puis en 7/G et en 4/D etc. Nous encourageons aussi le lecteur à faire l'exécution à la main, au moins pour les premières visites... Les modules de gestion de la queue sont les suivants 
 Module Initialise
   paramètre FQ
   globale   NbElt
 Début du Module Initialise
   NbElt[ FQ ] <-- 0
 Fin du Module Initialise

 Module Nonvide
   paramètre FQ
   globale   NbElt
   valeur renvoyée res
 Début du Module Nonvide
   res <-- (NbElt[ FQ ] = 0)
 Fin du Module Nonvide
 Module Extrait
   paramètres FQ , Vx
   globale    NbElt, Elt
   locale     i, j
 Début du Module Extrait
   Vx <-- Elt[FQ,1]
   pour j de1à Nbelt[FQ]-1
      i <-- j+1
      Elt[FQ,j] <-- Elt[FQ,i]
   fin pour j de1à Nbelt[FQ]-1
   NbElt[FQ] <-- NbElt[FQ] - 1
 Fin du Module Extrait
Module Metdans
   paramètres FQ , Vx
   globale    NbElt, Elt
 Début du Module Metdans
   NbElt[FQ] <-- NbElt[FQ] + 1
   Elt[ FQ,Nbelt[FQ] ] <-- Vx
 Fin du Module Metdans
Le programme Rexx LitGraph.rex (200 lignes, 6 k) reprend ces différents algorithmes . Outre les affichages déjà présentés, ce programme fournit les résultats suivants : 
Graphe associé au fichier BIGCROIS.GRF
Arc  1  : le sommet   1  est relié au sommet   2
Arc  2  : le sommet   1  est relié au sommet   3
Arc  3  : le sommet   1  est relié au sommet   6
Arc  4  : le sommet   1  est relié au sommet   7
Arc  5  : le sommet   3  est relié au sommet   7
Arc  6  : le sommet   4  est relié au sommet   5
Arc  7  : le sommet   4  est relié au sommet   6
Arc  8  : le sommet   5  est relié au sommet   6
Arc  9  : le sommet   5  est relié au sommet   7
Arc 10  : le sommet   7  est relié au sommet   8


Arc 11  : le sommet   7  est relié au sommet  10
Arc 12  : le sommet   7  est relié au sommet  12
Arc 13  : le sommet   8  est relié au sommet   9
Arc 14  : le sommet  10  est relié au sommet  11
Arc 15  : le sommet  10  est relié au sommet  12
Arc 16  : le sommet  10  est relié au sommet  13
Arc 17  : le sommet  12  est relié au sommet  13

Il y a  17 arcs et  13  sommets
 Parcours DFS  récursif
  A  B  C  G  E  D  F  H  I  J  K  L  M
 Parcours BFS  itératif
  A  B  C  F  G  D  E  H  J  L  I  K  M

2. Applications des graphes à la théorie des jeux

2.1. Chemins et circuits

Dans un graphe orienté G=(S,A) un chemin [x1,x2,...xn] est une suite d'arcs tels que l'extrémité terminale de xi est l'extrémité initiale de xi+1. Par exemple, avec le graphe précédent, [<1,3 >,<3,7 >,<7,8 >] est un chemin qui va de 1 à 8. On peut aussi de décrire comme [2,5,10] car <1,3>est l'arc numéro 2, <3,7 >est l'arc numéro 5 et <7,8>l'arc numéro 10. Un circuit est un chemin qui revient à son point de départ (l'extrémité terminale dur dernier arc est l'extrémité initiale du premier arc). Le chemin [<1,3>,<3,7>,<7,1>] est donc un circuit. La longueur d'un chemin est le nombre d'arcs qui le composent. Le circuit précédent est donc de longueur 3.

2.2. Fonction ordinale de graphe, mex et nombres de Grundy

Si G=(S,A) est un graphe orienté sans circuit et soit O une fonction de S dans *. On dit que f est une fonction ordinale de G ssi il existe un partition de E en r sous-ensembles Nk totalement et strictement ordonnés par la relation Nk * Nk' * k < k' telle que s * Nk * O(s)=k. Les ensembles Nk s'appellent niveaux d'ordre k.

Pour un graphe G orienté, on définit les fonctions successeur et précédent par 

   succ(x) = { y ;  * A } et prec(y) = { x ;  * A }

Deux problèmes classiques sont ainsi posés : 

   - vérifier que le graphe est sans circuit
   - construire les niveaux ou vérifier
     qu'une fonction O définit des niveaux.

Une méthode pour construire une fonction ordinale est la suivante : 

   - on pose    N0 = { s * S ; prec(s) = * }
   - on prend    N1 = { s * S ; prec(s) =  * N0}
   - puis      N2 = { s * S ; prec(s) =  * N0 * N1}
   - plus généralement : Ni = { s * S ; prec(s) =  *  Nk }
r est alors le plus petit entier tel que suc(Nr) = * en posant succ(H) = succ(s).

Le mex d'un ensemble de valeurs (m pour minimum et ex pour excluded) est le plus petit entierpositif ou nul qui n'appartient pas à l'ensemble. Le mex de {0,1,3} est donc 2 ; de même, le mex de {1,2,4,5,6,7} est 0 (revoir le chapitre 4 pour des algorithmes de calcul du mex). Une fonction g de G dans * est un fonction de Grundy ssi g(s) est le plus petit entier positif ou nul qui n'appartient pas à { g(t) } pour t * succ(s). g(s) s'appelle alors nombre de Grundy de G relatif à la fonction g. En d'autres termes, g(s) est le mex de l'ensemble des g(t) pour t * succ(s). Un graphe ne possède pas toujours de fonction de Grundy ; ainsi pour E={x,y,z}, A={,,}, g(x)=0, g(y)=1, g(z) ne peut pas être défini. De même, on peut avoir plusieurs fonctions de Grundy pour un même graphe.

Par exemple, pour E={a,b,c,d1,d2,e} et A={,,,,,}, on peut choisir g telle que 


   g(a)  = 1,
   g(b)  = 0,
   g(c)  = 1,
   g(d1) = g(d2) = 0,
   g(e)  = 1
ou telle que 
   g(a) = 0,
   g(b) = 1,
   g(c) = 0,
   g(d1) = g(d2) = 1,
   g(e) = 0
Une représentation graphique montre ces phénomènes.

La liaison entre les jeux, les graphes et les fonctions de Grundy est la suivante 


- un jeu est  représenté par un graphe  sans cycle
  (sans circuit)
- un  graphe  sans  circuit possède forcément une
  fonction  de  Grundy  -  le  nombre de Grundy
  d'un graphe est celui du sommet-racine du graphe-arbre
- si  ce  nombre  vaut  0,  il  y a une stratégie
  gagnante pour le jeu.
Les problèmes associés à ces définitions, sont : 
   - calculer le mex d'une liste de valeurs
   - construire une fonction de Grundy ou vérifier qu'une fonction est de Grundy
   - expliciter la stratégie gagnante

2.3. Algorithmes pour les fonctions ordinales

La méthode de M. Demoucron (présentée dans l'ouvrage de Kaufman) permet de déterminer soit qu'un graphe possède un circuit, soit de trouver ses niveaux. A partir de la matrice de conectivité, on effectue le total des colonnes. Un 0 dans la ligne ainsi créée indique des sommets sans précédents. On leur affecte le niveau 0 ; on retranche à la ligne des totaux la somme des lignes des sommets sans précédents. Un 0 dans la nouvelle ligne ainsi créée indique des sommets désormais sans précédents. On leur affecte le niveau 1 et on itère le processus. Lorsque tous les sommets ont été utilisés, soit il reste au moins une valeur non nulle et le graphe possède un circuit, soit on n'obtient que des 0 et les niveaux ont été construits.

Exemple : soit le graphe représenté par

La matrice de connectivité pour ce graphe est 

     A  B  C  D  E  F  G  H  I  J  K  L  M  N
  +--------------------------------------------+
A ¦        1                             1     ¦
B ¦                                      1     ¦
C ¦                                            ¦
D ¦        1                                   ¦
E ¦        1                 1  1              ¦
F ¦           1                    1  1  1     ¦
G ¦                                1           ¦
H ¦     1     1     1  1                       ¦
I ¦  1                                      1  ¦
J ¦  1                 1              1        ¦
K ¦        1                                   ¦
L ¦                                            ¦
M ¦        1                                   ¦
N ¦                 1                          ¦
  +--------------------------------------------+

La ligne des totaux en colonne vaut

  L1   ¦  2  1  5  2  0  2  2  0  1  1  2  2  3  1

On met donc E et H au niveau 0. Si on soustrait à L1 la somme des lignes E et H on obtient 

  L2   ¦  2  0  4  1  x  1  1  x  0  0  2  2  3  1

Le niveau 1 contient donc B, I et J. Si on soustrait à L2la somme des lignes B,I,H on obtient 

  L3   ¦  0  x  4  1  x  1  0  x  x  x  2  1  2  0
etc. Finalement, les niveaux sont constitués comme suit 
Niveau    0   :   E   H
   1   :   B   I   J
   2   :   A   G   N
   3   :   F
   4   :   D   K   L   M
   5   :   C
La programmation de la détermination des niveaux (ou de la présence d'un circuit) se fait donc très simplement ; la seule précaution à prendre concerne les arcs puisqu'il s'agit ici de graphes orientés.

Fidèle à nos habitudes, nous utiliserons comme structures de données descriptives des tableaux, y compris pour les listes liées des niveaux. Comme le montreront les implémentations en Rex et en Pascal, ce choix ne gêne ne pas la traduction. Nous nous sommes permis une seule simplification, sachant le petit nombre sommets : les noms de sommets sont concaténés dans une variable de type chaîne, ce qui facilite le test de présence d'un nom de sommet. Un lecteur plus exigeant pourra réécrire les instructions liées à NomSom sous forme d'instructions en tableau.

2.3.1. Module principal :

{ # 1. Initialisation des variables et structures }
   NbNiv      * 0   { Niveau courant puis nombre de niveaux }
   NbArc      * 0   { Arc    courant puis nombre d' arcs    }
   NbSom      * 0   { Sommet courant puis nombre de sommets }
   NbSrestant * 0   { nombre de sommets actuellement sans niveaux }
   NomSom     * ''  { Liste des noms de sommets }
   FichA      * 'Grundys.Arc' { Fichier des Arcs }
   InitVec(LigneT)     { Ligne des Totaux }
   InitMat(Connec)     { Matrice de connecticité }
   InitLst(Niveau)     { Listes liées des éléments par niveaux }
   InitVecAl(NumS)     { Numéro des sommets, Al comme Alphanumérique }
   ConstruireMatC {la matrice de connectivité à partir du fichier des arcs}
   TotalColonne   {initialise la Ligne des Totaux et NbSrestant}

{ # 2. Détermination des niveaux par la méthode de Moucron }
    tant que nbSrestant > 0 { nombre de Sommets restant }
       SupprimeSetCreeN
       { supprime les sommets isolés et crée les niveaux }
    fintant que nbSrestant > 0
{ # 3. Affichages des résultats }
 écrire "Graphe orienté associé au fichier Grundy.Arc "
 écrire " avec : ",nbsom," sommet(s) ",nbarc,
 écrire  " arc(s) ",nbniv," niveau(x) "
 afficheMatConnec

2.3.2. Détail des modules importants :

Pour construire la matric de connectivité Connec à partir du fichier physique Ficha de nom FichArc, on utilise la méthode suivante : on lit séquentiellement les lignes ; dés que la ligne lignarc est lue dans le fichier, on incrémente le nombre d'arcs et on découpe lignarc en orig et dest, noms des sommets qui composent l'arc ; on vient ensuite rajouter si besoin est ces noms à NomSom qui contient la liste de tous les noms de sommets, gérant au passage le nombre NbSom de sommets et le tableau NumS des noms de sommets.

Nous utilisons trois fonctions dans le module de construction : 

   Decoupe,
   pos
   NumSom.

Decoupe(chA,chB,chC) vient décomposer la chaine chA en mots ; chB est le premier mot, chC est le deuxième ; les mots sont séparés par des espaces blancs. pos(chA,chB) est une fonction classique qui renvoie la position de chA dans chB ou 0. Enfin, NumSom(chA,chB) donne le numéro du mot (ou sommet) chA dans la chaine chB (liste des sommets) ; on notera que cette fonction est sûre d'aboutir, de par notre construction. Réutiliser cette fonction hors de son contexte serait donc dangereux. 

module ConstruireMatC {du fichier des arcs vers la matrice de connectivité}
 variables locales  lignarc,orig,dest {ligne et noms},
                    norig,ndest {numéros}
 variables globales Ficha, FichArc, NbArc, Connec {matrice},
                    NbSom, NomSom {liste des noms}, NumS {tableau des noms}
début de module ConstruireMatC
  ouvrir Ficha comme Ficharc
  NbArc * 0
  tant que non fin de fichier sur Ficharc
       lire lignarc sur Ficharc
       Decoupe(lignarc,orig,dest)
       NbArc * NbArc  + 1
       si pos(orig,NomSom) = 0 alors
          NbSom       * NbSom + 1
          NomSom      * NomSom + ' ' + orig + ' '
          NumS[NbSom] * orig
       finsi pos(orig,nomsom) = 0
       si pos(dest,NomSom) = 0 alors
          NbSom       * NbSom + 1
          NomSom      * NomSom + ' ' + dest + ' '
          NumS[NbSom] * dest
       finsi pos(dest,nomsom) = 0
       norig * NumSom(orig,NomSom)
       ndest * NumSom(dest,NomSom)
       Connec[norig,ndest] * 1
  fintant que non fin de fichier
fin de module ConstruireMatC
Le deuxième module est celui qui initialise LigneT, liste des totaux en colonne et le nombre NbSrestant de sommets auxquels on n'a pas encore attribué de niveau. L'initialisation de Nbsrestant se fait en testant si le nombre de niveaux est nul. Pour LigneT, un parcours de chacun des numéros de sommets noté so en tant qu'indice de ligne dans la matrice connec suffit : on fait alors le total de la colonne so. Notre implémentation teste s'il y a un 1 dans connec. Ce module est donc utilisable si les arcs sont comptabilisés en (0,1) ou en (-1,1) dans la matrice de connectivité, ce qui n'aurait pas été le cas si on avait le total inconditionnel des éléments de la colonne so. 
module TotalColonne { initialise la Ligne des Totaux et nbrestant }
 variables locales  so,sd, somcol
 variables globales NbNiv, Connec { matrice }, NbSrestant, NbSom
début de module TotalColonne
 si Nbniv = 0 alors
    NbSrestant * NbSom
 finsi Nbniv = 0
 pour so de1a NbSom
     somcol * 0
     pour sd de1a nbsom
         si Connec[sd,so] = 1 alors
            somcol * somcol + Connec[sd,so]
         finsi Connec[sd,so] = 1
     finpour sd
     LigneT[so] * somcol
 finpour so
fin de module TotalColonne
Pour supprimer un sommet et lui attribuer un niveau, on commence par incrémenter le nombre de niveau. Ensuite, on cherche un sommet isolé : il correspond à un indice s tel que LigneT[s] est nul. On cherche alors où insérer ce sommet au niveau NbNiv ; on nomme ps cette position. Il reste alors à calculer dans totc le total de la colonne s et à décrémenter le nombre de sommets restants. 
module SupprimeSetCreeN {supprime les sommets isolés et crée les niveaux}
 variables locales  totc    {vecteur total colonne }
                    s,sc,ps {numéros de sommets}
variables globales  NbNiv, NbSom, LigneT, Niveau, Connec, NbSrestant
début module SupprimeSetCreeN
 NbNiv * NbNiv + 1
 initvec(totc)
 pour s de1a NbSom
     si LigneT[s] = 0 alors
         ps * poslibre(NbNiv)
         Niveau[NbNiv,ps] * nums[s]
         pour sc de1a NbSom
             si Connec[s,sc] = 1 alors
                totc[sc] * totc[sc] + 1
             finsi connec[s,sc] = 1
         finpour sc
         NbSrestant * NbSrestant - 1
         LigneT[s]  * -1
     finsi lignet[s] = 0
 finpour s
 pour s de1a NbSom
     LigneT[s] * LigneT[s] - totc[s]
 finpour s
fin module SupprimeSetCreeN
Ce module utilise deux sous-modules : 
   InitVec
   PosLibre (qui est une fonction).
InitVec(vct) vient initialiser le vecteur vct ; PosLibre(niv) renvoie l'indice du premier élément nonul de la ligne niv du tableau global Niveau. De façon à être complet, nous fournissons le détail de tous les modules élémentaires. Chacun des tableaux est supposé avoir au moins NbElt cases.

2.3.3. Autres modules

Module InitVec { met à zéro tous les éléments du paramètre }
 paramètre vecLig { vecteur, par adresse }
 locale    ind
 globale   (aucune)
debut Module InitVec
  pour ind de1a nbelt
      vecLig[ind] * 0
  finpour ind
fin Module InitVec

Module InitVecAl { met à chaîne vide tous les éléments du paramètre }
 paramètre vecLigAl { vecteur, par adresse }
 locale    indAl
 globale (aucune)
debut Module InitVec
  pour indAL de1a nbelt
      vecLigAl[indAl] * ''
  finpour indAl
fin Module InitVec

Module InitMat { met à zéro tous les éléments du paramètre-matrice }
 paramètre Cnec      { matrice, par adresse           }
 locales   indl,indc { indices de ligne et de colonne }
 globale (aucune)
debut Module InitVec
  pour indl de1a nbelt
      pour indc de1a nbelt
           Cnec[indl,indc] * 0
      finpour indc
  finpour indl
fin Module InitVec

Module ecritniveau    { renvoie une chaine       }
  paramètre n         { numéro de niveau, entier }
  locales   indniv    { indice de niveau         }
            sort      { phrase renvoyée          }
  globale   Niveau    { matrice des listes liées des niveaux }
début de module ecritniveau
  indniv * 1
  sort * ''
  tant que Niveau[n,indniv] <> '?'
    sort * sort + ' ' + Niveau[n,indniv]
    inc(indniv)
  fintant que
  renvoyer sort
fin de module ecritniveau

module LesNiveaux { affiche les niveaux }
  paramètre       (aucun)
  locale          son    { numéro de niveau }
  globale indirecte    Niveau { matrice des listes liées des niveaux }
début de module LesNiveaux
    pour son de1a nbelt
        écrire" niveau ",son," " ,ecritniveau(son)
    finpour son
fin de module LesNiveaux

Module InitLst
 paramètre niv         { listes liées implémentée en matrice }
 locales   indn,indel  { indices de ligne et de colonne      }
 globale   (aucune)
debut module InitLst
     pour indn de1a Nbelt do début
         pour indel de1a Nbelt do début
             niv[indn,indel] * '?'
         finpour indel
     finpour indn
fin module InitLst

module decoupe { la phrase en deux mots nommés preume et deuze }
   paramètres  phr          { chaine,  par valeur }
               preum,deuze  { chaines, par adresse }
   locales     indcar
               longn
               deb,fin
   globale     (aucune)
   fonctions utilisées : Longueur, SousChaine
 début module decoupe
   phr    * phr + ' ? ?? '
   longn  * longueur(phr)
   indcar * 1
   tant que phr[indcar] =  ' '
        indcar * indcar + 1
        deb    * indcar
   fintant que phr[indcar] =  ' '
   tant que phr[indcar] <> ' '
        indcar * indcar + 1
        fin    * indcar
   fintant que phr[indcar] <> ' '
   preum * SousChaine(phr,deb,fin-deb)
   tant que phr[indcar] =  ' '
        indcar * indcar + 1
        deb    * indcar
   fintant que phr[indcar] =  ' '
   tant que phr[indcar] <> ' '
        indcar * indcar + 1
        fin    * indcar
   fintant que phr[indcar] <> ' '
   deuze * SousChaine(phr,deb,fin-deb)
 fin module decoupe


module poslibre { renvoie l'indice du premier élément non nul de la ligne
                  dont le numéro est passé en paramètre }
  paramètre  nv
  locale     iv
  globale   Niveau    { matrice des listes liées des niveaux }
début module poslibre
  iv * 1
  tant que Niveau[nv,iv] <> '?'
        iv * iv + 1
  fintant que
  renvoyer iv
fin module poslibre

module affLignet { affiche la ligne des Totaux }
 paramètre  (aucun)
 locale      s
 globale     LigneT { liste des totaux }
 fonction utilisée : Mécrire { écrire sans passer à la ligne }
début module affLignet
 mécrire " niveau ", nbniv, " : "
 pour s de1a nbsom
    mécrire LigneT[s] { sur 3 caractères }
 finpour s
fin module affLignet


module NumSom { renvoie le nuémro de sommet, entier
                c'est à dire le numéro du mot aig dans la phrase bfoin }
 paramètres   aig      { chaine, "aiguille" - needle }
              bfoin    { chaine, "botte de foin " - haystack }
 locales      ic       { indice de caractère }
              im       { indice du mot, valeur renvoyée }
              long     { longueur de la botte }
              deb,fin  { indices de début et fin de mot }
              mot      { mot courant }
 globale      (aucune)
 fonctions utilisées : Longueur, SousChaine
début module NumSom
 ic * 1
 im * 0
 bfoin  * ' ' + bfoin + aig + '??? '
 longc  * longueur(bfoin)
 tant que ic <= longc
   tant que bfoin[ic] =  ' '
        ic  * ic+1
     deb * ic
        im  * im + 1
   fintant que bfoin[ic] = ' '
   tant que bfoin[ic] <> ' '
        ic  * ic+1
        fin * ic
        mot * SousChaine(bfoin,deb,fin-deb)
   fintant que bfoin[ic] <> ' '
   si mot = aig alors
      ic * longc + 1
   finsi mot = aig
 fintantque ic <= longc
 renvoyer im
fin de module NumSom

module afficheMatConnec  {affiche la matrice de connecticité, les niveaux}
  paramètre (aucun)
  locales    s,so,sd {indices de numéros de sommet}
             nso     { chaine, nom de sommet      }
  globales   NumS, Connec, Niveau { indirect }
  fonctions utilisées : Mécrire { écrire sans passer à la ligne }
                        EcritNiveau
début module afficheMatConnec
 mécrire "   '
 pour s de1a NbSom
      mécrire " ",NumS[s]," "
 finpour s
 écrire"      Niveaux "
 pour so de1a nbsom
    nso * NumS[s]
    mécriren so, " "
    pour sd de1a NbSom
       si Connec[so,sd] = 1
          alors mécrire  " 1 "
          sinon mécrire  "   "
    finpour sd
    si so <= nbniv
       alors écrire "     ",so," : ", EcritNiveau(so)
       sinon écrire
    finsi so <= nbniv
 finpour
finmodule afficheMatConnec

2.3.4. Exemple de sortie

A partir du fichier Grundys.Arc dont le contenu est :
      A C
      A M
      B M
      D C
      E C
      E I
      E J
      F D
      F K
      F L
      F M
      G K
      H B
      H D
      H F
      H G
      I A
      I N
      J A
      J G
      J L
      K C
      M C
      N F
On obtient comme sortie : (l'ordre des sommets correspond à l'ordre de lecture des arcs) 
    niveau  1  :   2  4  3  0  1 -1  0  0  1  2  2  1 -1  1
    niveau  2  :   0  4  2 -1  1 -1 -1 -1  1  2  1  0 -1  0
    niveau  3  :  -1  3  1 -1  1 -1 -1 -1  0  1  1 -1 -1 -1
    niveau  4  :  -1  3  0 -1  0 -1 -1 -1 -1  0  0 -1 -1 -1
    niveau  5  :  -1  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    niveau  6  :  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

    Graphe orienté associé au fichier Grundy.Arc
    avec :  14     sommet(s)  24  arc(s)  6  niveau(x)

       A  C  M  B  D  E  I  J  F  K  L  G  H  N     Niveaux
   A      1  1                                        1  :   E H
   C                                                  2  :   B I J
   M      1                                           3  :   A G N
   B         1                                        4  :   F
   D      1                                           5  :   M D K L
   E      1              1  1                         6  :   C
   I   1                                      1
   J   1                             1  1
   F         1     1              1  1
   K      1
   L
   G                              1
   H            1  1           1        1
   N                           1

2.3.5. Implémentation en Pascal

Le programme Grundys.Pas fait à peu près 270 lignes et 8 k.

2.3.6. Implémentation en Rexx

Le programme Grundys.Rex fait à peu près 130 lignes et 4 k.