Tesina ASD 2

Elaborato in Algoritmi e Strutture Dati

- Corso di Laurea Magistrale in Ingegneria Informatica -

Anno Accademico 2014/2015

PASQUALE AMORUSO M63/000502

GIANFRANCO BALZANO M63/000546

Indice

Indice .................................................................................................................................................... 2 Introduzione ......................................................................................................................................... 3

Capitolo 1: Bucket-Sort ....................................................................................................................... 4 1.1 Intro ............................................................................................................................................ 4 1.2 Codice ........................................................................................................................................ 5

1.2.1 File Header (.h) ................................................................................................................... 5

1.2.2 BucketSort (.cpp) ................................................................................................................ 6 1.2.3 Main (.cpp) .......................................................................................................................... 8

1.3 Grafici e Tempi di esecuzione ................................................................................................. 10 1.3.1 CASO MEDIO .................................................................................................................. 10 1.3.1 CASO PEGGIORE ........................................................................................................... 13

Capitolo 2: Heap-Sort ........................................................................................................................ 16 2.1 Intro .......................................................................................................................................... 16

2.1 Codice ...................................................................................................................................... 17 2.1.1 File Header (.h) ................................................................................................................. 17

2.1.2 HeapSort (.cpp) ................................................................................................................. 18 2.2 Grafici e Tempi di esecuzione ................................................................................................. 25

2.2.1 Complessità n*log(n) ........................................................................................................ 25

2.2.2 Confronto tra due versioni di Build Max Heap................................................................. 27 2.2.3 Heap Extract Max su coda di max-priority ....................................................................... 28

Capitolo 3: Strongly-Connected-Components ................................................................................... 29 3.1 Intro .......................................................................................................................................... 29 3.2 Codice ...................................................................................................................................... 30

3.2.1 File Header (.h) ................................................................................................................. 30

3.2.2 SSC (.cpp) ......................................................................................................................... 31 3.2.3 Main (.cpp) ........................................................................................................................ 36

3.3 Tempi di esecuzione................................................................................................................. 37

Introduzione

In questo elaborato sono discusse le principali caratteristiche di tre particolari

algoritmi (Bucket-Sort, Heap-Sort e Strongly-Connected-Components), di cui i

primi due appartengono alla categoria degli algoritmi di ordinamento, mentre il terzo

a quella delle ricerche su grafi.

Di questi algoritmi, dopo una breve introduzione, viene riportato il codice

implementato in C++ e i tempi di esecuzione sotto forma di tabelle e grafici realizzati

in Excel, al fine di poterli opportunamente confrontare con quelli teorici ottenuti dall'

analisi asintotica.

A tale scopo, è stato utilizzato Eclipse IDE Luna for C++ Developers come ambiente

di sviluppo.

Capitolo 1: Bucket-Sort

1.1 Intro

Il Bucket Sort è un particolare algoritmo di ordinamento che lavora sul posto

su di un input generato da un processo casuale che distribuisce gli elementi

uniformemente e indipendentemente nell’intervallo [0,1) e che ha tempo lineare di

esecuzione pari a (n).

Partendo da un array di input di n elementi, il codice richiede che ci sia un

vettore ausiliario di liste concatenate, detto bucket, su cui viene eseguito

l’ordinamento. Infine è necessario concatenare le varie liste ordinate per realizzare

l’ordinamento complessivo dei valori dell’input.

Bucket Sort necessita dell’algoritmo di ordinamento Insertion Sort per ordinare

gli elementi di ciascuna lista. In particolare, poiché è noto che la complessità nel caso

peggiore di Insertion Sort è dell’ordine di O(n^2), il tempo di esecuzione nel caso

peggiore del BS è pari a:

T(n) =

Tuttavia è possibile calcolare il valore atteso del tempo di esecuzione di Bucket Sort

che, quindi, nel caso medio risulta uguale a (n).

1.2 Codice

Di seguito è riportato il codice in C++ organizzato secondo la

“programmazione a moduli” che prevede la creazione di un progetto contenente, oltre

al programma principale di esecuzione dell’algoritmo (main.ccp), anche il modulo

relativo alle diverse funzioni richiamate dallo stesso (bucketsort.cpp) e una libreria

che le include (lib.h).

1.2.1 File Header (.h)

In questo file è definita la struttura del componente base di ciascun bucket,

insieme alle principali funzioni da eseguire su ciascuno di essi :

#ifndef LIB_H_

#define LIB_H_

#include <cstdlib>

#include <iostream>

#include <vector>

#include <math.h>

#include <stdlib.h>

typedef struct ns {

float data;

struct ns *next;

} node;

void bucket_sort (float A[], int, int); // ordinamento secondo Bucket Sort

node* insertion_sort (node *); // ordinamento secondo Insertion Sort

void printBuckets(node *); // stampa dei valori presenti nei buckets

void print(float A[], int ); // stampa vettore di input ordinato

#endif /* LIB_H_ */

1.2.2 BucketSort (.cpp)

In questo file è implementato il corpo principale dell’algoritmo, insieme alle

procedure interne da richiamare definite nella libreria « lib.h »:

#include <cstdlib>

#include <iostream>

#include <stdlib.h>

#include "lib.h"

using namespace std;

void bucket_sort (float A[], int dim, int dim_B)

{

node **B;

B = (node **)malloc(sizeof(node *)*(dim_B));

for (int i=0; i<dim_B; i++)

{

B[i]=NULL;

}

float divisore = float(dim)/float(dim_B);

for (int j=0; j<dim; j++)

{

node *n = (node *) new node;

n->data = A[j];

//cout<<A[j]<<" "<<int(floor(dim*A[j]))<<" "<<divisore<<"

"<<floor((dim*A[j])/divisore)<<"\n";

n->next = B[int(floor((dim*A[j])/divisore))];

B[int(floor((dim*A[j])/divisore))] = n;

}

/* for(int i = 0; i < dim; i++)

{

cout << "Bucket[" << i << "] : ";

printBuckets(B[i]);

cout << endl;

}*/

for (int z=0; z<dim_B; z++)

{

B[z]=insertion_sort(B[z]);

}

int giro = 0;

for (int h=0; h<dim_B; h++)

{

while(B[h]!=NULL)

{

A[giro]=B[h]->data;

B[h]=B[h]->next;

giro++;

}

}

}

In questa procedura, si istanzia un nuovo bucket con la funzione ‘malloc’ e, dopo

averlo inizializzato, si allocano le liste con i valori di input.

Dopodichè, viene eseguito l’insertion sort su ciascuna lista, in modo che l’input sia

ordinato correttamente in seguito alla concatenazione delle liste ordinate.

node *insertion_sort (node *C)

