Repérez les composantes fortement connexes

Sur un site web, certaines pages se renvoient les unes aux autres, et d’autres sont des culs-de-sac : une fois arrivé, impossible de revenir. Dans un graphe orienté, « être relié » ne suffit plus, il faut savoir si l’on peut aller et revenir. C’est la notion de forte connexité.

Dans ce chapitre, vous allez apprendre à calculer tout ce qui est accessible depuis chaque sommet (la fermeture transitive), puis à découper un graphe orienté en blocs où tout le monde peut atteindre tout le monde. Notre fil rouge : un petit site web de sept pages.

Le fil rouge : un site de sept pages

Les pages du site sont numérotées : 1 accueil, 2 blog, 3 article, 4 catalogue, 5 fiche produit, 6 avis clients, 7 mentions légales. Un arc $(x, y)$ signifie « la page $x$ contient un lien vers la page $y$ » :

1 → 2, 2 → 3, 3 → 1, 2 → 4, 4 → 5, 5 → 6, 6 → 4, 6 → 7, 3 → 7.

Un internaute qui arrive sur l’accueil peut-il atteindre les avis clients ? Et revenir ensuite à l’accueil en suivant des liens ? Les cadres en pointillés donnent déjà la réponse, mais voyons comment un algorithme la trouve.

Descendants, ascendants et forte connexité

Qui peut atteindre qui ?

Pour un sommet $x$ :

ses descendants $\text{Desc}(x)$ sont les sommets qu’on peut atteindre depuis $x$ par un chemin ;
ses ascendants $\text{Asc}(x)$ sont les sommets depuis lesquels on peut atteindre $x$ .

Les descendants s’obtiennent par un simple parcours (BFS ou DFS) depuis $x$ , les ascendants par un parcours sur le graphe inversé (chaque arc retourné). Pour la page 4, $\text{Desc}(4) = \lbrace 4, 5, 6, 7 \rbrace$ et $\text{Asc}(4) = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$ .

Forte connexité

Un graphe orienté est fortement connexe si, pour toute paire de sommets $x$ et $y$ , il existe un chemin de $x$ à $y$ et un chemin de $y$ à $x$ . Le réseau de navettes du chapitre 1 l’est ; notre site ne l’est pas (depuis la page 7, on ne va nulle part).

Comme pour la connexité simple, « $x$ et $y$ s’atteignent mutuellement » est une relation d’équivalence. Ses classes sont les composantes fortement connexes (CFC, strongly connected components). Et elles se calculent très simplement à partir des deux ensembles précédents :

\text{CFC}(x) = \text{Desc}(x) \cap \text{Asc}(x)

en convenant que $x$ appartient à ses propres descendants et ascendants. En mots : la composante de $x$ contient les sommets qu’il atteint et qui l’atteignent.

La composante de 4 est ce que 4 atteint et qui l'atteint en retour : l'intersection des deux ensembles.

Un graphe orienté possède aussi des notions plus faibles. Un sommet $r$ est une racine s’il atteint tous les autres (ici, 1, 2 et 3 en sont). Un graphe est quasi fortement connexe si, pour toute paire $x, y$ , un même sommet $z$ atteint à la fois $x$ et $y$ ; on montre qu’un graphe fini admet une racine si et seulement s’il est quasi fortement connexe.

La fermeture transitive et l’algorithme de Roy-Warshall

Tout calculer d’un coup

Plutôt que de lancer un parcours par sommet, on peut calculer en une fois toutes les relations d’accessibilité. La fermeture transitive de $G$ , notée $G^+$ , est le graphe qui a un arc $(x, y)$ dès qu’il existe un chemin (d’au moins un arc) de $x$ à $y$ dans $G$ .

L’algorithme de Roy-Warshall la calcule sur la matrice d’adjacence $M$ , avec une idée simple : on autorise progressivement les chemins à passer par les sommets 1, puis 1 et 2, puis 1, 2 et 3, etc.

pour k de 1 à n :
    pour tout x tel que M[x, k] = 1 :        (x atteint k)
        pour tout y tel que M[k, y] = 1 :    (k atteint y)
            M[x, y] ← 1                       (donc x atteint y, en passant par k)

Après l’étape $k$ , $M[x, y] = 1$ si et seulement s’il existe un chemin de $x$ à $y$ dont tous les sommets intermédiaires sont parmi $1, \dots, k$ . À la fin ( $k = n$ ), plus aucune restriction : on a la fermeture transitive. Trois boucles imbriquées sur $n$ : la complexité est en $O(n^3)$ .

