SDAA

Problema drumurilor minime in grafuri orientate

Specificatia de definire a problemei

Enunt tema

STUDIU:Grafuri orientate.

Problema drumurilor minime cu origine unica - algoritmul lui Dijkstra.

Problema drumurilor minime corespunzatoare tuturor perechilor de noduri - algoritmul lui Floyd. Centrul unui graf.

DEMO: Exemple de utilizare interactiva.

Vizualizare trasee.

1.2 Descrierea cerintelor

-problema drumurilor minime cu origine unica , implementata cu algoritmul lui Dijkstra

-problema drumurilor minime corespunzatoare tuturor perechilor de noduri, implementata cu algoritmul lui Floyd

-determinarea centrului unui graf orientat folosind algoritmul lui Floyd

-exemple de utilizare interactiva:

- aplicarea algoritmului lui Dijkstra cu vizualizarea rezultatului

-aplicarea algoritmului lui Floyd,cu determinarea centrului grafului cu vizualizarea rezultatului

1.3 Specificatia functionala

Implementarea algoritmilor va fi facuta in limbajul C++, iar interfata cu utilizatorul va fi realizata in mod grafic , cu Visual C ++ 6.0.

S-a convenit ca graful orientat va fi implementat cu ajutorul matricei de adiacenta.

Interfata va contine un meniu din care utilizatorul poate ::

crearea grafului de catre utilizator ,utilizatorul poate adauga/ sterge noduri si laturi pentru graful pe care vrea sa testeze algoritmii;

aplicatii pentru cei doi algoritmi in care utilizatorul are posibilitatea de a vedea graful intial sub forma de graf orientat in forma grafica ,de asemenea si rezultatul aplicarii algoitmilor se poate vedea in acceasi maniera.. Utilizatorul isi construieste singur graful orientat cu ajutorul operatiilor de:

adaugare nod

stergere nod

adaugare arc

stergere arc

modificare arc

adugare nume nod

- date despre autorii proiectului

- vizualizare nume nod si distanta dintre noduri

1.4 Interfata utilizator

Interfata cu un utilizator este una complexa ,realizata in maniera grafica .La rularea programului va aparea pe ecran o fereastra care va contine in partea stanga butoane acre activate vor realiza dferite cerinte, iar in partea stanga o subfereastra in care utilizatorul isi formeaza graful in maniera interactiva.

Butoanele care apar in partea dreapta sunt :

AdaugareN - prin care utilizatorul poate aduga noduri pentru a creea graful.Utilizatorul apasa acest buton dupa care ,cu mouse-ul apasa pe fereastra alturata, in locul in care vrea sa apara nodul.Printr-o casuta de dialog i se va cere Numele nodului ,iar daca apasa pe OK informatia este preluata daca utilizatorul nu doreste sa continue (sa nu adauge nodul) apasa pe CANCEL.

AdaugareL prin care utilizatorul poate aduga o latura intre doua noduri.Utilizatorul trebuie sa apese acest buton , dupa care cu mouse-ul doua noduri intre care doreste sa traseze latura.Dupa aceasta va aparea pe ecran o casuta de dialog unde i se cere utilizatorului sa selecteze directia legaturii (deoarece trebuie sa creeze un graf orientat) precum si distanta intre cele doua noduri.Ca ultim pas trebuie apasat pe butonul de OK daca utilizatorul vrea ca datele introduse sa se regaseasca in graf sau CANCEL daca nu.

Editeza - reprezinta modificarea unui nod sau a unei laturi :cu mouse-ul se merge pa nodul/latura pe care dorim sa o stergem si de aici va aprea pe ecran una den cele doua casute de dialog descrise la cele doua butoane de mai sus , in functie editarea unui nod sau a unei laturi.Astfel nodul isi poate schimba numele , iar latura distanta si orientarea.

Stergere - se poate realiza stergera unui nod sau a unui laturi , care trebuie insemnat /insemnata cu mouse-ul dupa activarea acestui buton .

