Niveaux d'un graphe sans circuit et arborescence

Dans un graphe sans circuit, le niveau d'un sommet est la longueur du plus long chemin qui arrive à ce sommet : les sommets sans prédécesseur sont au niveau 0, ceux qui n'ont que des prédécesseurs de niveau 0 au niveau 1, et ainsi de suite. Ranger les sommets par niveaux permet de dessiner le graphe proprement, de gauche à droite, avec toutes les flèches dans le même sens, et donne l'ordre dans lequel traiter des tâches qui dépendent les unes des autres. Ce chapitre donne la méthode pour déterminer les niveaux, la représentation par niveaux, le lien avec les chemins hamiltoniens, puis la notion d'arborescence.

Pourquoi « sans circuit » ?

Les niveaux n'existent que si le graphe n'a aucun circuit. Dans un circuit comme (A, B, A), A devrait être après B et B après A : impossible de les ranger. Un graphe sans circuit, en revanche, peut toujours être rangé : il a au moins une source (un sommet sans prédécesseur), sinon on pourrait remonter de prédécesseur en prédécesseur indéfiniment et on finirait par repasser par un sommet, c'est-à-dire par trouver un circuit.

Le graphe G du ticket a des circuits : il n'a pas de niveaux. Les exemples de ce chapitre sont des graphes de dépendances, sans circuit par nature.

Définition du niveau d'un sommet

Dans un graphe sans circuit :

• les sommets sans prédécesseur (les sources) sont de niveau 0 ;
• un sommet est de niveau k quand le plus long chemin qui arrive à lui, en partant d'une source, a pour longueur k.

Concrètement, on ne calcule pas les plus longs chemins : on « épluche » le graphe. On retire les sommets de niveau 0 ; dans ce qui reste, les nouveaux sommets sans prédécesseur sont de niveau 1 ; on les retire à leur tour ; les nouveaux sommets sans prédécesseur sont de niveau 2, etc.

La méthode du tableau des prédécesseurs

Exemple : un pipeline d'intégration continue. À chaque modification du code d'une application, un serveur exécute ces étapes :

On dresse un tableau : une ligne par sommet avec ses prédécesseurs, puis une colonne par niveau. À chaque étape, on raye les sommets déjà classés dans les listes de prédécesseurs ; les sommets dont la liste est vide entrent dans le niveau suivant.

Le raisonnement, étape par étape :

1. Niveau 0 : seul A n'a pas de prédécesseur. N₀ = {A}.
2. On raye A. B n'a plus de prédécesseur non classé. N₁ = {B}.
3. On raye B. C et E n'ont plus de prédécesseur non classé. N₂ = {C, E}.
4. On raye C et E. D et F sont libres ; G attend encore D et F. N₃ = {D, F}.
5. On raye D et F. N₄ = {G}.

Tous les sommets sont classés : le graphe est sans circuit, et ses niveaux sont N₀ = {A}, N₁ = {B}, N₂ = {C, E}, N₃ = {D, F}, N₄ = {G}.

La représentation par niveaux

On dessine les niveaux en colonnes, de gauche à droite (ou en lignes, de haut en bas), et on place les arcs. Toutes les flèches vont alors d'un niveau vers un niveau plus grand : le dessin se lit dans un seul sens, sans croisement inutile.

Ce que la représentation apprend. Deux sommets d'un même niveau ne sont jamais reliés par un arc : ils ne dépendent pas l'un de l'autre. Dans le pipeline, l'analyse de qualité (E) peut tourner en parallèle de la compilation (C), et les tests (D) en parallèle de la construction de l'image (F). Le nombre de niveaux, 5, est le nombre minimal de « vagues » successives pour tout exécuter, même avec autant de serveurs qu'on veut.

Lire les sommets niveau par niveau (A, B, C, E, D, F, G) donne un ordre dans lequel chaque sommet vient après tous ses prédécesseurs. Les informaticiens appellent cela un tri topologique : c'est l'ordre dans lequel un gestionnaire de paquets installe les dépendances, ou dans lequel un outil comme make ou un orchestrateur de pipeline lance ses tâches.