Déroulons les premières étapes sur notre site.

$k = 1$ : seul 3 a un arc vers 1, et 1 n’a qu’un successeur, 2. On ajoute $(3, 2)$ : l’article mène au blog, via l’accueil.
$k = 2$ : 1 et 3 atteignent maintenant 2, qui atteint 3 et 4. On ajoute $(1, 3)$ , $(1, 4)$ , $(3, 3)$ et $(3, 4)$ . Le 1 sur la diagonale en $(3, 3)$ signifie que 3 est sur un circuit.
$k = 3$ : on ajoute $(1, 1)$ , $(1, 7)$ , $(2, 1)$ , $(2, 2)$ et $(2, 7)$ .
Les étapes $k = 4, 5, 6$ complètent le bloc $\lbrace 4, 5, 6 \rbrace$ et ses liens vers 7 ; l’étape $k = 7$ n’ajoute rien, puisque 7 n’a aucun successeur.

La matrice finale $M^+$ est :

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	1	1	1	1
3	1	1	1	1	1	1	1
4	0	0	0	1	1	1	1
5	0	0	0	1	1	1	1
6	0	0	0	1	1	1	1
7	0	0	0	0	0	0	0

def roy_warshall(M):
    """Fermeture transitive d'une matrice d'adjacence (liste de listes de 0/1)."""
    n = len(M)
    F = [ligne[:] for ligne in M]          # copie : on ne modifie pas l'original
    for k in range(n):
        for x in range(n):
            if F[x][k]:                     # x atteint k
                for y in range(n):
                    if F[k][y]:             # k atteint y
                        F[x][y] = 1
    return F

Chaque étape k ajoute les couples reliés en passant par k. Le bloc de 1 en haut (pages 1 à 3) et le bloc 4 à 6 font apparaître les composantes.

Une même boucle, beaucoup d’usages

La structure de Roy-Warshall est bien plus générale qu’il n’y paraît. Si la matrice contient des valeurs (des longueurs) au lieu de 0 et 1, et que l’on remplace « ou » par « min » et « et » par « + », la mise à jour devient :

v(x, y) \leftarrow \min\big(v(x, y),\; v(x, k) + v(k, y)\big)

où $v(x, y)$ est la meilleure longueur connue d’un chemin de $x$ à $y$ . On obtient alors les plus courts chemins entre tous les couples : c’est l’algorithme de Floyd-Warshall du chapitre 7. Avec (max, +), on obtient les plus longs chemins (utiles en ordonnancement, sur un graphe sans circuit) ; avec (max, min), le chemin de plus grande capacité. Les sujets d’examen demandent volontiers d’adapter Roy-Warshall à un nouveau problème : il suffit de dire ce que représente $v(x, y)$ et comment combiner deux demi-chemins.

Calculer les composantes fortement connexes

La méthode de Foulkes, par la fermeture transitive

Une fois $M^+$ calculée, les composantes se lisent directement. Deux sommets distincts $x$ et $y$ sont dans la même CFC si et seulement si $M^+[x, y] = M^+[y, x] = 1$ . Il suffit donc de comparer la matrice à sa transposée : les lignes 1, 2 et 3 s’atteignent mutuellement, de même que 4, 5 et 6, et 7 reste seul. C’est la méthode vue en cours (algorithme de Foulkes). Elle est simple à dérouler à la main, mais coûte $O(n^3)$ à cause de la fermeture transitive.

Les algorithmes linéaires : Tarjan et Kosaraju

Pour de grands graphes, on utilise des algorithmes en $O(n + m)$ , fondés sur le DFS du chapitre 2 (ce sont des compléments standard, hors du cours magistral) :

Kosaraju fait deux DFS : un premier sur $G$ pour ordonner les sommets par date de fin décroissante, puis un second sur le graphe inversé, dans cet ordre. Chaque arbre du second parcours est une CFC.
Tarjan n’en fait qu’un, en maintenant pour chaque sommet le plus petit numéro de visite qu’il peut atteindre ; un sommet dont ce numéro est le sien est la « tête » d’une composante.

Le graphe réduit

Si l’on contracte chaque CFC en un seul sommet, en gardant un arc entre deux composantes dès qu’un arc les relie dans $G$ , on obtient le graphe réduit (ou condensation). Pour notre site : $C_1 = \lbrace 1, 2, 3 \rbrace$ , $C_2 = \lbrace 4, 5, 6 \rbrace$ , $C_3 = \lbrace 7 \rbrace$ , avec les arcs $C_1 \to C_2$ (grâce à 2 → 4), $C_2 \to C_3$ (6 → 7) et $C_1 \to C_3$ (3 → 7).