Dijkstra - se apeleaza algoritmul lui Dijkstra pentru graful creat anterior, se va cere printr-o casuta de dialog nodul de pornire pentru algoritmul lui Dijkstra.Se va afisa pe ecran sub forma de graf drumul minim cu origine minima in nodul pentru care s-a aplicat alforitmul.

Floyd - se apleza algoritmul lui Floyd pentru graful creat anterior , se va afisa matricea care rezulta in urma aplicarii algoritmului lui Floyd.Intr-o fereastra de dialog se cere un nod de pornire si in alta un nod de oprire si se va afisa drumul creat intre aceste doua noduri.

Informatii - afiseaza o casuta cu numele autoriilor

Iesire - cand se apeleza se iese din program.

2.Planul de dezvoltare al proiectului

2.1. Obiective generale

Programul trebuie sa realizeze implementarea algoritmilor lui Dijkstra si Floyd si determinarea centrului unui graf.S-a urmarit calcularea drumului minim cu origine unica

,pornind de la un nod al grafului si calcularea drumurilor minime corespunzatoare tuturor perechilor de noduri cu vizualizarea rezultatului sub forma de matrice. Pe aceasta matrice se calculeaza centrul unui graf.

2.2.Discutie

2.2.1.Delimitarea fazelor si taskurilor

Cuprinde defalcarea proiectului in faze si fiecararei faze in activitati (taskuri) specifice acestui proiect.Se vor lua in considerare urmatoarele faze :

-faza de organizare a proiectului;

-faza de definire ;

-faza de proiectare;

-revizia 1 a proiectului;

-faza de programare;

-faza de testare;

-revizia 2 a proiectului;

-faza de acceptare;

-faza de redactare a documentatiei finale a proiectului;

-faza de predare a proiectului;

Faza de organizare a proiectului (redactarea Planului de dezvotare al proiectului).Taskuri specifice.

Impartirea sarcinilor de documentare despre resursele ce trebuie folosite pentru realizarea acestui proiect:

Task1:-documentarea despre algoritmii ce trebuie folositi , descrierea lor pas cu pas

Task2:-documentarea despre mediul de programere care va fi folosit pentru crearea interactiva a comunicarii cu utilizatorul :Visual C++ 6.0

Faza de definire (redactarea Specificatiei de definire aproblemei).Taskuri specifice.

Definirea datelor de intrarea si a celor de iesire:

Task3:-s-a admis ca graful se fie cunoscut de catre algoritmi prin intermediul matricei costurilor

Task4:structura folosita pentru a retine matrice costurilo, numele nodului,culoare cu care se deseneaza nodul, precum si coordonatele pe ecran este:

typedef struct nod

Faza de proiectare (redactarea Specificatiei de proiectare (Arhitectura aplicatiei)). Taskuri specifice

Proiectarea aplicatiei consta in :

Task5:-stabilirea continutului meniului principal in raport cu cerintele priectului ,precum si realizarea meniului cat mai interactiv pentru ca utilizatorul sa poata sa-si realizeze aplicatiile pe exemplele dorite de el ;

Task6:-realizarea dialogului cu utilizatorul acolo unde utilizatorul are acces , mai precis prin butoanele din meniu:AdugareN,AdugareL,Editeaza(mofificare),Stergere,Dijkstra,Floyd;

Revizia 1 a proiectului. Aprobare derulare

Task7:Dupa ce fiecare membru al echipei a realizat taskurile anterioare ,care ii reveneau , s-a realizat reunirea acestor informatii si discutatea lor in vederea alegerii metodelor cele mai potrivite pentru realizarea proiectului.Dupa stabilirea takurilor anterioare se poate trece la implementarea propriu-zisa a algoritmilor si a interfetei cu utilizatorul.

Task8:Revizia 1 este realizata in prezenta tuturor membrilor echipei pentru ca derularea mai departe a depins de realizarile fiecarui membru al echipei;

Faza de programare (redactarea Specificatiei de codificare)

