Codice Quello che segue è il codice java che implementa l’algoritmo ALL- BRIDGE e la rete virtuale creata per l’esecuzione dello stesso.

Codice

Quello che segue è il codice java che implementa l’algoritmo

ALL-BRIDGE e la rete virtuale creata per l’esecuzione dello stesso.

Tipi di dato

Verranno prima presentati i tipi di dato che sono stati creati e poi le

procedure che ne fanno uso per la simulazione della rete e

l’esecuzione dell’algoritmo.

Il tipo nodo rappresenta un nodo della rete, al cui interno sono

definite tutte le strutture dati necessarie.

class nodo {

int nome; /* nome del nodo */

arco[] in; /* insieme degli archi incidenti */

int ind; /* indice (dimensione) del vettore degli archi */

/* incidenti */

Tree[] SPT; /* alberi SPT radicati nel nodo i-esimo */ Position[] posizioni; /* posizione del nodo nell'albero */

/* SPT i-esimo */

int[] distanza; /* distanza dalla radice dell'albero */

APPENDICE: Codice

Vector[] LL; /* rappresenta la lista del archi */ /* incidenti che non appartengono */

/* all'albero SPT per ogni */

/* SPT i-esimo */

alfa[] vect_alfa; /* vettore degli alfa (un elemento */

/* per ogni SPT) */

elem_routing[] TabRout; /* tabella di routing */ /* (un elemento per ogni */

/* destinazione) */

int ind1 = 0; /*indice della tabella di routing */ }

Il tipo arco rappresenta un link della rete ed è composto dal nome dei

nodi che collega e dal suo peso.

class arco {

int a; /* nome del primo nodo */

int b; /* nome del secondo nodo */

int peso; /* peso dell'arco */

}

Il tipo seguente rappresenta l’elemento di base della tabella di routing

contenuta in ogni nodo:

class elem_routing {

int dest; /* nome del nodo destinazione */

int next; /* nome del nodo successivo nel */

/* percorso verso la destinazione */

arco swap_edge; /* arco di swap */

APPENDICE: Codice

Un elemento di tipo SPT serve per memorizzare un albero di

copertura di costo minimo ed è rappresentato semplicemente come

una collezione di archi.

class SPT {

arco[] albero; /* SPT, memorizzato come */

/* collezione di archi */

}

I tipi mostrati di seguito implementano i canali di comunicazione

utilizzati dai nodi per comunicare fra di loro come se fossero link.

Quindi sono realizzati utilizzando una struttura dati per contenere i

messaggi e due metodi sincronizzati per permettere che il canale

risulti consistente.

class canaleR {

private Vector inputR = new Vector(10,2);

/* questo vettore funge da canale di */ /* comunicazione (per le richieste) quindi */ /* l'accesso deve essere fatto in modo */

/* Synchronized */

synchronized void send(elemento_canale e) { inputR.add(e);

notify(); }

synchronized elemento_canale receive() { if (inputR.isEmpty()) {

try {

wait();

/* se mi trovo qui vuol dire che */

/* qualcuno ha scritto nel canale */

}

catch (InterruptedException e) {} }

return (elemento_canale) inputR.remove(0); }

APPENDICE: Codice

}

class canaleC {

private Vector inputC = new Vector(10,2);

/* questo vettore funge da canale di */ /* comunicazione (per le scelte) quindi */ /* l'accesso deve essere fatto in modo */

/* Synchronized */

synchronized void send(elemento_canale e) { inputC.add(e);

notify(); }

synchronized elemento_canale receive() { if (inputC.isEmpty()) {

try {

wait();

/* se mi trovo qui vuol dire che */

/* qualcuno ha scritto nel canale */

}

catch (InterruptedException e) {} }

return (elemento_canale) inputC.remove(0); }

}

Per ultimo, ma non per importanza, è presentato il tipo di dato grafo

che rappresenta la rete: oltre a contenere una collezione di nodi ed

archi, contiene anche la lista di tutti gli alberi di copertura di costo

minimo ognuno radicato in un diverso nodo.

class grafo {

int n_nodi = 0;

nodo[] V; /* insieme dei nodi */

arco[] E; /* insieme degli archi */

SPT[] tree; /* insieme degli SPT del grafo */

APPENDICE: Codice

Procedure

Vengono ora mostrate le procedure create ed utilizzate per la

simulazione della rete e di seguito quelle per la simulazione

dell’esecuzione dell’algoritmo distribuito ALL-BRIDGE.

La seguente procedura è stata scritta per acquisire la

rappresentazione di una rete vista come grafo, da un file di testo. La

procedura restituisce un elemento di tipo grafo in cui ogni nodo

conosce quali sono i propri archi incidenti.

static grafo acquisisci_grafo(String file)

{ /* il file deve avere questo formato: */

/* numero nodi */

/* nodo1 nodo2 peso */

/* nodox nodoy peso */

/* ... */ int nodi=0; grafo gr; int source; int dest; int cost; try {

FileReader fin = new FileReader( file );

BufferedReader graph = new BufferedReader( fin );

int i = 0;

/* Lettura archi e inserimento */

String line;

line = graph.readLine( );

/* legge il numero di nodi */

StringTokenizer st = new StringTokenizer( line ); nodi = Integer.parseInt(st.nextToken( )); gr = new grafo(nodi);

APPENDICE: Codice

gr.n_nodi = nodi;

i++;

while( ( line = graph.readLine( ) ) != null ) {

st = new StringTokenizer( line ); try

{ if( st.countTokens( ) != 3 )

throw new Exception( );

source = Integer.parseInt(st.nextToken( )); dest = Integer.parseInt(st.nextToken( )); cost = Integer.parseInt(st.nextToken( )); gr.E[i-1].a = source; gr.E[i-1].b = dest; gr.E[i-1].peso = cost; } catch( Exception e ) { System.err.println( e + " " + line ); } i++; }

/* inserimento dei nodi */

for (int k = 0; k<nodi; k++) { gr.V[k].nome = k+1; }

/* elaborazione del grafo per fare in modo */

/* che ogni nodo sappia quali sono gli archi incidenti */

for (int ind_arco=0; ind_arco<gr.E.length; ind_arco++) { if (gr.E[ind_arco].a != 0) { gr.V[gr.E[ind_arco].a-1].in[gr.V[gr.E[ind_arco].a-1].ind] = gr.E[ind_arco]; gr.V[gr.E[ind_arco].a-1].ind++; gr.V[gr.E[ind_arco].b -1].in[gr.V[gr.E[ind_arco].b-1].ind] = gr.E[ind_arco]; gr.V[gr.E[ind_arco].b -1].ind++; } } return gr;

APPENDICE: Codice

La procedura mostrata di seguito, è stata scritta per calcolare,

partendo da un grafo e da un nodo “radice” un albero di copertura dei

cammini di costo minimo, utilizzando l’algoritmo di Dijkstra

opportunamente rivisto per funzionare anche nel caso di reti con archi

bidirezionali.

Inoltre la procedura è in grado di elaborare per ogni nodo le etichette

di visita dell’albero relative ad una visita preorder traversal e

preorder inverted traversal.

Ovviamente il calcolo dell’albero SPT porta come conseguenza al

riempimento della tabelle di routing di tutti i nodi.

public static Tree calcola_SPT(nodo radice, grafo G) {

/* questa procedura calcola l’SPT del grafo G, radicato */ /* nel nodo “radice” utilizzando l’algoritmo di Dijkstra */

Tree albero = new NodeTree(); /* albero SPT */

Tree albero_inverso = new NodeTree(); /* albero SPT "inverso" */

albero.replaceElement(albero.root(), new Integer(radice.nome)); albero_inverso.replaceElement(albero_inverso.root(), new

Integer(radice.nome));

Position[] posizioni = new Position[G.n_nodi+1];

/* vettore che memorizza le posizioni dei nodi */

Position[] posizioni_inverse = new Position[G.n_nodi+1];

/* vettore che memorizza le posizioni dei nodi nell'albero inverso */

APPENDICE: Codice

posizioni_inverse[radice.nome] = albero_inverso.root(); int[] D = new int[G.n_nodi+1];

Vector P = new Vector(G.n_nodi);

/* rappresenta l'insieme "P" */

Vector N_P = new Vector(G.n_nodi);

/* rappresenta l'insieme "N-P" */

/* INIZIALIZZAZIONE */

P.add(radice);

/* inserire in N_P i nodi che non stanno in P */

for (int i=0; i<G.V.length; i++) { if ( G.V[i].nome != 0) {

if ( G.V[i] != radice ) { N_P.add(G.V[i]); } }

}

D[radice.nome]=0;

/* D[j] = d(1,j), oppure = “inifinito” se l’arco non esiste */ for (int i=1; i<G.n_nodi+1; i++){

if ( i != radice.nome ) D[i] = 10000; /* sta per “infinito” */ }

for (int k=0; k<radice.in.length; k++) {

if (radice.in[k].a == radice.nome) { D[radice.in[k].b] = radice.in[k].peso; } else { D[radice.in[k].a] = radice.in[k].peso; }

}

/* FINE INIZIALIZZAZIONE */

int s=0;

boolean fine = false;

APPENDICE: Codice

/* PASSO 1 */

/* trovare il minimo D[j] con j appartenente a N_P */

int indice = 0; int min = 10000;

arco arcoInserito = new arco(); for (int i=0; i<D.length; i++) {

if (( D[i] < min ) && ( D[i] != 0 )) {

/* se l'elemento è presente in N-P allora il minimo viene aggiornato */ if (N_P.contains(G.V[i-1])) { min = D[i]; indice = i; } } } /* aggiornamento di P */ P.add(G.V[indice-1]);

int nodoInserito = G.V[indice-1].nome;

/* serve per creare l’ SPT */

/* inserimento dell'arco nel SPT */

nodo nodo_estr = new nodo(G.n_nodi); int peso;

boolean esci;

for (int k=0; k<P.size(); k++) { esci = false;

nodo_estr = (nodo) P.get(k); peso = D[nodo_estr.nome];

for (int i=0; i<G.V[indice-1].ind; i++){

if (( G.V[indice-1].in[i].a == nodo_estr.nome ) | ( G.V[indice-1].in[i].b == nodo_estr.nome ))

{ if ( D[G.V[indice-1].nome] == D[nodo_estr.nome] + G.V[indice-1].in[i].peso ) { /* inserire l'arco in SPT e uscire dai cicli */

APPENDICE: Codice

G.tree[radice.nome].albero[s] = G.V[indice-1].in[i]; s++;

arcoInserito = G.V[indice-1].in[i];

/* serve per creare il SPT */ esci = true;

break; } } }

if (esci == true) break; }

/* fine dell'inserimento dell'arco nel SPT */

/* aggiornamento di N-P */

N_P.remove(G.V[indice-1]);

/* avendo a disposizione nodoInserito e arcoInserito, */ /* è possibile creare la struttura albero con NodeTree */ /* (“s” indica il numero di nodi inseriti); ad ogni nodo inserito */ /* è necessario salvare i "position" così quando si deve */ /* inserire un figlio di un nodo con una certa "position" si */

/* conosce il punto in cui inserirlo */

int figlio, padre;

if (arcoInserito.a == nodoInserito)

{ padre = arcoInserito.b;

figlio = arcoInserito.a; }

else { figlio = arcoInserito.b; padre = arcoInserito.a; }

Position node = albero.insertFirstChild(posizioni[padre], new Integer(figlio)); posizioni[figlio] = node;

Position node_inverso =albero_inverso.insertLastChild(

posizioni_inverse[padre], new Integer(figlio)); posizioni_inverse[figlio] = node_inverso;

APPENDICE: Codice

/* una volta inserito il nodo nell'albero SPT, è possibile */

/* aggiornare la tabella di routing per quel nodo */

G.V[indice-1].TabRout[G.V[indice-1].ind1].dest = radice.nome; G.V[indice-1].TabRout[G.V[indice-1].ind1].next = padre; G.V[indice-1].ind1++; /* FINE PASSO 1 */ if ( P.size() == G.n_nodi ) {

/* l'algoritmo si deve fermare */

fine = true; } if ( fine != true ){ /* PASSO 2 */ /* aggiornare i D[j] */

nodo estratto = new nodo(G.n_nodi); int nome_nodo = 0;

int minimo=10000; /* "infinito" */ int nuovo_peso = 0;

for (int j=0; j<N_P.size(); j++) { estratto = (nodo) N_P.get(j); nome_nodo = estratto.nome; minimo = 10000;

for (int k=0; k<estratto.ind; k++) {

if ( nome_nodo == estratto.in[k].a ) {

nuovo_peso = estratto.in[k].peso + D[estratto.in[k].b]; } else { nuovo_peso = estratto.in[k].peso + D[estratto.in[k].a]; }

if (nuovo_peso < minimo) { minimo = nuovo_peso; }

}

if ( D[nome_nodo] < minimo ) {/* D[j] rimane quello che è */ } else { D[nome_nodo] = minimo; }

} } }

APPENDICE: Codice

/* ora occorre calcolare gli alfa(a,b), attraverso la visita */ /* preorder e preorder inverted dell'albero e inserire */

/* questi dati nei nodi */

PositionIterator nodes = new TreeTraversal(albero, 1); int i=0; String estratto; while(nodes.hasNext()) { estratto = nodes.nextPosition().element().toString(); G.V[Integer.parseInt(estratto)-1].vect_alfa[radice.nome-1].a = i+1; i++; }

PositionIterator nodes_i = new TreeTraversal(albero_inverso, 1); i=0; while(nodes_i.hasNext()) { estratto = nodes_i.nextPosition().element().toString(); G.V[Integer.parseInt(estratto)-1].vect_alfa[radice.nome-1].b = i+1; i++; } /* alfa(a,b) memorizzati */

/* ora l’albero calcolato deve essere memorizzato in tutti i nodi */

for (int k=0; k<G.n_nodi; k++){

G.V[k].SPT[radice.nome] = albero; }

/* poi viene memorizzata la posizione dei nodi nell'albero */

/* all'interno dei nodi stessi */

for (int k=1; k<posizioni.length; k++){ if (posizioni[k] == null) break;

G.V[k-1].posizioni[radice.nome] = posizioni[k]; }

/* si memorizza la distanza dei nodi dell'albero dalla radice */

APPENDICE: Codice

if (posizioni[k] == null) break;

G.V[k-1].distanza[radice.nome] = D[k]; } SPT[] alb = G.tree; return albero; }

È stato necessario scrivere la seguente procedura, che per ogni nodo

e per ogni albero SPT calcola la lista degli archi incidenti che non

fanno parte dell’SPT, perché tale lista fa parte dei prerequisiti

necessari ai nodi per poter eseguire l’algoritmo ALL-BRIDGE.

public static void calcola_vicini_non_SPT(int nome_nodo) {

/* calcola i vicini non appartenenti agli SPT per il nodo */ /* i-esimo deve essere fatto una volta per ogni albero SPT */

for (int n_alb=0; n_alb<G.n_nodi; n_alb++) {

for (int i=0; i<G.V[nome_nodo].ind; i++) {

elemento da_inserire = new elemento();

if (!appartiene(nome_nodo, n_alb, G.V[nome_nodo].in[i])) {

/* se l'arco "e" non appartiene al SPT deve */ /* essere inserito L(x). prima di inserirlo, occorre */ /* calcolare il peso dell'arco "d(e)" */ da_inserire.link = G.V[nome_nodo].in[i];

da_inserire.peso = calcola_peso(nome_nodo, n_alb,

G.V[nome_nodo].in[i]); inserisci(nome_nodo, n_alb, da_inserire);

} } } }

APPENDICE: Codice

Quello che segue è invece il corpo del thread, che rappresenta un

generico nodo della rete, il quale dovrà poi eseguire l’algoritmo

distribuito.

Al suo interno oltre ad essere presenti le strutture dati necessarie, è

contenuto anche il codice dell’algoritmo; grazie all’esecuzione di n

istanze dell’algoritmo, eseguite ognuna da un thread(nodo) diverso, la

computazione distribuita verrà portata a termine.

public class thread_nodo extends Thread {

public final int Computing = 1; /* rappresentano */ public final int Swapped = 2 ; /* gli stati in cui */ public final int Waiting = 3 ; /* si può trovare un nodo */ public final int Done = 4;

int stato; nodo mio_nodo; elemento swap_edge;

Vector LX = new Vector(0,2); /* rappresenta la lista dei */

/* Possibili swap edge */

Vector Req = new Vector(0,2); /* rappresenta la lista delle */ /* richieste da fare ai figli */ canaleC CC = new canaleC(); /* canale di comunicazione */ /* per i messaggi in ingresso */ canaleR CR = new canaleR(); /* canale di comunicazione */ /* per i messaggi in uscita */ public void run() {

int cond = 0; while (cond == 0) {

switch (this.stato) { /* struttura dell’algoritmo */ case 1: computing(); break;

case 2: swapped(); break; case 3: waiting(); break;

case 4: { done(); cond=1; break; } }

APPENDICE: Codice

Di seguito sono presentate le quattro procedure che rappresentano i

quattro stati in cui un nodo, nel corso dell’esecuzione dell’algoritmo

distribuito ALL-BRIDGE, si può venire a trovare. Queste

rappresentano il cuore dell’algoritmo e al loro interno sono

diversificate a seconda che in nodo su cui sono eseguite sia la radice

dell’SPT oppure un nodo interno oppure una foglia.

public void computing () {

if (!albero.isRoot(pos)) /* se il nodo non è la radice */

{ /* ricavare il nome del padre */

padre = albero.parent(pos);

String Spadre = padre.element().toString(); n = Integer.parseInt(Spadre);

}

if (albero.isExternal(pos)) /* se il nodo è una foglia */

{ /* sceglie il suo bridge e */

/* lo invia al genitore */ mybridge = ChooseMin(mio_nodo.vect_alfa[this.n_alb-1]);

if (mybridge != null) sendCTo("Choice", mybridge,n); else sendCTo("null", mybridge,n);

became(Swapped);

/* si prepara ad attendere richieste dal genitore */ return;

}

else /* se è un nodo interno */

{ /* attende che ognuno dei proprio figli abbia inviato il proprio bridge */ int num_figli = albero.numChildren(pos);

int k = 0;

for (int i=0; i<num_figli; i++) {

// receive da un figlio sonBridge = receiveC();

// se l'arco è "feasible" lo memorizza if (!sonBridge.s.equals("null"))

{ if (feasible(sonBridge.ele.link, mio_nodo.vect_alfa[this.n_alb-1]))

APPENDICE: Codice

k++;

}

/* se non è "feasible", fai una richiesta al figlio */

else

{ elemento_canale elem = new

elemento_canale("Request",null,sonBridg e.mitt,mio_nodo.vect_alfa[this.n_alb-1]); this.Req.add(elem); this.check++; } } else k++; }

/* se lo swap edge di tutti i figli è "feasible" scegli */ /* il migliore, se il nodo era un nodo interno, */ /* altrimenti se era la radice, deve terminare l’algoritmo */

if (albero.isRoot(pos)) /* se il nodo era la radice */

{ /* si deve terminare l'algoritmo */

/* invio un messaggio a tutti i figli che a */ /*loro volta lo invieranno ai loro figli... */ PositionIterator Pfigli = albero.children(pos);

String Sfiglio; int figlio; while(Pfigli.hasNext()) { Sfiglio = Pfigli.nextPosition().element().toString(); figlio = Integer.parseInt(Sfiglio);

sendRTo("Done", null, figlio, null); }

became(Done); return; }

if (k == num_figli) /* se tutti i figli hanno inviato un */

/* bridge feasible, deve essere */

/* scelto il migliore e deve essere */

/* inviato al genitore */

APPENDICE: Codice

if (mybridge != null) sendCTo("Choice", mybridge,n); else sendCTo("null", mybridge,n);

became(Swapped);

/* si prepara ad attendere richieste dal genitore */ return;

} else {

became(Waiting);

/* si prepara ad attendere risposte dai figli */ return;

} } }

public void swapped () {

/* ricavare il nome del padre */

padre = albero.parent(pos);

String Spadre = padre.element().toString(); n = Integer.parseInt(Spadre); this.check = 0; while(true) { // ricevi richiesta rec = receiveR(); if (rec.s.equals("Request")) { if ( albero.isExternal(pos) ) { // calcola minimo mybridge = ChooseMin(rec.label);

/* invia la risposta al genitore */

if (mybridge != null) sendCTo("Choice", mybridge,rec.mitt); else sendCTo("null", mybridge,rec.mitt); }

else

{ int precedente = 0;

for (int i=0; i<LX.size(); i++) {

APPENDICE: Codice

if (estratto.ricevuto == 1)

{ if (estratto.mitt != precedente) {

precedente = estratto.mitt;

/* se l'arco inv. del figlio i-esimo non è feasible */ if ( !(feasible(estratto.ele.link,rec.label)) )

{ /* invia una richiesta al figlio */ elemento_canale elem = new

elemento_canale("Request", null, estratto.mitt, rec.label); this.Req.add(elem); this.check++; } } } } if (this.check > 0) { this.comp = 1; this.alfa_attuale = rec.label;

/* se è stata fatta richiesta ad almeno un figlio */ became(Waiting); /* bisogna mettersi in attesa */

/* di ricevere la risposta */ return; } else { /* calcola il minimo */ mybridge = ChooseMin(rec.label);

/* invia l'arco scelto al genitore */

if (mybridge != null) sendCTo("Choice", mybridge,n); else sendCTo("null", mybridge,n);

} } } else { if ( albero.isExternal(pos) ) { became(Done); return; } else

{ /* si deve propagare il messaggio che */

/* l'algoritmo è terminato */

APPENDICE: Codice

sendRTo("Done", null, figlio, null); } became(Done); return; } } } }