{

int j, l = 0;

float key =0.0;

std::vector<float> appoggio;

while (C!=NULL)

{

appoggio.push_back (C->data);

node *n = C->next;

delete C;

C = n;

}

for (int i=1; i< appoggio.size(); i++)

{

j = i;

while (j>0 && appoggio[j-1]>appoggio[j])

{

key = appoggio[j];

appoggio[j] = appoggio[j-1];

appoggio[j-1] = key;

j--;

}

}

for (int z=appoggio.size()-1; z>=0 ; z--)

{

node *n = (node *) new node;

n->data = appoggio[z];

n->next = C;

C = n;

}

return C;

}

void printBuckets(node *list)

{

node *current = list;

while(current) {

cout << "\t" << current->data;

current = current->next;

}

}

Questa procedura stampa a video il contenuto di tutto il bucket.

void print(float A[], int dim)

{

for(int i = 0; i < dim; i++)

{

cout << "\n" << A[i];

}

cout << endl;

}

Questa procedura stampa a video il contenuto di tutto il vettore di input ordinato.

1.2.3 Main (.cpp)

Viene qui presentato il main del programma, dove vengono effettuati vari test

sul funzionamento dell’algoritmo. In particolare è testato un caso peggiore a partire

da un vettore A di input ordinato in modo decrescente (caso peggiore dell’insertion

sort e quindi del bucket sort), avendo però a disposizione un bucket di una sola

posizione. Inoltre, per testare il funzionamento nel caso medio, è allocato un bucket

di un ordine di grandezza inferiore al numero di elementi da ordinare, così da causare

delle concatenazioni (‘collisioni’) all’interno delle posizioni del bucket.

#include <cstdlib>

#include <stdio.h>

#include <iostream>

#include <time.h>

#include "lib.h"


int main(int argc, char *argv[])

{

srand(time(NULL));

clock_t t;

//CASO PEGGIORE (con A ordinato in modo decrescente):

/*

float A[500];

int dim_B = 1; // Bucket B di una sola posizione!

t = clock ();

for (int l = 0; l<100; l++)

{

for (int j = 0; j<(sizeof(A)/sizeof(float)); j++) // inizializzare e

ordinare A in modo decrescente

{

A[j] = (float(j)/(sizeof(A)/sizeof(float)));

}

bucket_sort(A,(sizeof(A)/sizeof(float)), dim_B);

}

t = clock () - t;

cout <<"\n";

printf("%10.9f\n",(((double)(t))/CLOCKS_PER_SEC));

*/

//CASO PEGGIORE (con A ordinato in modo casuale):

/*

float A[500];

int dim_B = 1; // Bucket B di una sola posizione!

t = clock ();

for (int l = 0; l<100; l++)

{

for (int i=0; i<(sizeof(A)/sizeof(float)); i++)

{

A[i] = static_cast<float>(rand())/static_cast<float>(RAND_MAX);

}


}

t = clock () - t;

cout <<"\n";


*/

//CASO MEDIO:

float A[3000];

int dim_B = 10; // Bucket B di 10 posizioni!

t = clock ();

for (int l = 0; l<100; l++)

{

for (int i=0; i<(sizeof(A)/sizeof(float)); i++)

{

A[i] = static_cast<float>(rand())/static_cast<float>(RAND_MAX);

}


}

t = clock () - t;

cout <<"\n";


/*cout<<(sizeof(A)/sizeof(float))<<"\n";

cout << "Initial array: " << endl;

print(A,(sizeof(A)/sizeof(float)));

cout << "-------------" << endl;

cout << "-------------" << endl;

cout << "Sorted array: " << endl;

print(A, (sizeof(A)/sizeof(float)));

*/

//system("PAUSE");

return EXIT_SUCCESS;

}

I due cicli ‘for’ innestati consentono di calcolare i tempi di esecuzione dell’algoritmo,

eseguendolo un numero di iterazioni tali da rendere più dettagliati i risultati.

1.3 Grafici e Tempi di esecuzione

1.3.1 CASO MEDIO

Per CASO MEDIO si intende avere a disposizione un bucket B di dimensione

crescente (perchè altrimenti l’algoritmo sarebbe caduto nel caso peggiore) per un

massimo di circa un paio di ordini di grandezza inferiore al numero di elementi di A

ordinato casualmente.

Tabella:

n bucketsort c2 c1 n (caso medio)

10 0,0000281 1,31579E-05 5,26316E-05 10

20 0,0000313 2,63158E-05 0,000105263 20

30 0,0000609 3,94737E-05 0,000157895 30

40 0,0001107 5,26316E-05 0,000210526 40

50 0,0000797 6,57895E-05 0,000263158 50

60 0,0001068 7,89474E-05 0,000315789 60

70 0,0001318 9,21053E-05 0,000368421 70

80 0,0001449 0,000105263 0,000421053 80

90 0,0001594 0,000118421 0,000473684 90

100 0,0001062 0,000131579 0,000526316 100

125 0,0001032 0,000164474 0,000657895 125

150 0,0002097 0,000197368 0,000789474 150

175 0,0002813 0,000230263 0,000921053 175

200 0,000225 0,000263158 0,001052632 200

250 0,000437 0,000328947 0,001315789 250

300 0,000562 0,000394737 0,001578947 300

350 0,0005 0,000460526 0,001842105 350

400 0,000437 0,000526316 0,002105263 400

450 0,000923 0,000592105 0,002368421 450

500 0,001235 0,000657895 0,002631579 500

600 0,001263 0,000789474 0,003157895 600

700 0,001752 0,000921053 0,003684211 700

800 0,001453 0,001052632 0,004210526 800

900 0,001094 0,001184211 0,004736842 900

1000 0,0027 0,001315789 0,005263158 1000

1100 0,002622 0,001447368 0,005789474 1100

1200 0,003391 0,001578947 0,006315789 1200

1300 0,003044 0,001710526 0,006842105 1300

1400 0,003262 0,001842105 0,007368421 1400

1500 0,00469 0,001973684 0,007894737 1500

1600 0,00484 0,002105263 0,008421053 1600

1700 0,00734 0,002236842 0,008947368 1700

1800 0,00797 0,002368421 0,009473684 1800

1900 0,00953 0,0025 0,01 1900

2000 0,0103 0,002631579 0,010526316 2000

3000 0,01469 0,003947368 0,015789474 3000

4000 0,00797 0,005263158 0,021052632 4000

5000 0,01103 0,006578947 0,026315789 5000

6000 0,01328 0,007894737 0,031578947 6000

7000 0,01062 0,009210526 0,036842105 7000

8000 0,0202 0,010526316 0,042105263 8000

9000 0,01375 0,011842105 0,047368421 9000

10000 0,0313 0,013157895 0,052631579 10000

