Algoritmo di Tarjan per le componenti fortemente connesse

Da Wikipedia, l'enciclopedia libera.
Algoritmi di ricerca su grafi ed alberi.
Ricerca
Altro
Correlato

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. Un'applicazione tipica dell'algoritmo è la ricerca dei cicli. Ha la stessa efficienza dell'algoritmo di Gabow.

Concetto di base[modifica | modifica sorgente]

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 sono dunque inseriti in uno stack, ossia una pila, nell'ordine in cui sono visitati. Quando la ricerca risale da un sotto-albero visitato, i nodi corrispondenti sono ripresi dalla pila e viene determinato se ognuno è la radice di una componente fortemente connessa. Se lo è un nodo, allora insieme a tutti quelli presi prima (cioè appartenenti al sotto-albero di cui è radice) formano una componente fortemente connessa.

Determinare se un nodo è una radice[modifica | modifica sorgente]

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, ogni nodo ha un altro valore assegnato chiamato v.minima_distanza (o lowlink) che indica che indice deve avere per essere raggiungibile dalla radice. 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[modifica | modifica sorgente]

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 è 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'.index )     // 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[modifica | modifica sorgente]

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)
		for(Relationship r:n.getRelationships(DynamicRelationshipType.withName("TIPORELAZIONE"), Direction.INCOMING)){
 
//vp rappresenta il nodo v'
			Node vp=r.getOtherNode(n);
			if(!vp.hasProperty("index")){
				tarjan(vp);
//L'utilizzo di Integer.MAX_VAUE come parametro di default serve a gestire il caso del valore non definito
				if((Integer)vp.getProperty("lowlink",Integer.MAX_VALUE)<(Integer)n.getProperty("lowlink"))
					n.setProperty("lowlink", vp.getProperty("lowlink"));
			}
			else{
				if(s.contains(vp))
					if((Integer)vp.getProperty("index",Integer.MAX_VALUE)<(Integer)n.getProperty("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[modifica | modifica sorgente]

  1. Complessità: La procedura è chiamata una volta per ogni nodo. L'iterazione analizza ogni arco per due volte se non è orientato, altrimenti una. L'algoritmo dunque ha complessità computazionale lineare in base al numero di archi nel grafo, ossia O(|V|+|A|)
  2. Il test per determinare se v' è nella pila andrebbe fatto in tempo costante, per esempio controllando un valore memorizzato nel nodo stesso. Se non ci sono insiemi fortemente connessi molto grandi, comunque, si può iterare sulla pila senza peggiorare troppo la complessità dell'algoritmo.

Bibliografia[modifica | modifica sorgente]

  • Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, P. 146-160.

Collegamenti esterni[modifica | modifica sorgente]