Chaque composante devient un seul sommet ; les arcs qui restent (en blanc à gauche) relient les composantes et ne forment aucun circuit.

Cette dernière propriété est précieuse : tout graphe orienté se décompose en blocs « circulaires » reliés par une structure sans circuit, que l’on sait traiter efficacement (chapitre 4).

Enfin, on appelle graphe τ-minimal (tau-minimal) un graphe partiel de $G$ qui a la même fermeture transitive avec le moins d’arcs possible. Ici, l’arc 3 → 7 est superflu (on atteint déjà 7 par 3 → 1 → 2 → 4 → 5 → 6 → 7) : les 8 autres arcs forment un graphe τ-minimal. C’est l’idée d’une « réduction transitive » : ne garder que les liens indispensables.

L'arc 3 → 7 n'apporte aucune accessibilité nouvelle : le retirer ne change pas la fermeture transitive.

import networkx as nx

site = nx.DiGraph([(1, 2), (2, 3), (3, 1), (2, 4), (4, 5),
                   (5, 6), (6, 4), (6, 7), (3, 7)])
print(list(nx.strongly_connected_components(site)))   # [{7}, {4, 5, 6}, {1, 2, 3}]
reduit = nx.condensation(site)                         # graphe réduit, sans circuit
print(nx.is_directed_acyclic_graph(reduit))            # True
fermeture = nx.transitive_closure(site, reflexive=False)
print(sorted(fermeture.successors(4)))                 # [4, 5, 6, 7]

En résumé

Dans un graphe orienté, $\text{Desc}(x)$ et $\text{Asc}(x)$ sont les sommets atteints depuis $x$ et ceux qui atteignent $x$ ; un parcours suffit à les calculer.
Un graphe est fortement connexe si tout sommet atteint tout autre ; ses classes sont les composantes fortement connexes, $\text{CFC}(x) = \text{Desc}(x) \cap \text{Asc}(x)$ .
La fermeture transitive se calcule par Roy-Warshall en $O(n^3)$ , en autorisant progressivement les sommets intermédiaires $1, \dots, k$ (boucle sur $k$ à l’extérieur).
Roy-Warshall se généralise en changeant les opérations : (min, +) donne les plus courts chemins entre tous les couples.
Méthode de Foulkes : $x$ et $y$ sont dans la même CFC si $M^+[x, y] = M^+[y, x] = 1$ ; Tarjan et Kosaraju font la même chose en $O(n + m)$ .
Le graphe réduit est toujours sans circuit.

Exercices

Exercice · Lire des composantes dans une fermeture

facile

On ajoute au site un lien de la page 7 (mentions légales) vers la page 1 (accueil). Quelles sont les nouvelles composantes fortement connexes ? Le graphe devient-il fortement connexe ?

Voir la solution

Depuis 7, on atteint maintenant 1, donc tout le bloc $\lbrace 1, 2, 3 \rbrace$ , puis $\lbrace 4, 5, 6 \rbrace$ par 2 → 4. Et tous les sommets atteignaient déjà 7 (1, 2, 3 par 3 → 7 ; 4, 5, 6 par 6 → 7). Donc tout sommet atteint tout autre en passant par 7 : il n’y a plus qu’une seule composante, $\lbrace 1, \dots, 7 \rbrace$ , et le graphe est fortement connexe. Un seul arc bien placé a suffi, parce que le graphe réduit était une chaîne $C_1 \to C_2 \to C_3$ : relier la dernière composante à la première referme tout.

En code

Python
R

def descendants(graphe, x):
    """Sommets atteignables depuis x (x compris), par un parcours en profondeur."""
    vu, pile = {x}, [x]
    while pile:
        for y in graphe[pile.pop()]:
            if y not in vu:
                vu.add(y)
                pile.append(y)
    return vu

def cfc(graphe):
    inverse = {x: [] for x in graphe}          # graphe inversé, pour les ascendants
    for x in graphe:
        for y in graphe[x]:
            inverse[y].append(x)
    blocs, classes = [], set()
    for x in graphe:
        if x not in classes:
            bloc = descendants(graphe, x) & descendants(inverse, x)   # Desc(x) ∩ Asc(x)
            blocs.append(sorted(bloc))
            classes |= bloc
    return blocs