15000 0,031 0,019736842 0,078947368 15000

20000 0,11 0,026315789 0,105263158 20000

25000 0,062 0,032894737 0,131578947 25000

30000 0,218 0,039473684 0,157894737 30000

35000 0,11 0,046052632 0,184210526 35000

40000 0,391 0,052631579 0,210526316 40000

45000 0,422 0,059210526 0,236842105 45000

50000 0,548 0,065789474 0,263157895 50000

60000 0,515 0,078947368 0,315789474 60000

70000 1,058 0,092105263 0,368421053 70000

80000 1,288 0,105263158 0,421052632 80000

90000 1,721 0,118421053 0,473684211 90000

100000 1,946 0,131578947 0,526315789 100000

150000 3,367 0,197368421 0,789473684 150000

Dopo aver generato casualmente (funzione random()) i valori del vettore di input da

ordinare, per calcolare i tempi di esecuzione di questo algoritmo è stato necessario

eseguire il codice più volte, per una maggior precisione di calcolo dei valori dei

tempi; in particolare:

- per n = 10 - 200 è stato scelto di eseguirlo 10000 volte;



- per n = 10000 in poi è stato scelto di eseguirlo 10 volte;

Si tiene presente che la dimensione del bucket è pari a 10 (10 posizioni -> 10 liste)

per input fino a 3000 (3000 elementi da ordinare), mentre è pari a 100 per input

superiori, fino ad un numero di elementi tale da trovarsi ad un passo prima del caso

peggiore.

Grafico:

Dai tempi riportati in tabella e graficati in Excel si evince che l’algoritmo in

questione mostra un andamento lineare, rispetto ai valori dei tempi riportati

sull’asse y. Infatti, nel caso medio, la complessità del Bucket Sort è pari a (n).

Nota: Una curva “spezzata” di questo tipo indica che il calcolo dei tempi è

influenzato dallo stato in cui si può trovare la macchina a tempo di esecuzione.

0

0,005

0,01

0,015

0,02

0,025

0,03

BucketSort

c1

c2

1.3.1 CASO PEGGIORE

Per CASO PEGGIORE si intende avere a disposizione un bucket B di dimensione

pari a 1 (o relativamente piccola rispetto alla dimensione dell’input) e un vettore di

input A ordinato in modo decrescente.

Tabella:

n bucketsort c2 c1 n^2

10 0,0000078 0,0000002 0,000002 100

50 0,0000453 0,000005 0,00005 2500

100 0,000551 0,00002 0,0002 10000

105 0,000531 0,00002205 0,0002205 11025

110 0,000594 0,0000242 0,000242 12100

115 0,000781 0,00002645 0,0002645 13225

120 0,000703 0,0000288 0,000288 14400

125 0,000774 0,00003125 0,0003125 15625

150 0,000328 0,000045 0,00045 22500

200 0,000547 0,00008 0,0008 40000

500 0,01125 0,0005 0,005 250000

510 0,01116 0,0005202 0,005202 260100

520 0,01101 0,0005408 0,005408 270400

530 0,01173 0,0005618 0,005618 280900

540 0,01616 0,0005832 0,005832 291600

550 0,01431 0,000605 0,00605 302500

560 0,01415 0,0006272 0,006272 313600

570 0,01596 0,0006498 0,006498 324900

580 0,0187 0,0006728 0,006728 336400

590 0,01548 0,0006962 0,006962 348100

600 0,01529 0,00072 0,0072 360000

1000 0,04111 0,002 0,02 1000000

1010 0,04094 0,0020402 0,020402 1020100

1020 0,04313 0,0020808 0,020808 1040400

1030 0,04253 0,0021218 0,021218 1060900

1040 0,04377 0,0021632 0,021632 1081600

1050 0,0424 0,002205 0,02205 1102500

2000 0,0481 0,008 0,08 4000000

5000 0,31 0,05 0,5 25000000

10000 1,22 0,2 2 100000000

25000 7,5 1,25 12,5 625000000

50000 29,935 5 50 2500000000

100000 122,42 20 200 10000000000

Per determinati intervalli di input:



- per n = 2000 – (<10000) è stato scelto di eseguirlo 10 volte;

- per n = 10000 in poi è stato scelto di eseguirlo 1 volta, poiché all’aumentare di n si

notava un crescente rallentamento dell’elaborazione del calcolo del tempo di

esecuzione.

Grafico:


questione mostra un andamento quadratico, nel rispetto del risultato ottenuto dalla

sua analisi asintotica.

0

50

100

150

200

250

BucketSort

c1

c2

Infatti, nel caso peggiore l’algoritmo Insertion Sort contribuisce con un fattore pari a

O( ) per ordinare gli elementi di ciascuna lista.

In particolare, questo tipo di andamento è maggiormente evidente per valori di input

molto grandi, come riportato dal grafico.

Infine, sulla base dei tempi trovati, sono state calcolate le due costanti, c1 e c2, che

definiscono l’intervallo temporale in cui si colloca l’esecuzione dell’algoritmo (linea

blu), dividendo così ciascun valore dei tempi asintotici per due costanti che

differiscono per uno o più ordini di grandezza.

Capitolo 2: Heap-Sort

2.1 Intro

L’Heap Sort è un altro particolare algoritmo di ordinamento sul posto che

utilizza una struttura dati (heap) per gestire le informazioni e per poter realizzare

anche un’ efficiente coda di priorità.

L’ heap (binario) è composto dall’ array di input considerato come un albero

binario completo, in cui ad ogni nodo dell’albero corrisponde un elemento dell’array.

Questo albero viene riempito da sinistra verso destra in modo che tutti i livelli

vengano completamente riempiti, tranne eventualmente l’ultimo.

Esistono due tipi di heap: max-heap e min-heap. Di seguito è mostrata

l’implementazione dell’ Heap Sort sulla base della creazione di un max-heap secondo

cui l’elemento più grande è memorizzato nella radice e il sottoalbero di un nodo

(padre) contiene valori non maggiori di quello contenuto nel nodo (padre) stesso.

Dato che le operazioni fondamentali sugli heap vengono eseguite in un tempo

che è al massimo proporzionale all’altezza dell’albero (lg(n)), il tempo di esecuzione

complessivo dell’ Heap Sort è pari a O(n* ). In particolare, sia il caso migliore

che il caso peggiore sono limitati inferiormente da una complessità pari a

(n* ).

2.1 Codice




relativo alle diverse funzioni necessarie richiamate dall’ algoritmo stesso

(heapsort.cpp) e una libreria che le potesse includere (lib.h).


In questo file sono definite le principali procedure eseguite da Heap Sort per

eseguire correttamente l’ordinamento; inoltre, sono state definite le procedure utili