Task9:-implementarea in C++ a algoritmului lui Dijkstra;

Task10:-implementarea in C++ a algoritmului lui Floyd;

Task11:-implementarea in C++ a centrului unui graf;

Task12:-realizarea ferestrei de comunicare cu utilizatorul:fereastra fiind impartita in doua ,partea stanga pentru reprezentarea grafica a grafului, iar in partea dreapta locul pentru butoanele aferenta aplicatiei;

Task13:-realizarea legaturii intre punctele de pe ecran si nodurile grafului;

Task14:-reprezentarea nodurilor prin culori;

Task15:-reprezentarea laturilor si orientarilor lor prin culori;

Task16:-vizualizarea numelui daca se merge cu mouse-ul p un nod si a distantei intre doua noduri daca se merge pe legatura dintre doua noduri;

Fiecare membru al echipei a avut de realizat cateva dintre aceste taskuri.

Faza de testare (redactarea Planului de testare)

Task17:Dupa relizarea taskurilor de la punctul anterior membrii echipei s-au reunit pentru a asambla partile care au fost relizate separat.S-au facut legaturile intre interfata (meniu) ,butoane care fiecare face ceva specific , algoritmii aplicatiei.

Revizia 2 a proiectului

Task18:S-a realizat potrivirea partilor componente si s-au refacut legaturile si partile care dadeau erori de complire sau erori de algoritmi.Dupa ce acste legaturi au fost facute atunci butonele din meniu erau active , adica 'faceau ceva'.

Faza de acceptare (redactarea Raportului de test beta-Site)

Task19:Dupa ce s-a testat functionalitatea corecta a fiecarui buton din meniu si ceea ce a prevazut proiectul a fost realizat , atunci membrii proiectului au accepat ca aceasta sa fie faza finala a proiectului realizat in Visual C++ 6.0 si C++,.

Faza de redactare a documentatiei finale a proiectului

Task20:Documentatia proiectului a fost realizata urmarind pasii de dezvoltare a proiectului, fazele de dezvoltare si proiectare a proiectului.

Faza de predare a proiectului>

Task21:Predarea proiectului se va realiza in data de 28 mai 2004 , ora 8:00 , in cadrul orei de proiect la materia SDAA.Pe suport fizic va fi adus proictul pentru a putea fi rulat in Visual C++ pentru a vedea ce s-a realizat.Proiectul va fi insotit si de documentatie care prezinta caracteristicile proiectului, modul de abordare a proiectului, modul de implementare ,facilitatile de lucru si o vizualizare cat mai edificatorie a rezultatului.

2.2.2. Estimarea duratei taskurilor.

Taskurile prezentate mai sus au o durata de realizare in funcie de comlexiatrea lor.Avand in vedere ca am avut la dispozitie 14 saptamani durata aproximativa a fiecarui task este:

-pentru taskurile de la 2.2.1.1. -2sapt.

-pentru taskurile de la 2.2.1.2. -2sapt.

-pentru taskurile de la 2.2.1.3. -2sapt.

-pentru taskurile de la 2.2.1.4. -2sapt.

-pentru taskurile de la 2.2.1.5. -4sapt.

-pentru taskurile de la 2.2.1.6. -3sapt.

-pentru taskurile de la 2.2.1.7. -2sapt.

-pentru taskurile de la 2.2.1.8. -2sapt.

-pentru taskurile de la 2.2.1.9. -3sapt.

-pentru taskurile de la 2.2.1.10. -1sapt.

2.2.3.Estimarea resurselor necesare

Estimarea resurselor necesare:

-umane: cei patru membrii ai echipei indrumati de profesorul caruia trebuie prezentat proiectul la final;

-tehnica de calcul:C++ si Visual C++ 6.0;

-materiale necesare :documentarea necesara pentru a putea implementa cerintele proiectului.

2.3. Organizarea proiectului

2.3.1 Organizarea generala

In deezvoltarea proiectului s-au urmarit urmatoarele principii generale:

-realizarea unui program cat mai bine structurat;

