L'algoritmo di Tarjan, così chiamato per il nome del suo inventore Robert Tarjan, è un algoritmo usato nella teoria dei grafi per trovare le componenti fortemente connesse di un grafo orientato. Un'applicazione tipica dell'algoritmo è la ricerca dei cicli. Ha la stessa efficienza dell'algoritmo di Gabow.
Concetto di base L'idea alla base dell'algoritmo è che una ricerca depth-first inizia sempre da un nodo di partenza. Le componenti fortemente connesse, insieme, formano i sotto-alberi dell'albero di ricerca le cui radici sono le componenti fortemente connesse.
I nodi vengono inseriti in una pila nell'ordine in cui sono visitati e vi rimangono finché non viene individuata la radice di una componente fortemente connessa. Quando viene trovata una radice, essa e tutti i nodi successivi presenti nella pila che appartengono alla stessa componente vengono estratti insieme.
Determinare se un nodo è una radice Il punto centrale dell'algoritmo consiste nel determinare se un nodo è la radice di una componente fortemente connessa. Per farlo, a ogni nodo v è assegnato un indice di profondità della ricerca, chiamato v.indice, che viene incrementato man mano che vengono trovati nuovi nodi. Inoltre, a ogni nodo è associato un valore chiamato v.minima_distanza (o lowlink), che rappresenta il più piccolo indice di un nodo ancora presente nella pila e raggiungibile da v attraverso il sottoalbero generato dalla ricerca depth-first, includendo v stesso. Quindi, un nodo è la radice di una componente fortemente connessa se e solo se indice e minima_distanza sono uguali. Il valore minima_distanza è calcolato durante la ricerca depth-first in modo da poter essere sempre recuperabile.
L'algoritmo in pseudocodice L'algoritmo riceve in input il grafo G composto da un insieme di vertici V e di archi orientati (se non è un grafo orientato si può modellizzare ogni arco con due archi orientati nei due orientamenti).
Input: Grafo G = (V, A)
indice = 0 // contatore del numero di nodi S = [] // La pila dei nodi, inizialmente vuota per ogni v in V: se (v.indice non è definito) // avvia la ricerca depth-first per ogni nodo tarjan(v) // non è ancora visitato, lo visitiamo
procedura tarjan(v) v.indice = indice // assegna al nodo l'indice attuale v.minima_distanza = indice indice = indice + 1 S.push(v) // aggiungi (push) v alla pila S per ogni arco (v, v') in A: // analizza i successori di v nel grafo se (v'.indice non è definito) // Questo successore non è ancora stato visitato tarjan(v') // Ricorsione v.minima_distanza = min(v.minima_distanza, v'.minima_distanza) altrimenti se (v' è contenuto in S) // v' era già dentro S? v.minima_distanza = min(v.minima_distanza, v'.indice) // v' è in S ma non nel sotto-ramo ottenuto nella ricerca depth-first se (v.minima_distanza == v.indice): // v è la radice di un sottoalbero scrivi "Trovato insieme di componenti fortemente connesse:" ripeti v' = S.pop() scrivi v' finché (v' != v)
Implementazione in Java Ecco un codice Java che implementa l'algoritmo utilizzando un grafo Neo4j.
public void RicercaSFC() {
this.index = 0; this.s = new ArrayList<Node>();
for (Node n : graphDb.getAllNodes()) { commitTransazione(); if (!n.hasProperty("index")) tarjan(n);
private void tarjan(Node n) throws IOException { System.out.println("analizzo "+n.getProperty("name"));
n.setProperty("index", this.index); n.setProperty("lowlink", index);
index++; s.add(n);
commitTransazione();
/* TIPORELAZIONE è il nome del tipo di relazione da analizzare. Si può omettere se si vogliono analizzare indistintamente tutte quelle presenti Il programma tiene conto dell'orientamento degli archi (si può scrivere ugualmente INCOMING o OUTGOING, per le proprietà delle Componenti Fortemente Connesse si otterrà lo stesso risultato) */
Relationship[] relationships = n.getRelationships( DynamicRelationshipType.withName("TIPORELAZIONE"), Direction.INCOMING );
for (Relationship r : relationships) { Node vp=r.getOtherNode(n); //vp rappresenta il nodo v'
if (!vp.hasProperty("index")) { tarjan(vp);
// L'utilizzo di Integer.MAX_VALUE come parametro di default serve a gestire il caso // del valore non definito
int vp_lowlink = (Integer) vp.getProperty("lowlink", Integer.MAX_VALUE); int n_lowlink = (Integer) n.getProperty("lowlink");
if (vp_lowlink < n_lowlink) n.setProperty("lowlink", vp.getProperty("lowlink")); } else{ int vp_index = (Integer) vp.getProperty("index", Integer.MAX_VALUE); int n_lowlink = (Integer) n.getProperty("lowlink");
if(s.contains(vp) && vp_index < n_lowlink) n.setProperty("lowlink", vp.getProperty("index"));
if (n.getProperty("lowlink").equals(n.getProperty("index"))) { System.out.println("Trovata Struttura Fortemente connessa:"); Node l;
/* la variabile singolo serve a non mostrare nulla quando il nodo è uno solo, per non mostrare le SFC banali */ boolean singolo = true;
while (!(l = s.remove(s.size() - 1)).equals(n)) { System.out.println(l.getProperty("name")); singolo = false;
if (!singolo) System.out.println(l.getProperty("name"));
La funzione commitTransazione (), omessa per semplicità, chiude la transazione e la riapre, per salvare i valori di proprietà assegnati ed evitare anomalie dovute al fatto che nei successivi passaggi non sarebbero letti i valori appena assegnati. Si è supposto che ogni nodo abbia una proprietà name che lo identifica.
Osservazioni Complessità: la procedura viene eseguita una volta per ogni nodo e ogni arco viene esaminato al più una volta. La complessità temporale dell'algoritmo è quindi lineare rispetto al numero di vertici e archi del grafo, ossia . Per mantenere tale complessità, il controllo che determina se un nodo è presente nella pila deve essere eseguito in tempo costante, ad esempio memorizzando per ogni nodo un apposito valore booleano.
Bibliografia Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, P. 146-160.
Collegamenti esterni
Tarjan Tarjan Categoria:Connettività dei grafi