per poter realizzare un’ efficiente coda di priorità sulla base della creazione di max-

heap:

#ifndef HEAPSORT_LIB_H_

#define HEAPSORT_LIB_H_

#include <stdio.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <stdlib.h>


int Parent (int );

int Left (int );

int Right (int );

// Procedure per coda di priorità: void Heap_Increase_Key (std::vector<int> & , int , int );

void Max_Heap_Insert (std::vector<int> & , int );

int Heap_Extract_Max (std::vector<int> & );

void Max_Heapify (std::vector<int> & , int ); // Proprietà max-heap

void Min_Heapify (std::vector<int> & , int ); // Proprietà min-heap void My_Min_Heap (std::vector<int> & A);

// convertire l’array in un max-heap (Max_Heapify eseguita “bottom-up”): void Build_Max_Heap (std::vector<int> & );

void Build_Max_Heap_1 (std::vector<int> & ); // Build Max Heap come Esercizio 6)

void Heapsort (std::vector<int> & );

void Heapsort_1 (std::vector<int> & ); // Heap Sort con la Buil_Max_Heap_1:

#endif /* HEAPSORT_LIB_H_ */

2.1.2 HeapSort (.cpp)

In questo file è implementato il corpo principale dell’algoritmo, insieme alle

procedure interne da richiamare definite nella libreria « lib.h » :

#include "lib.h"

#include <stdio.h>

#include <iostream>

int Parent (int i) // ritorna la posizione del padre del nodo corrente {

return int(floor(i/2));

}

int Left (int i) // ritorna la posizione del figlio sinistro del nodo corrente {

return ((2*i)+1);

}

int Right (int i) // ritorna la posizione del figlio destro del nodo corrente {

return ((2*i)+2);

}

void Heap_Increase_Key (std::vector<int> & A, int i, int key)

{

// stampa errore se la chiave da inserire è più piccola di quella già presente: if (key < A[i])

{

cout<<"La nuova chiave è più piccola di quella corrente\n";

}

// scambia la chiave del padre con quello del figlio se più piccola: A[i] = key;

while (i>0 && A[Parent(i)]<A[i])

{

std::swap(A[Parent(i)],A[i]);

i = Parent(i);

}

}

Questa procedura implementa l’incremento della chiave di un determinate nodo,

scambiando eventualmente il valore della nuova chiave del nodo corrente con quella

del padre se quest’ultimo è ha un valore di chiave più piccolo.

void Max_Heap_Insert (std::vector<int> & A, int key)

{

A.push_back(-999);

Heap_Increase_Key(A, A.size()-1, key);

}

Questa procedura implementa l’inserimento di un nuovo nodo con un determinato

valore di chiave, chiamando la Increase_Key per effettuare l’inserimento.

La push_back inizializza il valore di chiave del nuovo nodo prima dell’inserimento

del valore di chiave.

int Heap_Extract_Max (std::vector<int> & A)

{

if (A.size() < 1)

{

cout<<"Underflow dell'heap\n";

}

int max = A[0];

A[0] = A[A.size()-1];

A.resize(A.size()-1);

Max_Heapify (A,0);

return max;

}

Questa procedura implementa l’estrazione del valore di chiave più grande presente

nell’albero, che per definizione è l’elemento presente in cima, in prima posizion.

Viene assegnato in cima l’ultimo elemento dell’albero, eliminando poi la posizione

del valore tramite la resize. Dopodichè è necessario richiamare la Heapify per

ripristinare la proprietà di max-heap.

void Max_Heapify (std::vector<int> & A, int i)

{

int massimo, provvisorio_1, provvisorio_2= 0;

int l = Left(i);

int r = Right(i);

if (l <= (A.size()-1) && A[l]>A[i])

{

massimo = l;

}

else

{

massimo = i;

}

if (r<= (A.size()-1) && A[r]>A[massimo])

{

massimo = r;

}

if (i != massimo)

{

std::swap(A[i],A[massimo]);

Max_Heapify(A,massimo);

}

}

E’ la procedura tramite la quale viene soddisfatta la proprietà di max-heap,

controllando quale tra nodo corrente e i due possibili figli ha il valore di chiave più

grande. In questo caso il valore massimo è assegnato al nodo (padre) corrente.

void Min_Heapify (std::vector<int> & A, int i)

{

int minimo, provvisorio_1, provvisorio_2= 0;

int l = Left(i);

int r = Right(i);

if (l <= (A.size()-1) && A[l]<A[i])

{

minimo = l;

}

else

{

minimo = i;

}

if (r<= (A.size()-1) && A[r]<A[minimo])

{

minimo = r;

}

if (i != minimo)

{

std::swap(A[i],A[minimo]);

Min_Heapify(A,minimo);

}

}

E’ la procedura tramite la quale viene soddisfatta la proprietà di min-heap,

controllando quale tra nodo corrente e i due possibili figli ha il valore di chiave più

piccolo. In questo caso il valore minimo è assegnato al nodo (padre) corrente.

Di seguito è mostrata una procedura simile per soddisfare la proprietà di min-heap:

void My_Min_Heap (std::vector<int> & A){

for (int l=0; l<A.size(); l++)

{

if (A[l]==-1)

A[l] = rand()%50;

if ((2*l)+1 < A.size())

{

A[(2*l)+1] = A[l] + rand()%10 + 1;

}

if ((2*l)+2 < A.size())

{

A[(2*l)+2] = A[l] + rand()%10 + 1;

}

}

}

void Build_Max_Heap (std::vector<int> & A)

{

for(int i=(int(floor((A.size()-1)/2)));i>=0;i--)

{

Max_Heapify(A,i);

}

}

Questa procedura richiama la Max_Heapify per soddisfare il vincolo di max-heap su

tutto l’albero, controllandolo dal basso verso l’alto.

void Build_Max_Heap_1 (std::vector<int> & A)

{

std:vector<int> B;

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

{

Max_Heap_Insert(B,A[i]);

}

for (int j=0; j<A.size(); j++)

{

A[j]=B[j];

}

}

Quest’altro tipo di Build si serve della procedura Max_Heap_Insert per costruire

max-heap sull’intero albero.

void Heapsort (std::vector<int> & A)

{

Build_Max_Heap(A);

for (int i=int(A.size()-1);i>=1;i--)

{

std::swap(A[0],A[i]);

//cout<<A[i]<<" ";

//system("PAUSE");

A.pop_back();

Max_Heapify(A,0);

}

A.pop_back();

//cout<<A[0]<<" ";

}

void Heapsort_1 (std::vector<int> & A)

{

Build_Max_Heap_1(A);

for (int i=int(A.size()-1);i>=1;i--)

{

std::swap(A[0],A[i]);

//cout<<A[i]<<" ";

//system("PAUSE");

A.pop_back();

Max_Heapify(A,0);

}

//cout<<A[0]<<" ";

}