public void waiting () {

while (this.Req.size() > 0) /* prima di tutto si devono */ /* inviare tutte le richieste */

/* da fare ai figli */

{

ric = (elemento_canale)this.Req.remove(0); sendRTo(ric.s, null, ric.mitt, ric.label); }

/* poi si aspettano le risposte */ for (int i=0; i<check1; i++)

{

/* riceve l'arco (giusto) dal figlio */

rec = receiveC(); if (!rec.s.equals("null")) { /* memorizza l'arco */ insert(rec); } this.check--; } if (!albero.isRoot(pos)) { int n = 0;

/* ricavare il nome del padre */

padre = albero.parent(pos);

APPENDICE: Codice

n = Integer.parseInt(Spadre);

/* sceglie il minimo tra gli archi */

if (comp == 0)

mybridge = ChooseMin(mio_nodo.vect_alfa[this.n_alb-1]); else

mybridge = ChooseMin(this.alfa_attuale);

/* invia l'arco al genitore */

if (mybridge != null) sendCTo("Choice", mybridge,n); else sendCTo("null", mybridge,n); became(Swapped);

return; }

else {

/* si deve terminare l'algoritmo */

/* invio un messaggio a tutti i figli che a */

/*loro volta lo invieranno ai loro figli... */

PositionIterator Pfigli = albero.children(pos); String Sfiglio; int figlio; while(Pfigli.hasNext()) { Sfiglio = Pfigli.nextPosition().element().toString(); figlio = Integer.parseInt(Sfiglio);

sendRTo("Done", null, figlio, null);

}

became(Done); return;

} }

public void done () {

/* il nodo deve memorizzare il proprio swap-edge */

if (LX.isEmpty()) estratto = null; else{ estratto = ChooseMin(mio_nodo.vect_alfa[this.n_alb-1]); this.swap_edge = estratto; } return; }