Come elencare tutti i cicli in un grafo orientato

Questa volta passo ad un articolo un po’ più tecnico, riguardante un argomento che ho avuto modo di approfondire durante un tirocinio interno all’università Roma Tre: si cercava un modo per evidenziare i cicli presenti in un grafo orientato, che rappresentava una mappa concettuale per un corso universitario.

Un esempio di un grafo diretto (fonte: Wikipedia)
Un esempio di un grafo diretto (fonte: Wikipedia)

Il problema di trovare eventuali cicli in un grafo orientato è stato sempre oggetto di studio da anni, vista la loro importanza applicativa. Da questo ci si è anche chiesti di trovare non solo un eventuale ciclo in un grafo orientato, ma anche un elenco completo di questi cicli: sono stati presentati alcuni algoritmi che svolgono questo compito, come gli algoritmi di Tiernan o Tarjan, ma le loro implementazioni sono piuttosto dispendiose in termini di memoria di calcolo richiesta e tempo limitati nell’ordine O(N·e·(c+1)), dove N indica il numero di nodi, e il numero di archi e c il numero di cicli.
Un algoritmo migliore in prestazioni è Johnson, che riesce ad elencare tutti i circuiti elementari di un grafo diretto in tempo limitato da O((n+e)·(c+1)) e spazio limitato O(N+e), questo anche grazie a dei controlli che eliminano la riproposizione di circuiti già considerati in precedenza sotto forma di una permutazione dei loro nodi.

Si è considerato l’algoritmo di Hawick e James, un’evoluzione dell’algoritmo di Johnson, ma che considera anche grafi con componenti isolate e dà alcune informazioni strutturali come la lunghezza media dei cicli, i nodi che hanno più partecipazione ai cicli e il ciclo con lunghezza maggiore.
L’algoritmo descrive il grafo tramite una lista di adiacenza contenuta in un array bidimensionale Ak[i][j], dove l’i-esimo vertice ha j archi in uscita (con j∈[0, …, m], m è il numero totale di archi presenti nel grafo), indicati tramite un array in cui il valore è il nodo di arrivo. Prendendo in analisi tutti i nodi del grafo, l’algoritmo inserisce in uno stack i nodi dai quali ha tentato una visita ricorsiva e li blocca, per evitare che vengano ripresi in considerazione; la funzione principale circuit($v) viene richiamata ricorsivamente per cercare un ciclo: se il nodo $v è diverso da quello con cui è iniziata l’iterazione dell’algoritmo e non è stato preso in considerazione finora, viene rilanciata ricorsivamente circuit su di esso; se il nodo che ha ricevuto in input è uguale al nodo iniziale, è stato trovato un ciclo: salvo l’attuale stack, imposto un flag per indicare la fine della ricerca e richiamo la funzione unblock($u) per sbloccare i vari nodi. L’algoritmo elenca i circuiti elementari presenti nel grafo, secondo l’ordine con cui sono stati passati i nodi.

L’implementazione è stata fatta in PHP e la potete trovare sulla pagina GitHub dedicata a fondo articolo: ha le funzioni richieste dall’algoritmo ed alcune funzioni di supporto, per gestire al meglio le strutture dati utilizzate. Ecco l’elenco nel dettaglio:
countArcs(): ritorna il numero di archi presenti nel grafo;
removeFromList($list, $arc): elimina l’elemento dall’array e ne ricompatta i valori;
stackInit(): inizializza lo stack ed azzera la variabile $stackTop, che punta alla testa dello stesso;
stackPush($val): immette il valore $val in testa allo stack;
stackPop(): ritorna l’elemento in testa allo stack e decrementa $stackTop;
stackClear(): svuota lo stack;
unblock($u): funzione che imposta a false il nodo nell’array blocked, che indica se un nodo è bloccato o meno; successivamente, per ogni nodo $w figlio di $u, lo rimuove dall’array $B[$u], che rappresenta il grafo degli elementi bloccati, e sblocca ricorsivamente $w;
circuit($v): la funzione principale dell’algoritmo, immette i nodi nello stack, blocca i nodi considerati lungo il cammino e verifica se è stato trovato un ciclo, come descritto precedentemente;
setupGlobals($nVert, $ak): si occupa di inizializzare le variabili globali necessarie ai fini dell’algoritmo e imposta il grafo sulla base di $ak;
launchHawickJames($a, $nv): è la funzione richiamata dall’esterno per lanciare l’algoritmo di Hawick-James, si occupa di lanciare la funzione circuit($v) su ogni nodo del grafo e di riportare le variabili di supporto al loro stato originale dopo ogni iterazione; ritorna l’array bidimensionale contenente tutti i cicli trovati.

GitHub Repository: Hawick-James PHP Implementation

The following two tabs change content below.
Un giovane universitario che col passare degli anni rimane universitario e diventa meno giovane.