-realizarea cerintelor proiectului;

-realizarea unei interfete cu utilizatorul ,cat mai usor de utilizat de catre utilizator;

-dialogul cu utilizatorul sa fie cat mai interactiv si sa lase la dispozitia utilizatorului crarea grafului intr-un mod cat mai simplu;

-vizualizarea grafului in forma grafica pe ecran;

-vizualizarea rezultatelor finale in forma grafica , acolo unde este posibil .

Responsabilitati

Atribuirea taskurilor membrilor echipei:

Task1:1+2+3+4;

Task2:1+2+3+4;

Task3:1+2+3+4;

Task4:1+3;

Task5:2+4;

Task6:1+2+3+4;

Task7:1+2+3+4;

Task8:1+2+3+4;

Task9:1;

Task10:1;

Task11:3;

Task12:4;

Task13:4;

Task14:4

Task15:2;

Task16:3;

Task17:1+2+3+4;

Task18:2;

Task19:1+2+3+4;

Task20:1+2+3;

Task21:1+2+3+4;

2.3.3.Diagrama generala de Dezvoltare a Proiectului

Dragan Adina

Dragomir Crina

Grozea Florin

Mocanu Petru

Specificatia de proiectare (Arhitectura aplicatiei)

3.1. Introducere

Limbajul de programare in care a fost realizat proiectul este :

-Visual C++ 6.0 pentru interfata cu utilizatorul si meiu;

-C++ pentru algoritmii necesari;

3.2. Descriere generala

Arhitectura software a proiectului este implementata cu ajutorul obiectelor, realizate in Visual C++ 6.0 .Ferestrei principale ii sunt subordonate toate obiectele.

3.3. Structuri de date

S-au folosit ca date de intrare o matrice care reprezinta matricea costurilor si care este preluata in urma creerii de catre utilizator a grafului.Structura folosita este urmatoarea:

typedef struct nod

3.4. Structura programului.

Descrierea arhitecturii software a programului,respectiv a structurii sale:

CAfisApp -clasa generala a programului

CAfisDlg -clasa asociata ferestrei principale

CDlgFLoyd    -clasa care contine algoritmul Floyd si fereastra coresp.

CEtic    -clasa care realizeaza afisarea numelor si distantelor nodurilor

CLegNouDLG-clasa asociata ferestrei care cere informatiile despre legaturi

CNodNouDLG-clasa asociata ferestrei care cere informatiile despre noduri

Nod    -structura grafului

NodPornire    -clasa care cere nodul de pornire pentru Dijkstra

Globals    -clasa care contine variabilele locale

Se realizeaza o descriere succinta de principiu a fiecarei componente in parte:

CafisDlg:

3.5. Proiectarea interfetei programului

Interfata este foarte simplu de utilizat continand urmatoarele butoane:

AdaugareN - prin care utilizatorul poate aduga noduri pentru a creea graful.Utilizatorul apasa acest buton dupa care ,cu mouse-ul apasa pe fereastra alturata, in locul in care vrea sa apara nodul.Printr-o casuta de dialog i se va cere Numele nodului ,iar daca apasa pe OK informatia este preluata daca utilizatorul nu doreste sa continue (sa nu adauge nodul) apasa pe CANCEL.

AdaugareL prin care utilizatorul poate aduga o latura intre doua noduri.Utilizatorul trebuie sa apese acest buton , dupa care cu mouse-ul doua noduri intre care doreste sa traseze latura.Dupa aceasta va aparea pe ecran o casuta de dialog unde i se cere utilizatorului sa selecteze directia legaturii (deoarece trebuie sa creeze un graf orientat) precum si distanta intre cele doua noduri.Ca ultim pas trebuie apasat pe butonul de OK daca utilizatorul vrea ca datele introduse sa se regaseasca in graf sau CANCEL daca nu.

