Visualizza wikitesto di Algoritmo di Tarjan per le componenti fortemente connesse

{{Algoritmo
|classe = [[Componente fortemente connessa]]
|immagine = Tarjan's Algorithm Animation.gif
|didascalia = Esecuzione dell'algoritmo di Tarjan
|struttura dati = [[Grafo]]
|tempo = <math>O(|E| + |V|)</math>
}}
L''''algoritmo di Tarjan''', così chiamato per il nome del suo inventore [[Robert Tarjan]], è un [[algoritmo]] usato nella [[teoria dei grafi]] per trovare le [[Componente fortemente connessa|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 [[Pila (informatica)|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).

<pre>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)
</pre>

==Implementazione in Java==
Ecco un codice [[Java (linguaggio di programmazione)|Java]] che implementa l'algoritmo utilizzando un grafo [[Neo4j]].

<syntaxhighlight lang=Java>

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"));
    }
}
</syntaxhighlight>
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 è 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 <math>O(|V|+|E|)</math>
#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 ==
*{{cita web|https://www.ics.uci.edu/~eppstein/161/960220.html#sca|Description of Tarjan's Algorithm}}
*{{cita web |1=https://vacilando.org/article/php-implementation-tarjans-cycle-detection-algorithm |2=Implementation of Tarjan's Algorithm in PHP |accesso=30 luglio 2015 |urlarchivio=https://web.archive.org/web/20160315030747/http://www.vacilando.org/article/php-implementation-tarjans-cycle-detection-algorithm# |dataarchivio=15 marzo 2016 |urlmorto=sì }}
*{{cita web | 1 = http://algowiki.net/wiki/index.php/Tarjan%27s_algorithm | 2 = Implementation of Tarjan's Algorithm in Java | accesso = 2 settembre 2010 | urlarchivio = https://web.archive.org/web/20090421041239/http://algowiki.net/wiki/index.php/Tarjan%27s_algorithm | dataarchivio = 21 aprile 2009 | urlmorto = sì }}

{{Algoritmi ricerca grafi}}

[[Categoria:Algoritmi sui grafi|Tarjan]]
[[Categoria:Algoritmi di ricerca|Tarjan]]
[[Categoria:Connettività dei grafi]]