site = {1: [2], 2: [3, 4], 3: [1, 7], 4: [5], 5: [6], 6: [4, 7], 7: []}
print(cfc(site))     # [[1, 2, 3], [4, 5, 6], [7]]
site[7] = [1]        # nouveau lien 7 -> 1
print(cfc(site))     # [[1, 2, 3, 4, 5, 6, 7]] : fortement connexe

roy_warshall <- function(M) {
  for (k in 1:nrow(M)) for (x in 1:nrow(M))
    if (M[x, k] == 1) M[x, M[k, ] == 1] <- 1     # x atteint k, et k atteint ces y
  M
}
cfc <- function(M) {                             # méthode de Foulkes
  F <- roy_warshall(M)
  mutuel <- (F == 1 & t(F) == 1) | diag(nrow(M)) == 1
  unique(lapply(1:nrow(M), function(x) which(mutuel[x, ])))
}

arcs <- rbind(c(1, 2), c(2, 3), c(3, 1), c(2, 4), c(4, 5), c(5, 6), c(6, 4), c(6, 7), c(3, 7))
M <- matrix(0, 7, 7); M[arcs] <- 1
str(cfc(M))          # 1 2 3 ; 4 5 6 ; 7
M[7, 1] <- 1         # nouveau lien 7 -> 1
str(cfc(M))          # 1 2 3 4 5 6 7 : fortement connexe

Exercice · Adapter Roy-Warshall

moyen

On veut savoir, pour chaque couple $(x, y)$ , s’il existe un chemin de $x$ à $y$ passant par un sommet donné $z$ (qui peut être l’une des extrémités). Proposez une méthode qui utilise la fermeture transitive $M^+$ , puis appliquez-la au site avec $z = 5$ : quels couples conviennent ?

Voir la solution

Un chemin de $x$ à $y$ passe par $z$ si et seulement si on peut aller de $x$ à $z$ , puis de $z$ à $y$ . En notant $M^\ast = M^+$ complétée par des 1 sur la diagonale (chaque sommet s’atteint lui-même par un chemin vide, ce qui autorise $z = x$ ou $z = y$ ), on pose :

A[x, y] = M^\ast[x, z] \times M^\ast[z, y]

Pour $z = 5$ : les sommets qui atteignent 5 (ou sont 5) sont $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$ , et ceux atteints depuis 5 (ou 5 lui-même) sont $\lbrace 4, 5, 6, 7 \rbrace$ . Tous les couples $(x, y)$ avec $x \in \lbrace 1, \dots, 6 \rbrace$ et $y \in \lbrace 4, 5, 6, 7 \rbrace$ conviennent, soit $6 \times 4 = 24$ couples. Par exemple, (1, 7) convient (1 → 2 → 4 → 5 → 6 → 7), mais (1, 3) non : aucun chemin de 1 à 3 ne peut passer par 5, car on ne revient jamais du bloc $\lbrace 4, 5, 6 \rbrace$ vers $\lbrace 1, 2, 3 \rbrace$ .

En code

Python
R

def roy_warshall(M):
    n = len(M)
    F = [ligne[:] for ligne in M]
    for k in range(n):                          # sommet intermédiaire à l'extérieur
        for x in range(n):
            if F[x][k]:
                for y in range(n):
                    if F[k][y]:
                        F[x][y] = 1
    return F

arcs = [(1, 2), (2, 3), (3, 1), (2, 4), (4, 5), (5, 6), (6, 4), (6, 7), (3, 7)]
M = [[0] * 7 for _ in range(7)]
for x, y in arcs:
    M[x - 1][y - 1] = 1
F = roy_warshall(M)
etoile = [[1 if x == y else F[x][y] for y in range(7)] for x in range(7)]   # M* : diagonale à 1

z = 5 - 1
couples = [(x + 1, y + 1) for x in range(7) for y in range(7) if etoile[x][z] and etoile[z][y]]
print(len(couples))                      # 24
print((1, 7) in couples, (1, 3) in couples)   # True False

roy_warshall <- function(M) {
  for (k in 1:nrow(M)) for (x in 1:nrow(M))
    if (M[x, k] == 1) M[x, M[k, ] == 1] <- 1     # x atteint k, et k atteint ces y
  M
}

arcs <- rbind(c(1, 2), c(2, 3), c(3, 1), c(2, 4), c(4, 5), c(5, 6), c(6, 4), c(6, 7), c(3, 7))
M <- matrix(0, 7, 7); M[arcs] <- 1
etoile <- roy_warshall(M); diag(etoile) <- 1       # M* : chaque sommet s'atteint lui-même

