Per vestirsi la mattina bisogna rispettare alcuni vincoli: le calze prima delle scarpe, la camicia prima della cravatta, i pantaloni prima della cintura. Altri capi sono indipendenti: l'orologio si può mettere quando si vuole. Trovare una sequenza che rispetti tutti i vincoli è un ordinamento topologico.
Lo stesso problema si presenta ovunque ci siano dipendenze: un sistema di build deve compilare le librerie prima dei programmi che le usano, un gestore di pacchetti deve installare le dipendenze prima del pacchetto richiesto, un foglio di calcolo deve ricalcolare le celle nell'ordine giusto, un piano di studi deve rispettare le propedeuticità.
Il modello: un grafo orientato aciclico
Si costruisce un grafo orientato con un vertice per ogni attività e un arco (A, B) quando A deve precedere B. Un ordinamento topologico è una disposizione dei vertici in fila in cui ogni arco va da sinistra verso destra.
Esiste se e solo se il grafo non ha cicli orientati, cioè se è un DAG. Il motivo è intuitivo: se A precede B, B precede C e C precede A, nessuna sequenza può accontentare tutti. Un algoritmo di ordinamento topologico ben scritto, quindi, fa sempre anche un secondo lavoro: segnalare i cicli quando ci sono.
Di solito gli ordinamenti validi sono molti. Nel caso dei vestiti, l'orologio può stare in qualunque posizione. Gli algoritmi ne producono uno; se serve un ordine particolare (per esempio alfabetico a parità di vincoli) si sceglie con criterio quale vertice estrarre per primo.
L'algoritmo di Kahn
È il metodo più intuitivo e quello che conviene implementare per primo.
- Calcola il grado entrante di ogni vertice, cioè quante dipendenze non ancora soddisfatte ha.
- Metti in una coda tutti i vertici con grado entrante zero: sono le attività che si possono fare subito.
- Estrai un vertice dalla coda, aggiungilo al risultato e «cancella» i suoi archi uscenti, diminuendo di uno il grado entrante dei vicini. Ogni vicino che arriva a zero entra in coda.
- Ripeti finché la coda è vuota.
from collections import deque
def kahn(n, archi):
adj = [[] for _ in range(n)]
entranti = [0] * n
for a, b in archi:
adj[a].append(b)
entranti[b] += 1
coda = deque(v for v in range(n) if entranti[v] == 0)
ordine = []
while coda:
u = coda.popleft()
ordine.append(u)
for v in adj[u]:
entranti[v] -= 1
if entranti[v] == 0:
coda.append(v)
if len(ordine) < n:
raise ValueError("il grafo contiene un ciclo")
return ordine
Se alla fine il risultato contiene meno vertici di quelli totali, i vertici rimasti fanno parte di un ciclo o dipendono da un ciclo. È un'informazione diagnostica preziosa: invece di dire genericamente «errore», si può elencare l'insieme dei vertici bloccati.
Il costo è proporzionale a n + m.
La versione con DFS
Un secondo metodo usa la visita in profondità. Si esegue una DFS completa e, ogni volta che un vertice è finito (tutti i suoi discendenti sono stati esplorati), lo si aggiunge in testa a una lista. Alla fine la lista è un ordinamento topologico.
Funziona perché, in un DAG, se esiste l'arco (u, v) allora v finisce sempre prima di u. Mettendo in testa i vertici man mano che finiscono, u si ritrova davanti a v. I cicli si rilevano con il consueto schema a tre colori: un arco verso un vertice ancora in corso di visita indica una dipendenza circolare.
La versione DFS è comoda quando si vuole ordinare solo ciò che serve a un obiettivo: lanciando la visita dal solo vertice richiesto si ottengono esclusivamente le sue dipendenze, come fa un gestore di pacchetti che installa un programma e niente altro.
Parallelismo per livelli
L'algoritmo di Kahn offre un bonus. Se invece di estrarre un vertice alla volta si estraggono tutti i vertici con grado entrante zero, si ottengono dei livelli: tutte le attività di un livello sono indipendenti tra loro e possono essere eseguite in parallelo. È così che un sistema di build con più processori decide quali file compilare contemporaneamente. Il numero di livelli indica il tempo minimo con risorse illimitate, misurato in «turni».
Cammino critico
Se ogni attività ha una durata, sul DAG si può calcolare il cammino critico: la catena di dipendenze più lunga in termini di tempo. Si scorre l'ordinamento topologico e, per ogni attività, si calcola il primo istante in cui può iniziare, cioè il massimo dei tempi di fine dei suoi predecessori.
| Attività | Durata | Dipende da | Inizio minimo | Fine |
|---|---|---|---|---|
| Fondazioni | 4 | — | 0 | 4 |
| Impianti | 3 | Fondazioni | 4 | 7 |
| Muri | 5 | Fondazioni | 4 | 9 |
| Tetto | 2 | Muri | 9 | 11 |
| Finiture | 3 | Impianti, Tetto | 11 | 14 |
Il progetto dura 14 unità e il cammino critico è Fondazioni → Muri → Tetto → Finiture. Ritardare gli impianti di qualche unità non cambia nulla; ritardare i muri sposta l'intera consegna. Questa analisi, nota nella gestione di progetti come metodo del cammino critico, non è altro che un ordinamento topologico seguito da una semplice programmazione dinamica.
In sintesi
- Un ordinamento topologico mette in fila le attività rispettando tutte le dipendenze.
- Esiste solo nei grafi orientati aciclici; un buon algoritmo segnala anche i cicli.
- L'algoritmo di Kahn usa i gradi entranti e una coda, con costo lineare.
- La versione con DFS ordina i vertici per tempo di fine decrescente.
- Livelli paralleli e cammino critico si ricavano direttamente dall'ordinamento.