Infine, queste due procedure implementano l’algoritmo Heap Sort chiamando,

rispettivamente, la Build_Max_Heap e la Build_Max_Heap_1 per costruire max-heap

sull’intero albero. Il ciclo for che segue permette di ripristinare la proprietà di max-

heap, dopo aver scambiato il valore di cima con l’ultimo per eseguire l’ordinamento

finale del vettore di input.

2.1.3 Main (.cpp)

#include <cstdlib>

#include <stdio.h>

#include <iostream>

#include <time.h>

#include <algorithm>

#include "lib.h"



{

srand(time(NULL));

clock_t t, t_sort, t_insert;

std::vector<int> A;

std::vector<int> SCH;

/*

// CASO PEGGIORE: COSTRUZIONE ALBERO MIN HEAP ED

// ESECUZIONE DI HEAPSORT CON PROCEDURA MAX HEAPIFY (nel caso peggiore)

// A casuale

for (int i=0; i<1572864; i++)

{

A.push_back(rand()%100);

}

Min_Heapify(A,0);

t = clock ();

for (int e = 0; e < 1; e++)

{

Heapsort (A);

}

t = clock () - t;

/*

//ESECUZIONE HEAPSORT CON PROCEDURA MAX HEAPIFY

// con A ordinato in modo crescente

for (int i=0; i<12582912; i++)

{

A.push_back(i);

}

t = clock ();

for (int e = 0; e < 1; e++)

{

Heapsort (A);

}

t = clock () - t;

//ESECUZIONE HEAPSORT CON PROCEDURA MAX HEAPIFY

// con A ordinato in modo decrescente

for (int i=12582912; i>-1; i--)

{

A.push_back(i);

}

t = clock ();

for (int e = 0; e < 1; e++)

{

Heap_Extract_Max (A);

}

t = clock () - t;

*/

// A casuale (vedere Tabella in Tesina)

cout <<"\n";

std::cout.setf( std::ios::fixed, std:: ios::floatfield );

std::cout.precision(9);

cout <<(((double)(t))/CLOCKS_PER_SEC)<<"\n";

//system("PAUSE");


}

2.1.3.1 Build Max Heap

/*cout<<"VETTORE A - BUILD MAX HEAP v1: ";

Build_Max_Heap(A);

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

{

cout<<A[i]<<" ";

}

cout<<"\n\n";

Build_Max_Heap(B);

cout<<"VETTORE B - BUILD MAX HEAP v2 [ES. 6.1]: ";

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

{

cout<<B[i]<<" ";

}*/

Con questo blocco viene chiamata la Build_Max_Heap sul vettore A e la

Build_Max_Heap_1 sul vettore B, generando il seguente risultato in console:

Dall’ output si può notare che le due procedure, a partire dallo stesso input, non

generano lo stesso heap, in quanto mentre con la Build_Max_Heap la proprietà dell’

heap viene rispettata dopo aver creato tutto il vettore di input e quindi il suo

corrispondente albero analizzandolo dal basso verso l’alto, la Build_Max_Heap_1,

invece, chiamando la procedura Heap_Increase_Key, rispetta la proprietà ad ogni

successivo inserimento.

2.1.3.2 Heap Extract Max

// COSTRUZIONE HEAP e SCHEDULAZIONE “PROCESSI” tramite HEAP EXTRACT MAX

for (int i=0; i<1000; i++)

{

A.push_back(rand()%100);

}

/* for (int i=0; i<A.size(); i++)

{

cout<<A[i]<<" ";

}

*/

cout<<"\n\n";

Build_Max_Heap (A);

/* for (int i=0; i<A.size(); i++)

{

cout<<A[i]<<" ";

}

cout<<"\n\n";

*/

int dim_A = A.size();

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

SCH.push_back(Heap_Extract_Max(A));

sort(SCH.begin(), SCH.end(), greater<int>());

int j = rand()%10;

if (j == rand()%10){

int key = rand()%100;

Max_Heap_Insert(A, key);

dim_A = dim_A + 1;

// cout<<"\nè stata inserita una nuova chiave: "<<key<<"\n";

}

}

for(std::vector<int>::const_iterator i = SCH.begin(); i != SCH.end(); i++){

std::cout << *i <<"\n";}

Con questo codice viene simulata la schedulazione di processi da eseguire

eventualmente su un computer condiviso. E’ stata quindi creata una coda di max-

priority che tiene traccia dei lavori da svolgere e delle loro relative priorità.

Lo scheduler ha il compito di selezionare il processo con priorità più alta tra quelli in

attesa nella coda chiamando la Heap Extract Max sul vettore di input dei processi. In

particolare la lista dei processi (vettore A) da eseguire può essere in qualsiasi

momento aggiornata dallo scheduler che può aggiungere un nuovo lavoro chiamando

la Max Heap Insert sul vettore.

2.2 Grafici e Tempi di esecuzione

2.2.1 Complessità n*log(n)

Un possibile CASO PEGGIORE consiste nell’ eseguire l’Heap Sort (con Max

Heapify) su di un albero binario costruito secondo la proprietà del Min Heap.

Un possibile CASO MIGLIORE consiste nell’ eseguire l’Heap Sort (con Max

Heapify) su di un albero binario già costruito secondo la proprietà del Max Heap.

In entrambi i casi, i tempi di esecuzione sono dell’ordine di n*log(n). Inoltre, questi

tempi possono essere maggiorati da tali considerazioni:

- avere come input un numero di elementi (ordinati casualmente) tali che l’albero

binario risultante abbia l’ultimo livello dei nodi riempito esattamente a metà, allo

scopo di spingere al massimo la Max Heapify;

- avere come input un numero di elementi già ordinati (in modo crescente), tali che

l’albero binario risultante sia un min heap, allo scopo di spingere al massimo la Build

Max Heap;

Invece, un limite inferiore per n*log(n) può essere ricercato a partire da un vettore di

input ordinati in modo decrescente, tale che l’albero binario risultante sia già un max

heap.

Tabella:

n heapsort c2 c1 n*log(n)

393216 0,344 0,146158092 0,487193641 7307904,615

786432 0,734 0,308044825 1,026816082 15402241,23

1572864 1,516 0,647546929 2,158489764 32377346,46

3145728 3,154 1,358008418 4,526694728 67900420,92

6291456 6,625 2,841845957 9,472819856 142092297,8

12582912 14,068 5,935350153 19,78450051 296767507,7

Per calcolare i tempi di esecuzione in questo caso peggiore, data la grandezza

dell’input, il codice è stato eseguito una sola volta.

Grafico:


questione mostra un andamento compreso tra due curve di tipo n*log(n), nel

rispetto del risultato ottenuto dalla sua analisi asintotica.

Infatti, la complessità dell’algoritmo è dell’ordine di O(n*log(n)), in quanto la

Build_Max_Heap costruisce un max heap da un array in input non ordinato in tempo

lineare, mentre la Max_Heapify impiega un tempo logaritmico, rispetto al numero di

nodi dell’albero.

0

5

10

15

20

25

393216 786432 1572864 3145728 6291456 12582912

HeapSort

c1

c2

Infine, sulla base dei tempi trovati, sono state calcolate le due costanti, c1 e c2, che

definiscono l’intervallo temporale in cui si colloca l’esecuzione dell’algoritmo (linea

blu), dividendo così ciascun valore dei tempi asintotici per due costanti che

differiscono per uno o più ordini di grandezza.

2.2.2 Confronto tra due versioni di Build Max Heap

Di seguito sono riportati i tempi di esecuzione impiegati dalle due versioni di Build-

Max_Heap precedentemente discusse. Si può notare che, a parità di input, la v2

mostra un tempo maggiore della v1 in quanto, secondo l’analisi asintotica, richiede

un tempo (n* ) per costruire un heap di n elementi, contro un limite

asintoticamente più stretto pari a (n) che caratterizza la versione v1.

n build_max_heap_v1 build_max_heap_v2 (n) (n*log(n))

10 0,00001 0,00008 10 33,21928095

Qui, invece, sono riportati i tempi di esecuzione impiegati dalle due versioni di Heap

Sort precedentemente discusse. Dai dati ottenuti per le Build, ci si può aspettare che,

a parità di input, la v2 impiega un tempo maggiore della v1, per la presenza del

logaritmo. Al lato è riportato anche un valore di limite superiore corrispondente alla

complessità (n* ):

n heap_v1 heap_v2 (n*log(n))

1000000 1,213 1,444 19931568,57

2.2.3 Heap Extract Max su coda di max-priority

E’ possibile confrontare i tempi di esecuzione di questa funzione con i propri limiti

asintotici, pari a log(n), per un numero molto grande di processi (elementi del

vettore) da “schedulare”, di cui si riporta una tabella e un grafico illustrativi

dell’andamento della funzione.

Nota: Per il calcolo di questi tempi è stato necessario escludere quelli relativi alle

altre funzioni che completano la schedulazione attesa.

Tabella:

Grafico:

0

0,0000002

0,0000004

0,0000006

0,0000008

0,000001

0,0000012

0,0000014

100000 1000000 10000000 20000000 50000000

HeapExtractMax

c1

c2

n extract c2 c1 log(n)

100000 0,00000094 6,64386E-07 8,30482E-07 16,60964047

1000000 9,53E-07 7,97263E-07 9,96578E-07 19,93156857

10000000 1,1298E-06 9,3014E-07 1,16267E-06 23,25349666

20000000 1,164E-06 9,7014E-07 1,21267E-06 24,25349666

50000000 1,2294E-06 1,02302E-06 1,27877E-06 25,57542476

Capitolo 3: Strongly-Connected-Components

3.1 Intro

La Strongly-Connected-Components (SCC) rappresenta una particolare

applicazione del meccanismo di visita in profondità in un grafo (orientato) in cui è

possibile trovare le componenti fortemente connesse (SCC), dove per SCC si intende

un insieme di vertici del grafo tale che, per ogni coppia di vertici dell’insieme, questi

sono raggiungibili l’uno dall’ altro.

Il grafo è rappresentato tramite liste di adiacenza, dove ogni lista, una per

ciascun vertice (o nodo) del grafo, contiene tutti i vertici adiacenti al vertice corrente.

Visitare in profondità quindi tale grafo significa ispezionare tutti gli archi

dell’ultimo vertice v scoperto che ha ancora archi da visitare, tornando infine indietro

per ispezionare gli archi che escono dal vertice dal quale v è stato visitato. Inoltre,

tramite un meccanismo di colorazione, un vertice è BIANCO se non è stato ancora

scoperto, GRIGIO se viene scoperto durante la visita ma i suoi adiacenti non sono

stati tutti ispezionati, NERO se è stato completato, cioè se la sua lista di adiacenza è

stata completamente ispezionata.

L’algoritmo, con tempo lineare pari a (V + E), calcola quindi le componenti

fortemente connesse di un grafo orientato, utilizzando due visite in profondità, cioè

una sul grafo G principale e un’altra sulla versione trasposta dello stesso.

3.2 Codice




relativo alle diverse funzioni necessarie richiamate dall’ algoritmo stesso (scc.cpp) e

una libreria che le potesse includere (lib.h).


#ifndef LIB_H_

#define LIB_H_

#include <iostream>

#include <list>

#include <vector>

//macro che ci serviranno dopo per lo svolgimento del codice

#define NIL -1

#define WHITE 0

#define GRAY 1

#define BLACK 2


class Grafo

{

int V; //numero di vertici all'interno del grafo

list<int> *adiacenza; //liste di adiacenza di ogni vertice

void DFS (int [], int [], int [], int [], bool , list<int> []);

void DFS_Visit (int , int [], int , int [], int [], int [], list<int> []);

public:

Grafo(int ); //costruttore

void aggiungi_arco(int , int );

void SCC();

Grafo Trasposto();

};

#endif /* LIB_H_ */

3.2.2 SSC (.cpp)

#include <algorithm>

#include "Lib.h"

Grafo::Grafo(int V){

this->V = V;

adiacenza = new list<int>[V];

}

Questo è il costruttore del grafo che crea V nodi ed inizializza le relative liste di

adiacenza.

