Algoritmo di Tarjan per le componenti fortemente connesse
Algoritmo di Tarjan per le componenti fortemente connesse | |
---|---|
![]() | |
Classe | Componente fortemente connessa |
Struttura dati | Grafo |
Caso peggiore temporalmente | |
Manuale |
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
- 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
- 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).
V · D · M | |||
---|---|---|---|
Ricerca | Potatura alfa-beta · Algoritmo di Bellman-Ford · Algoritmo di Tarjan · Bidirectional search · D* · Depth-limited search · Algoritmo di Dijkstra · Algoritmo di Floyd-Warshall · Hill climbing · Iterative deepening depth-first search · Algoritmo di Johnson · Lexicographic breadth-first search · Ricerca in ampiezza · Ricerca in profondità · Uniform-cost search · Ricerca ad albero Monte Carlo (MCTS)
| ||
Voci correlate | Programmazione dinamica |