Editeza reprezinta modificarea unui nod sau a unei laturi :cu mouse-ul se merge pa nodul/latura pe care dorim sa o stergem si de aici va aprea pe ecran una den cele doua casute de dialog descrise la cele doua butoane de mai sus , in functie editarea unui nod sau a unei laturi.Astfel nodul isi poate schimba numele , iar latura distanta si orientarea.

Stergere - se poate realiza stergera unui nod sau a unui laturi , care trebuie insemnat /insemnata cu mouse-ul dupa activarea acestui buton .

Dijkstra se apeleaza algoritmul lui Dijkstra pentru graful creat anterior, se va cere printr-o casuta de dialog nodul de pornire pentru algoritmul lui Dijkstra.Se va afisa pe ecran sub forma de graf drumul minim cu origine minima in nodul pentru care s-a aplicat alforitmul.

Floyd - se apleza algoritmul lui Floyd pentru graful creat anterior , se va afisa matricea care rezulta in urma aplicarii algoritmului lui Floyd.Intr-o fereastra de dialog se cere un nod de pornire si in alta un nod de oprire si se va afisa drumul creat intre aceste doua noduri.

Informatii - afiseaza o casuta cu numele autoriilor

Iesire - cand se apeleza se iese din program.

4.Specificatia de codificare.

Codul sursa al programului este atasat proiectului pe suport magnetic.

5. Planul de test

Testarea programului s-a realizat in mod sistematic prin verificarea la fiecare pas a eroeilor de sitaxa,care au fost corectate imediat de cel care a implementat modulul.Problemele care au aparut in mod sistematic au fost erorile de compilare precum si executia incorecta a algoritmilor.

Corectarea erorilor de compilare s-a facut consultand HELP-ul Visual C++ 6.0 si C++, iar cele date de functionarea incorecta algoritmilor au fost corectate prin studierea cu atentie a impelmentarii si corectarea ei acolo unde necesita

Testarea se realizeaza de catre fiecare dintre membrii echipei ,ei trebuind sa aduca la 'legare' un cod corect atat din punct de vedere sintactic cat si executabil corect.

6.Manual de utilizare

Utilizatorul trebuie sa aiba cunostinte minime despre grafuri , intrucat programul implementeaza algoritmii lui Dijkstra si Floyd.In cazul comunicarii cu programul , utilizatorul nu are nevoie de documentatie, interfata fiind fiabila.

7. Devizul proiectului

7.1 Numar de persoane implicate    

La realizarea acestui proiect au participat 4 persoane:

Dragan Adina Patricia    gr. 2.2

Dragomir Crina    gr. 2.2

Grozea Florin    gr. 2.3

Mocanu Petru Alexandru    gr. 3.2

7.2 Contributia personala (%)

Lista persoanelor si contributia in procente a fiecaruia la realizarea proiectului :

Dragan Adina Patricia    gr. 2.2 25%

Dragomir Crina    gr. 2.2 25%

Grozea Florin    gr. 2.3 25%

Mocanu Petru Alexandru    gr. 3.2 25%

7.3 Ore consumate fizic:

8. Concluzii

La realizare proiectului au contribuit in prima faza cunostintele noaste de pana in

momentul in care am inceput realizarea proiectului si modul in care am cautat noi informatii despre modul de realizare si implementare a proiectului.

Un factor foarte important a fost eficienta cu care am reusit( sau nu in unele taskuri)

sa ne impartim proiectul pe faze si task-uri si sa le urmam.

Un alt obstacol a fost modul in care a inteles fiecare ce are de facut, pentru ca pe parcurs a trebiut sa legam task-uri facute de diferiti oameni si ele trebuiau sa se potriveasca , iar daca nu s-au potrivit au trebuit transformate.De asemenea a trebuit sa tinem seama de ideiile fiecaruia si a trebuit sa renuntam la unele.

Elemente de care se poate tine cont la realizarea unor alte proiecte ar fi multe , de fapt intregul proiect este un model de lucru in echipa si ceea ce s-a reusit realiza urmand pasii descrisi mai sus(pasi ce trebiue urmati pentru dezvoltarea unui proiect).