| CATEGORII DOCUMENTE |
DOCUMENTE SIMILARE |
|
TERMENI importanti pentru acest document |
|
| : | |
APLICATIA GraphSearch
Aplicatia GraphSearch este un program realizat cu scop demonstrativ si comparativ pentru metodele de traversare si se incadreaza in categoria software-urilor 'simple' (dupa E. Yourdon). Cu GraphSearch se pot construi repede si simplu grafuri neorientate, in cele doua moduri de implementare prezentate, grafuri care pot fi supuse operatiilor de traversare.
GraphSearch este proiectat sa ruleze sub sistemul de operare MS-DOS, necesitand resurse minime pentru instalare si utilizare: un calculator 80286 sau superior si 200KB spatiu liber pe disc. Ca echipamente periferice sunt necesare un monitor cel putin VGA cu rezolutie 640/480 pixeli cu minim 16 culori si eventual un mouse.
Cu o interfata prietenoasa, bazata pe ferestre si butoane, acest program este usor de folosit datorita dialogului permanent cu utilizatorul (utilizatorii de mouse pot constata ca se poate lucra exclusiv cu acest periferic).
Dupa ce lansati in executie softul apare un generic de care puteti trece fie apasand o tasta, fie apasand butonul drept al mouse-ului. In cazul in care nu este detectat un mouse atasat la calculator, se va semnala acest lucru intr-o caseta de dialog.
Fereastra principala a aplicatiei contine o bara de cinci butoane, dintre care, pentru inceput, se pot folosi doar doua.
Prin selectarea butonului File apare o noua bara de butoane specifice lucrului cu fisiere. Daca se doreste construirea unui graf nou trebuie apasat New, daca se doreste incarcarea unui graf salvat anterior pe disc se va apasa Load. Butoanele Save si SaveAs sunt utilizabile doar cand exista un graf curent, acestea permitand salvarea lui pe disc cu numele cu care a mai fost salvat sau sub care s-a incarcat, respectiv cu un nume nou. Daca se doreste parasirea aplicatiei se poate utiliza butonul Exit (operatie mai indicata decat inchiderea aplicatiei direct cu butonul din bara de titlu, care determina o iesire fara confirmare prealabila).
Dupa ce exista un graf curent (afisat pe ecran), el poate fi modificat prin apasarea butonului Edit.
Cu ajutorul butonului Options se pot indica modul de implementare a grafului, tehnica de traversare care va fi folosita, precum si viteza de traversare, iar cu cel mai mare buton: StartSearch se lanseaza procesul de traversare.
Butonul Messages activeaza o fereastra de mesaje in partea inferioara a ferestrei principale in care apar scurte indicatii si recomandari utile in lucrul cu GraphSearch.
Daca se lucreaza cu mouse-ul totul este cat se poate de usor, dar daca se lucreaza numai cu tastatura, sunt utile urmatoarele specificatii:
un buton cu o litera a textului subliniata reactioneaza la apasarea tastei corespunzatoare;
butoanele OK si Cancel reactioneaza la tastele <CR>, respectiv <Esc>;
butoanele pe care apar sageti reactioneaza la apasarea respectivelor taste; directionale (mai putin cele din fereastra Help care au ca si corespondente tastele <PgUp> si <PgDown>;
butonul de help de pe bara de titlu reactioneaza la apasarea tastei functionale <F1>;
butoanele de inchidere a unei ferestre reactioneaza la tastarea combinatiei <Alt>+<F4>;
butoanele 'radio' din fereastra de optiuni se selecteaza cu <Spatiu> dupa ce in prealabil v-ati pozitionat pe ele mutand cu tastele directionale simbolul '?'.
Selectarea optiunilor:
In fereastra de optiuni se poate specifica tehnica de implementare pentru un graf ce va fi construit. Acest lucru se poate face pana in momentul stabilirii numarului de noduri apasand butonul corespunzator. Metoda de traversare se stabileste inaintea fiecarei traversari. Prin reglarea vitezei de traversare se stabileste timpul de asteptare dintre etapele si subetapele procesului de parcurgere a grafului.
Cum se construieste un graf nou?
Dupa selectarea lui New apare pe ecran o fereastra in care veti putea construi graful. Primul lucru ce trebuie facut este specificarea modului de implementare a grafului. Atentie, dupa inceperea procesului de construire a grafului, nu mai este posibila schimbarea tehnicii de implementare.
Pentru inceput trebuie specificat numarul de noduri ce vor compune graful. Se pot folosi butoanele de incrementare / decrementare din coltul dreapta-jos al ferestrei pentru a se ajunge la numarul dorit sau se poate introduce direct de la tastatura acest numar, daca el este cel mult 9. Din ratiuni de vizualizare numarul de maxim noduri este fixat la 15. Validati numarul cu butonul OK.
Nodurile grafului apar sub forma unor butoane dispuse circular. Pentru specificarea unui arc pe care doriti sa-l inserati in graf, trebuie selectate butoanele corespunzatoare nodurilor care definesc arcul. Daca selectati nodurile care definesc un arc care este deja inserat in graf, se considera ca doriti sa stergeti acel arc din graf.
Incarcarea unui graf de pe disc:
Dupa selectarea butonului Load apare o lista a tuturor fisierelor posibil a avea in ele informatii despre grafuri (cu extensia .GRA). Actionati butoanele de deplasare pana cand fisierul dorit ajunge in caseta alba de editare de sus, apoi validati cu OK. Se poate insa introduce direct numele fisierului dorit, dupa ce ati punctat cu mouse-ul undeva in interiorul casetei de editare si a aparut un cursor de forma '_'. Stergeti si rescrieti sau modificati numele aflat aici, apoi validati.
Salvarea unui graf pe disc:
Salvarea unui graf cu un nume nou se face in fereastra 'SaveAs', specificand numele grafului, dupa procedura descrisa la operatia de incarcare. Daca se salveaza un graf cu un nume stabilit atunci se selecteaza Save.
Modificarea unui graf:
Facilitatea modificarii unui graf consta in posibilitatea inserarii de noi arce, sau stergerea unor arce din graf. Aceste operatii se fac asa cum au fost descrise la sectiunea de construire a unui graf.
Traversarea:
Inainte de a incepe traversarea unui graf trebuie aleasa o metoda de traversare. Se poate alege fie tehnica de traversare prin cuprindere, fie tehnica de traversare in adancime, sau se poate opta pentru a traversare 'paralela' a grafului cu ambele metode.
Pe parcursul procesului de traversare pot aparea diferite reprezentari ale nodurilor si arcelor grafului. Astfel, nodurile vizitate sunt reprezentate prin discuri, avand inscriptionate etichetele, pe cand nodurile nevizitate nu sunt marcate cu etichete. Nodurile care sunt inserate intr-o structura de date auxiliara vor fi incadrate cu un cerc. Arcele obisnuite ale grafului sunt marcate cu linie continua subtire, iar cele care sunt gasite ca arce de arbore, vor fi marcate cu linie continua groasa. Cu linie intrerupta sunt marcate arcele curente, adica arcele de-a lungul carora se continua cautarea la un moment dat.
Pentru ca fiecare operatie sa fie bine observata, intre doua operatii succesive exista un anumit timp de asteptare ce poate fi reglat din fereastra 'Optiuni', caseta 'viteza de traversare', o viteza marita insemnand timp de asteptare redus.
Corespunzator fiecarei metode de traversare aleasa, in partea de jos a ferestrei principale, se poate urmari evolutia structurii de date auxiliare utilizata.
3 Implementarea aplicatiei
Aplicatia GraphSearch a fost redactata in limbajul C
In abordarea iterativa a celor doua tehnici de traversare prezentate erau folosite, pentru a retine fie frontiera locurilor deja vizitate, fie drumul parcurs pana la un moment dat, structuri de date auxiliare: coada pentru cautarea prin cuprindere si stiva pentru cautarea in adancime.
Aplicatia GraphSearch utilizeaza o implementare dinamica a celor doua structuri de date. Informatia ce se memoreaza este indicele nodului pentru care s-a inceput vizitarea. Structura nodurilor listei (stivei sau cozii) este urmatoarea:
typedef struct LNode *pointer;
typedef struct LNode
ListNode;
Deoarece in cazul stivei este suficient sa retinem pozitia varfului stivei (ce va fi o referinta) se va declara:
typedef struct LNode *Stack;
iar in cazul cozii:
typedef struct Queues
Queue;
Asupra acestor structuri, algoritmii de traversare efectueaza urmatoarele operatii:
Push - functia care 'insereaza' un nou element in stiva:
void Push(int x,Stack *StackPoint)
/* Push */
InQueue - functia care adauga un nou element in coada :
int Pop(Stack *StackPoint)
return pop_temp;
} /* Pop */
Pop - functia care extrage elementul din varful stivei:
void InQueue(int x,Queue *Q)
/* InQueue */
OutQueue - functie care extrage un element din coada :
int OutQueue(Queue *Q)
return 0;
} /* OutQueue */
De asemenea se mai utilizeaza teste de validitate: functiile StackEmpty si QueueEmpty.
Functia StackEmpty :
int StackEmpty(Stack StackPoint)
/* StackEmpty */
Functia QueneEmpty:
int QueueEmpty(Queue Q)
/* QueueEmpty */
3.2 Implementarea grafurilor in cadrul aplicatiei
Este cunoscut faptul ca exista doua modalitati de reprezentare a unui graf in limbajele de programare: reprezentare prin structuri statice si prin structuri dinamice.
Structura statica prin care se implementeaza un graf este matricea sa de adiacente. Graful este declarat ca o structura de date de tipul :
typedef int Matrix[15][15];
typedef struct GraphT1
GraphType1;
Aceasta solutie este avantajoasa atata timp cat numarul maxim de noduri admise in graf (in cazul GraphSearch este 15) nu este cu mult mai mare de cat numarul efectiv de noduri, iar numarul de muchii este suficient de mare. In caz contrar este recomandata o implementare prin structuri dinamice de date. GraphSearch lasa la latitudinea celui care construieste graful sa-si aleaga tehnica de reprezentare dorita.
Structura dinamica ce implementeaza un graf este o structura multi-inlantuita in felul urmator:
Nodurile grafului sunt reprezentate de o lista (statica): NList. Fiecare nod al listei este de tipul:
typedef struct
nod;
Acest din urma camp pointeaza spre o lista de vecini ai nodului index. Vecinii unui nod sunt reprezentati printr-o lista cu noduri de tipul PointE definita astfel:
typedef struct Sedge *PointE;
typedef struct Sedge
edge;
Campul extrem reprezinta a doua extremitate a muchiei (prima fiind index).
Asadar, graful implementat ca o structura dinamica de date va fi de tipul:
typedef struct GraphT2
GraphType2;
In procesul de constructie si traversare asupra grafurilor se efectueaza o serie de operatii si teste:
InitMyGraph - functie ce initializeaza graful:
void InitMyGraph(int n)
/* InitMyGraph */
AddOrDeleteEdge - functie de adaugare sau stergere muchii din graf:
void AddOrDeleteEdge(int k,int j)
/* AddOrDeleteEdge */
IfAdiac - functie ce testeaza daca doua noduri sunt adiacente sau nu :
int IfAdiac(int i,int j)
/* IfAdiac */
Aceste functii sunt apelate fara a tine seama de implementarea grafului. Fiecare astfel de functie contine un test asupra tehnicii de implementare a grafului, apeland, dupa caz, una din functiile specifice implementarii.
De cele mai multe ori, implementarea prin matrice de adiacente a unui graf, are dezavantajul ocuparii efective a unui spatiu de memorie mai mic decat cel alocat, insa prezinta marele avantaj al simplitatii operatiilor asupra grafului.
Functia InitMyGraph1 in acest caz fixeaza campul G.NodeNo pe numarul transmis caparametru si construieste o matrice de adiacente cu toate elementele nule :
void InitMyGraph1(int n,GraphType1 *G)
} /* InitMyGraph1 */
Functia AddOrDeleteEdge1 testeaza doar daca pe pozitia din matricea de adiacente corespunzatoare indicilor transmisi ca parametru este 1 sau 0, complementand aceasta valoare :
void AddOrDeleteEdge1(int source,int dest,GraphType1 *G)
else
} /* AddOrDeleteEdge1 */
Functia IfAdiac1 returneaza TRUE daca pe pozitia corespunzatoare indicilor transmisi ca parametru se afla 1 in matricea de adiacente :
int IfAdiac1(int Node1,int Node2,GraphType1 G)
/* IfAdiac1 */
Un graf reprezentat prin structuri de adiacente are avantajul de a consuma exact atata memorie cata are nevoie, insa structurile dinamice utilizate complica operatiile curente asupra grafului.
Functia InitMyGraph2 fixeaza numarul de noduri al grafului si initializeaza extremitatile primelor muchii cu NULL :
void InitMyGraph2(int n,GraphType2 *G)
} /* InitMyGraph2 */
Functia AddOrDeleteEdge2 testeaza daca nodurile specificate in argumentele sale sunt adiacente sau nu. In caz afirmativ se cauta in lista muchiilor ce pornesc dintr-unul din noduri o referinta la cel de-al doilea nod specificat si se elimina acest element din lista. In caz contrar se insereaza la sfarsitul listei muchiilor corespunzatoare unui nod o referinta spre a doua extremitate a noii muchii.
Deoarece graful este neorientat, deci toate notiunile legate de adiacenta in graf sunt simetrice, aceste operatii se efectueaza pentru ambele noduri transmise ca parametrii procedurii.
Functia AddOrDeleteEdge2 are urmatoarea structura
void AddOrDeleteEdge2(int source,int dest,GraphType2 *G)
else
q->next=p1->next;
free(p1);
}
}
else
p1=((*G).NList[dest]).first;
q=p1;
if(IfAdiac2(dest,source,*G)==1)
else
q->next=p1->next;
free(p1);
}
}
else
} /* AddOrDeleteEdge2 */
Functia IfAdiac2 parcurge lista muchiilor cu o extremitate in nodul specificat in argument cautand o referinta spre cel de-al doilea nod. Daca nu a fost gasita se returneaza FALSE.
Functia IfAdiac2 este urmatoarea:
int IfAdiac2(int Node1,int Node2,GraphType2 G)
p=p->next;
}
return Exist;
} /* IfAdiac2 */
Indicativele 1, 2 din numele functiilor si procedurilor au fost necesare strict din considerente de constrangere a limbajului de programare utilizat.
Vizualizarea grafurilor se face prin asezarea nodurilor sale in colturile unui poligon regulat (ce are atatea varfuri cate noduri are graful). Coordonatele fiecarui nod sunt calculate cu o formula de rotatie a unui punct initial ales pe cercul imaginar circumscris poligonului regulat, relativ la centrul acestui cerc (x0,y0):
xR=x0+(x-x0)*cos(unghi)-(y-y0)*sin(unghi);
yR=y0+(x-x0)*sin(unghi)+(y-y0)*cos(unghi);
In acest scop nodurile grafului sunt retinute intr-o lista speciala, unde pe langa indicele nodului se mai afla coordonatele nodului, calculate cu formulele anterioare. De asemenea in procesul de traversare nodurile trebuie insotite de un marcaj, asadar lista va fi de tipul:
typedef Node NodeList[MaxNode]
unde:
typedef struct SNod
;
iar MaxNode este constanta ce desemneaza numarul maxim de noduri (15).
Este nevoie de doua marcaje pentru un nod din ratiuni de implementare a traversarii in paralel a grafului, prin cele doua metode.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1243
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