Niveaux et chemin hamiltonien

Dans un graphe sans circuit, le niveau maximal est la longueur du plus long chemin du graphe. Un chemin hamiltonien, qui passe par les n sommets, a n − 1 arcs : s'il existe, le plus long chemin a n − 1 arcs, il y a donc n niveaux (0 à n − 1) pour n sommets, soit un sommet par niveau. Inversement, s'il y a un sommet par niveau, le sommet du dernier niveau est au bout d'un chemin de longueur n − 1, qui passe forcément par les n sommets.

Le pipeline a deux sommets aux niveaux 2 et 3 : il n'a pas de chemin hamiltonien. On ne peut pas enchaîner toutes les étapes en une seule file en suivant les arcs : C et E, par exemple, ne sont reliés dans aucun sens.

Exemple avec chemin hamiltonien. Le graphe de sommets A, B, C, D, E et de prédécesseurs Γ⁻(A) = {C}, Γ⁻(B) = ∅, Γ⁻(C) = {B}, Γ⁻(D) = {A, C}, Γ⁻(E) = {B, D} a pour niveaux N₀ = {B}, N₁ = {C}, N₂ = {A}, N₃ = {D}, N₄ = {E}. Un sommet par niveau : le chemin hamiltonien est (B, C, A, D, E), et on vérifie que les arcs B → C, C → A, A → D et D → E existent.

Les arborescences

Une arborescence est un graphe orienté qui a un sommet particulier, la racine, tel que :

• la racine n'a aucun prédécesseur ;
• tout autre sommet a exactement un prédécesseur ;
• tout sommet peut être atteint depuis la racine.

De façon équivalente, il existe un et un seul chemin de la racine vers chaque autre sommet. Une arborescence n'a donc pas de circuit, et ses niveaux sont simplement les distances à la racine : la racine au niveau 0, ses successeurs au niveau 1, etc.

Le vocabulaire vient de la généalogie et de la botanique : le prédécesseur d'un sommet est son père (ou parent), ses successeurs sont ses fils (ou enfants), et les sommets sans successeur sont les feuilles.

L'arborescence des fichiers est l'exemple que tu manipules tous les jours : le chemin absolu d'un fichier, comme /var/log, est exactement l'unique chemin de la racine vers ce sommet. On rencontre aussi des arborescences dans :

• le DNS : la racine, puis les domaines de premier niveau (fr, com), puis les domaines (exemple.fr), puis les sous-domaines ;
• l'Active Directory : le domaine, ses unités d'organisation, leurs sous-unités et leurs objets ;
• une page web : l'arbre DOM des balises HTML, chaque balise ayant une seule balise parente ;
• un organigramme hiérarchique, où chacun a un seul supérieur direct.

En Python : calculer les niveaux

def niveaux(predecesseurs):
    """Renvoie la liste des niveaux, ou None si le graphe a un circuit."""
    restants = dict(predecesseurs)          # sommet -> liste de prédécesseurs
    classes = set()
    resultat = []
    while restants:
        niveau = sorted(x for x, preds in restants.items()
                        if all(p in classes for p in preds))
        if not niveau:                      # plus aucun sommet libre : circuit
            return None
        resultat.append(niveau)
        classes.update(niveau)
        for x in niveau:
            del restants[x]
    return resultat

pipeline = {"A": [], "B": ["A"], "C": ["B"], "D": ["C"],
            "E": ["B"], "F": ["C"], "G": ["D", "E", "F"]}
print(niveaux(pipeline))
# [['A'], ['B'], ['C', 'E'], ['D', 'F'], ['G']]

C'est la traduction directe de la méthode du tableau. Le cas None correspond à l'étape où plus aucun sommet n'est libre : un circuit bloque le classement.

Exercices