z <- 5
A <- outer(etoile[, z], etoile[z, ])               # A[x, y] = M*[x, z] * M*[z, y]
sum(A)                    # 24
c(A[1, 7], A[1, 3])       # 1 0

Exercice · Un graphe réduit sans circuit

difficile

Démontrez que le graphe réduit d’un graphe orienté quelconque est sans circuit. Déduisez-en que, si un graphe n’est pas fortement connexe, son graphe réduit possède au moins une composante sans arc entrant et une composante sans arc sortant.

Voir la solution

Supposons que le graphe réduit contienne un circuit $C_1 \to C_2 \to \dots \to C_p \to C_1$ avec $p \geq 2$ composantes distinctes. Prenons $x \in C_1$ et $y \in C_2$ . Il existe un chemin de $x$ à $y$ dans $G$ : on suit l’arc de $C_1$ vers $C_2$ , en circulant librement à l’intérieur de chaque composante. Il existe aussi un chemin de $y$ à $x$ : on suit le circuit $C_2 \to \dots \to C_p \to C_1$ de la même façon. Donc $x$ et $y$ s’atteignent mutuellement : ils devraient être dans la même composante, ce qui contredit $C_1 \neq C_2$ . Le graphe réduit est donc sans circuit.

Si $G$ n’est pas fortement connexe, le graphe réduit a au moins deux sommets. Partons de n’importe quelle composante et suivons des arcs sortants tant que c’est possible : comme il n’y a pas de circuit, on ne repasse jamais par la même composante, et comme il y en a un nombre fini, on finit bloqué sur une composante sans arc sortant (un « puits »). En remontant les arcs entrants de la même façon, on trouve une composante sans arc entrant (une « source »). C’est exactement la page 7 et le bloc $\lbrace 1, 2, 3 \rbrace$ de notre site.

En code

Python
R

def descendants(graphe, x):
    vu, pile = {x}, [x]
    while pile:
        for y in graphe[pile.pop()]:
            if y not in vu:
                vu.add(y)
                pile.append(y)
    return vu

site = {1: [2], 2: [3, 4], 3: [1, 7], 4: [5], 5: [6], 6: [4, 7], 7: []}
inverse = {x: [y for y in site if x in site[y]] for x in site}
compo = {x: min(descendants(site, x) & descendants(inverse, x)) for x in site}   # étiquette de la CFC

reduit = {c: set() for c in compo.values()}     # graphe réduit : un arc entre CFC distinctes
for x in site:
    for y in site[x]:
        if compo[x] != compo[y]:
            reduit[compo[x]].add(compo[y])
print(reduit)   # {1: {4, 7}, 4: {7}, 7: set()}
# un circuit existerait si une CFC c était atteignable depuis l'un de ses successeurs d
print(any(c in descendants(reduit, d) for c in reduit for d in reduit[c]))   # False
sources = [c for c in reduit if all(c not in s for s in reduit.values())]
puits = [c for c in reduit if not reduit[c]]
print(sources, puits)   # [1] [7] : le bloc {1, 2, 3} et la page 7

roy_warshall <- function(M) {
  for (k in 1:nrow(M)) for (x in 1:nrow(M))
    if (M[x, k] == 1) M[x, M[k, ] == 1] <- 1
  M
}

arcs <- rbind(c(1, 2), c(2, 3), c(3, 1), c(2, 4), c(4, 5), c(5, 6), c(6, 4), c(6, 7), c(3, 7))
M <- matrix(0, 7, 7); M[arcs] <- 1
F <- roy_warshall(M); diag(F) <- 1
compo <- sapply(1:7, function(x) min(which(F[x, ] == 1 & F[, x] == 1)))   # étiquette de la CFC

etiquettes <- unique(compo)
R <- matrix(0, length(etiquettes), length(etiquettes), dimnames = list(etiquettes, etiquettes))
for (k in 1:nrow(arcs)) {                         # graphe réduit
  a <- compo[arcs[k, 1]]; b <- compo[arcs[k, 2]]
  if (a != b) R[as.character(a), as.character(b)] <- 1
}
R                                                 # arcs 1 -> 4, 1 -> 7, 4 -> 7
any(diag(roy_warshall(R)) == 1)                   # FALSE : aucun circuit
etiquettes[colSums(R) == 0]; etiquettes[rowSums(R) == 0]   # source 1, puits 7