Algoritmo di Tarjan per le componenti fortemente connesse

Algoritmo di Tarjan per le componenti fortemente connesse
Esecuzione dell'algoritmo di Tarjan
Classe	Componente fortemente connessa
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|E|+|V|)$

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

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

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

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'.minima_distanza )     // 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_VAUE 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

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|+|E|)$
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

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

Collegamenti esterni

• Description of Tarjan's Algorithm, su ics.uci.edu.
• Implementation of Tarjan's Algorithm in PHP, su vacilando.org. URL consultato il 30 luglio 2015 (archiviato dall'url originale il 15 marzo 2016).
• Implementation of Tarjan's Algorithm in Java, su algowiki.net. URL consultato il 2 settembre 2010 (archiviato dall'url originale il 21 aprile 2009).