void Grafo::DFS (int predecessore [], int inizio [], int fine [], int colore [],

bool trasposto, list<int> visitati []){

static int time = 0;

if (!trasposto)

{

for (int i = 0; i < V; i++)

{

colore[i] = WHITE;

inizio[i] = NIL;

fine[i] = NIL;

predecessore[i] = NIL;

}

for (int i = 0; i < V; i++)

{

if (colore[i] == WHITE)

{

DFS_Visit(i, inizio, time, fine, colore, predecessore, visitati);

}

}

}

else {

int *fine_trasposto = new int[V];

for (int i = 0; i < V; i++)

{

colore[i] = WHITE;

inizio[i] = NIL;

fine_trasposto[i] = NIL;

predecessore[i] = NIL;

}

for (int j=0; j<V; j++)

{

int max, vertice_max = 0;

for (int i=0; i<V; i++)

{

if (max<fine[i])

{

max = fine[i];

vertice_max = i;

}

}

fine[vertice_max]=0;

if (colore[vertice_max]==WHITE

DFS_Visit(vertice_max, inizio, time, fine_trasposto, colore,

predecessore, visitati);

}

}

}

Questa procedura viene chiamata sia per il grafo iniziale che per la sua versione

trasposta. Grazie ad una variabile booleana, viene effettuato un controllo per poter

agire sul grafo normale oppure sul trasposto.

Dopo la fase di inizializzazione, in cui è inizializzata anche una lista dei predecessori

dei vertici volta per volta visitati, la visita procede tramite il meccanismo di

colorazione dei nodi, a partire dal colore BIANCO. Il ramo ‘else’ viene eseguito solo

nel caso in cui si stia operando sul grafo trasposto. Inoltre, è necessario memorizzare

i tempi di fine visita per ciascun vertice del grafo di partenza perchè essenziali per

dare inizio alla visita sul grafo trasposto. A tale scopo viene inizializzato il seguente

vettore :

fine_trasposto[i] = NIL

e ad ogni iterazione vado a trovare il tempo di fine visita più grande calcolato

precedentemente dall'esplorazione del grafo normale. Infine è necessario azzerare tale

tempo perchè così alla prossima iterazione si può prendere il tempo di fine successivo

più grande.

void Grafo::DFS_Visit (int u, int inizio [], int time, int fine [], int colore

[], int predecessore [], list<int> visitati [])

{

time = time+1;

inizio[u] = time;

colore[u] = GRAY;

list<int>::iterator i;

for (i = adiacenza[u].begin(); i != adiacenza[u].end(); i++)

{

int v = *i;

if (colore[v] == WHITE)

{

predecessore[v] = u;

visitati[u].push_back(v);

DFS_Visit(v, inizio, time, fine, colore, predecessore, visitati);

}

else if (colore[v] == GRAY && v!=predecessore[u] &&

predecessore[u]!=NIL)

{

visitati[u].push_back(v);

visitati[predecessore[u]].insert(visitati[predecessore[u]].end(),

visitati[u].begin(), visitati[u].end ());

}

}

if (visitati[u].size()>=1 && u!=0 && predecessore[u]!=NIL)

visitati[predecessore[u]].insert(visitati[predecessore[u]].end(),

visitati[u].begin(), visitati[u].end ());

colore[u] = BLACK;

time = time+1;

fine[u] = time;

}

Dopo aver incrementato il tempo di visita per il vertice corrente e successivamente

assegnato al suo tempo d'inizio esplorazione, si pone a GRIGIO il colore del vertice

attuale, indicando che è in corso la visita del vertice e dei suoi adiacenti.

Una volta memorizzato il vertice successivo nella lista di adiacenza del vertice

corrente, ricordando che u (vertice corrente) è il predecessore di questo vertice

adiacente, salvo questo vertice nella lista di quelli raggiungibili dal vertice attuale.

Se esplorando questo nuovo vertice si raggiunge uno in corso di esplorazione (di

colore GRIGIO) vuol dire che ci si trova in un circolo e quindi salvo la posizione del

vertice grigio che ho trovato e aggiungo la lista dei vertici raggiungibili dal vertice

attuale alla lista dei vertici raggiungibili del suo predecessore.

L’ultimo costrutto ‘if’ viene raggiunto una volta visitati tutti i possibili vertici

adiacenti oppure se un vertice non ha adiacenti. Quando tutti gli adiacenti del nodo

corrente sono stati visitati, questi sono salvati nella lista dei vertici visitabili del

predecessore; inoltre, il costrutto verifica di non aggiungere la lista corrente nel caso

in cui non sono stati visitati nodi e di non aggiungere la lista quando è esplorato il

vertice ‘0’ (vertice sorgente), cioè quindi per non generare errore. Infine, nel caso in

cui si trovano nodi isolati, cioè senza predecessori, si evita di aggiungere la loro lista

di vertici visitati a ‘NIL’.

Quando la visita del vertice corrente termina, il suo colore diventa NERO e viene

incrementato il tempo e memorizzato come tempo di fine scoperta del vertice.

void Grafo::aggiungi_arco(int u, int v)

{

adiacenza[u].push_back(v);

}

Questa procedura aggiunge un arco orientato da un vertice al successivo (il primo

parametro è il vertice di partenza, mentre il secondo paramentro è il vertice di arrivo)

Grafo Grafo::Trasposto()

{

Grafo g(V); for (int v = 0; v < V; v++)

{

list<int>::iterator i;

for(i = adiacenza[v].begin(); i != adiacenza[v].end(); i++)

{

g.adiacenza[*i].push_back(v);

}

}

return g;

}

Questa procedura genera il grafo trasposto del grafo attuale, salvando in maniera

inversa tutte le varie adiacenze.

void Grafo::SCC()

{

int *colore = new int[V];

int *inizio = new int[V];

int *fine = new int[V];

int *predecessore = new int[V];

int *predecessore_trasposto = new int[V];

list<int> *visitati = new list<int>[V];

list<int> *visitati_trasposto = new list<int>[V];

DFS(predecessore, inizio, fine, colore, false, visitati);

Grafo trasposto = Trasposto();

trasposto.DFS (predecessore_trasposto, inizio, fine, colore, true,

visitati_trasposto);

bool stampato [V];


{

stampato[i] = false; }


{

vector<int> scc, scc_trasposto;

vector<int> scc_risultato (V+1);

vector<int>::iterator it;

visitati[i].sort();

visitati_trasposto[i].sort();

list<int>::iterator l,m;

for (l = visitati[i].begin(); l!=visitati[i].end(); l++)

scc.push_back(*l);

for (m = visitati_trasposto[i].begin(); m!=visitati_trasposto[i].end();

m++)

scc_trasposto.push_back(*m);

it=set_intersection (scc.begin(), scc.end(), scc_trasposto.begin(),

scc_trasposto.end(), scc_risultato.begin());

scc_risultato.resize(it-scc_risultato.begin());

if(scc_risultato.empty() && !stampato[i])

//cout<<i<<"\n";

for (it=scc_risultato.begin(); it!=scc_risultato.end(); it++)

{

if (!stampato[*it])

// cout<<*it<<" ";

stampato[*it] = true;

}

// cout<<"\n";

}

}

Questa è la procedura principale per il calcolo delle componenti fortemente connesse

all'interno del grafo di input. I passi dell’algoritmo sono i seguenti:

- chiamo la DFS sul grafo normale

- calcolo il trasposto

- chiamo la DFS, opportunatamente modificata, sul trasposto.

Inoltre, è stata utilizzata la “set_intersection” per trovare eventuali elementi in

comune tra i vertici raggiungibili dal vertice i nel grafo normale e nel grafo trasposto.

Infatti, se ci sono delle intersezioni vuol dire che esiste un percorso a doppio senso tra

i due vertici (u->v e v->u), cioè è soddisfatta la condizione di definizione di

componente fortemente connessa.

Infine, il costrutto if che segue controlla se quel vertice è una componente fortemente

connessa a se stante (cioè formata da un solo vertice) oppure fa già parte di una

componente fortemente connessa, verificando poi se è stato già stampato, per evitare

di mostrare doppioni all’interno della componente.

3.2.3 Main (.cpp)

Qui di seguito viene mostrato il main del programma, con qualche caso di test:

1) E’ stato costruito un grafo con un numero variabile di vertici ma variando quello

