|
Algoritmo di Tarjan per le componenti fortemente connesse
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 baseL'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 radiceIl 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 pseudocodiceL'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 JavaEcco 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
Bibliografia
Collegamenti esterni
|
||||||||||