degli archi;

2) E’ stato costruito un grafo con un numero variabile di archi ma variando quello dei

vertici.

In entrambi i casi i collegamenti tra i nodi sono stati costruiti in maniera randomica.

#include <cstdlib>

#include <iostream>

#include <time.h>

#include "lib.h"



{

srand(time(NULL));

clock_t t1, t2, t3, t4, t5;

std::cout.setf( std::ios::fixed, std:: ios::floatfield );

std::cout.precision(9);

//Vertici fissati e archi variabili

/*Grafo g1(100);

for (int i=0; i<250; i++)

g1.aggiungi_arco(random()%100,random()%100);

t1 = clock();

for (int i=0; i<10000; i++)

g1.SCC();

t1 = clock() - t1;

cout <<"\nImpiegando un tempo : "<<(((double) (t1))/CLOCKS_PER_SEC)<<"\n";

*/

//Archi fissati e vertici variabili

/*Grafo g1(10000);

for (int i=0; i<100; i++)

g1.aggiungi_arco(random()%10000,random()%10000);

t1 = clock();

for (int i=0; i<10000; i++)

g1.SCC();

t1 = clock() - t1;

cout <<"\nImpiegando un tempo : "<<(((double) (t1))/CLOCKS_PER_SEC)<<"\n";

*/

system("PAUSE");


}

3.3 Tempi di esecuzione

Di seguito sono mostrati i tempi di esecuzione dell’algoritmo sulla base della

creazione randomica dei collegamenti tra i vertici del grafo, consentendo così una

valutazione “media” dei tempi.

3.3.1 V fissato, E variabile

Tabella:

vertici archi SCC

V+E 100 0 0,000106

100

100 50 0,00015

150 100 100 0,000209

200

100 150 0,00193

250 100 200 0,00692

300

100 250 1,476

350 1000 0 0,0045

1000

1000 500 0,0049

1500 1000 1000 0,00606

2000

1000 1500 10,042

2500 10000 0 0,404

10000

10000 1000 0,404

11000 10000 5000 0,404

15000

10000 10000 0,43

20000 10000 11000 0,46

21000

10000 12000 7

22000

Grafici:

Dal grafico si evince un andamento temporale lineare con il numero (fissato) di

vertici e con quello degli archi (variabile: E<=V), nel rispetto del risultato ottenuto

dalla sua analisi asintotica. Per E>V si nota un degrado dei tempi di rendimento

dell’algoritmo.

Infatti, la complessità dell’algoritmo è dell’ordine di (V + E), dove V è il numero

dei vertici, E è numero degli archi.

0

50

100

150

200

0

0,001

0,002

0,003

0,004

0,005

0,006

0,007

100

0

50

100

150

200

Dal grafico si evince un andamento temporale lineare con il numero (fissato) di vertici e con

quello degli archi (variabile: E<=V), nel rispetto del risultato ottenuto dalla sua analisi asintotica.

Infatti, la complessità dell’algoritmo è dell’ordine di (V + E), dove V è il numero dei vertici, E è

numero degli archi.


quello degli archi (variabile: E<=V), nel rispetto del risultato ottenuto dalla sua analisi asintotica.


numero degli archi.

0

500

1000

0

0,001

0,002

0,003

0,004

0,005

0,006

0,007

1000

0

500

1000

0

1000

5000

10000

0,39

0,395

0,4

0,405

0,41

0,415

0,42

0,425

0,43

10000

0

1000

5000

10000

3.3.2 E fissato, V variabile

Tabella:

vertici archi SCC

100 100 0,000209

1000 100 0,0045

2000 100 0,01664

5000 100 0,09828

10000 100 0,39

25000 100 2,41

50000 100 9,639

50000 1000 9,663

50000 5000 9,59

50000 10000 9,61

100000 10000 38,3

100000 30000 38,39

Grafici:

Dal grafico si evince un andamento temporale lineare con il numero (fissato) di

archi e con quello dei vertici (variabile) per E<=V, nel rispetto del risultato

ottenuto dalla sua analisi asintotica.

Infatti, la complessità dell’algoritmo è dell’ordine di (V + E), dove V è il numero

dei vertici, E è numero degli archi.

100

1000 2000

5000 10000

0

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

100

100

1000

2000

5000

10000


quello degli archi (variabile) per E<=V, nel rispetto del risultato ottenuto dalla sua analisi

asintotica.


numero degli archi.


quello degli archi (variabile) per E<=V, nel rispetto del risultato ottenuto dalla sua analisi

asintotica.


numero degli archi.

50000

70000

90000

0

5

10

15

20

25

30

35

1000

50000

70000

90000

100000

150000

200000

0

20

40

60

80

100

120

140

160

180

10000

100000

150000

200000

3.3.3 Caso peggiore (grafo di vertici “isolati”, senza alcun collegamento)

Tabella:

vertici archi SCC

100 0 0,00013

1000 0 0,005

10000 0 0,39

Grafico:

Per V crescente, senza costruire alcun arco tra i vertici, si nota una sostanziale

crescita dei tempi di esecuzione. In particolare, per V>>N, cioè per un numero di

vertici molto grande, si nota un degrado dei tempi di rendimento dell’algoritmo.

In conclusione, dagli esempi mostrati è possibile notare un andamento lineare (@(V+E)) dei tempi

di esecuzione, nel rispetto dell’analisi asintotica dell’intero algoritmo. Infatti:

Passo 1: esecuzione DFS su grafo principale di input -> @(V+E);

Passo 2: esecuzione trasposizione del grafo principale -> O(V+E) (analisi di tutte le liste di

adiacenza dei V vertici che compongono il grafo);

Passo 3: esecuzione DFS su grafo trasposto -> @(V+E);

Passo 4: output finale delle componenti fortemente connesse ricercate -> lineare (operazione di

intersezione).

0

0,05

0,1

0,15

0,2

0,25

0,3

0,35

0,4

0,45

100 1000 10000

SCC

SCC

Date post:	17-Jan-2016
Category:	Documents
Upload:	gianfrancobalzano
View:	41 times
Download:	0 times

Tesina ASD 2

Documents