Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- int mat_adiacenta[20][20] = { 0 }, mat_incidenta[20][20] = { 0 }, n = 0, m = 0, la_e1[20], la_e2[20], pozitie, lista_pozitie[20], lista_succesori[20], lista_predecesori[20];
- int succ, pred,i,j;
- void citire_ma() {
- ifstream fin("mat_adiacenta.in.txt");
- fin >> n;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- fin >> mat_adiacenta[i][j];
- fin.close();
- }//functie pentru citirea matricei de adiacenta
- void citire_mi() {
- ifstream fin("mat_incidenta.in.txt");
- fin >> n>>m;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- fin >> mat_incidenta[i][j];
- fin.close();
- }//functie pentru citirea matricei de incidenta
- void citire_la() {
- int i;
- ifstream fin("lista_arce.in.txt");
- fin >> n >> m;
- for (i = 1; i <= m; i++) {
- fin >> la_e1[i];
- }
- for (i = 1; i <= m; i++) {
- fin >> la_e2[i];
- }
- }//functie pentru citirea listei de arce
- void citire_ls() {
- int i;
- ifstream fin("lista_succesori.in.txt");
- fin >> n >> m;
- for (i = 1; i <= n + 1; i++)
- fin >> lista_pozitie[i];
- for (i = 1; i <= m; i++)
- fin >> lista_succesori[i];
- }//functie pentru citirea listei de succesori
- void citire_lp() {
- int i;
- ifstream fin("lista_predecesori.in.txt");
- fin >> n >> m;
- for (i = 1; i <= n + 1; i++)
- fin >> lista_pozitie[i];
- for (i = 1; i <= m; i++)
- fin >> lista_predecesori[i];
- }//functie pentru citirea listei de predecesori
- void afisare_matrice(int matrice[20][20], int n, int m) {
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- cout << matrice[i][j] << " ";
- cout << endl;
- }
- cout << "\n";
- }//functie pentru afisarea oricarei matrice
- void afisare_vector(int vector[20], int m) {
- for (int i = 1; i <= m; i++) {
- cout << vector[i] << " ";
- }
- cout << "\n";
- }//functie pentru afisarea oricarui vector
- void mat_adiacenta_toall() {
- for (int i = 1; i <= n; i++)//parcurgem matricea de adiacenta
- for (int j = 1; j <= n; j++)
- {
- if (mat_adiacenta[i][j] == 1) {//cand gasim legatura dintre doua noduri
- m++;//trecem la o coloana noua care reprezinta un arc nou
- mat_incidenta[i][m] = 1;//introducem pe pozitia coloana si indicele i care reprezinta partea superioara a arcului pe 1
- mat_incidenta[j][m] = -1;//introducem pe pozitia coloana si indicele j care reprezinta partea inferioara a arcului pe 1
- }
- }
- afisare_matrice(mat_incidenta, n, m);//afisam matricea de incidenta
- cout << endl;
- m = 0;
- for (int i = 1; i <= n; i++)//parcurgem matricea de adiacenta
- for (int j = 1; j <= n; j++)
- {
- if (mat_adiacenta[i][j] == 1) {//cand gasim legatura dintre doua noduri ce este reprezentata prin cifra 1
- m++;//crestem indicele de parcurgere a listelor
- la_e1[m] = i;//introucem in lista de noduri superioare pe i ce reprezinta nodul superior al arcului
- la_e2[m] = j;//introducem in lista de noduri inferioare pe j ce reprezinta nodul inferior al arcului
- }
- }
- afisare_vector(la_e1, m); //afisam cei doi vectori, care impreuna reprezinta lista de arce
- afisare_vector(la_e2, m); cout << endl; cout << endl; cout << endl;
- m = 1;
- lista_pozitie[m] = 1;// pe prima pozitie a listei de pozitii punem 1 deoarece in lista de succesori o sa incepem sa punem de pe prima pozitie
- pozitie = 0;//acesta reprezinta indicele de parcurgere a listei de succesori
- for (int i = 1; i <= n; i++)//parcurgem matricea de adiacenta
- {
- for (int j = 1; j <= n; j++)
- {
- if (mat_adiacenta[i][j] == 1) {//cand gasim legatura dintre doua noduri ce este reprezentata prin cifra 1
- pozitie++;//crestem pozitia pe care o sa adaugam noul nod ce reprezinta un nod succesor al altui nod
- lista_succesori[pozitie] = j;//adaugam nodul respectiv
- }
- }
- m++;
- lista_pozitie[m] = pozitie + 1;//adaugam in lista de pozitii, pozitia de unde urmatorul nod va urma sa-si puna nodurile succesoare
- }
- afisare_vector(lista_pozitie, m); //afisam lista de succesori
- afisare_vector(lista_succesori, pozitie); cout << endl; cout << endl; cout << endl;
- m = 1;
- lista_pozitie[m] = 1;// pe prima pozitie a listei de pozitii punem 1 deoarece in lista de predecesori o sa incepem sa punem de pe prima pozitie
- pozitie = 0;//acesta reprezinta indicele de parcurgere a listei de predecesori
- for (int j = 1; j <= n; j++)//parcurgem matricea de adiacenta
- {
- for (int i = 1; i <= n; i++)
- {
- if (mat_adiacenta[i][j] == 1) {//cand gasim legatura dintre doua noduri ce este reprezentata prin cifra 1
- pozitie++;//crestem pozitia pe care o sa adaugam noul nod ce reprezinta un nod predecesor al altui nod
- lista_predecesori[pozitie] = i;//adaugam nodul respectiv
- }
- }
- m++;
- lista_pozitie[m] = pozitie + 1;//adaugam in lista de pozitii, pozitia de unde urmatorul nod va urma sa-si puna nodurile predecesoare
- }
- afisare_vector(lista_pozitie, m);//afisam lista de predecesori
- afisare_vector(lista_predecesori, pozitie); cout << endl; cout << endl; cout << endl;
- }
- void mat_incidenta_toall() {
- for (j = 1; j <= m; j++) {//parcurgem matricea de incidenta
- for (i = 1; i <= n; i++) {
- if (mat_incidenta[i][j] == 1)//cand gasim cifra 1, ce reprezinta un nod superior
- succ = i;//il atribuim variabilei succ
- if (mat_incidenta[i][j] == -1)//cand gasim cifra -1, ce reprezinta un nod inferior
- pred = i;//il atribuim variabilei pred
- }
- mat_adiacenta[succ][pred] = 1;//la final, in matricea de adiacenta pe pozitia [succ][pred] inseram cifra 1, ce reprezinta arcul (succ, pred)
- }
- afisare_matrice(mat_adiacenta, n, n); cout << endl; cout << endl; cout << endl;
- pozitie = 0;
- for (j = 1; j <= m; j++) {//parcurgem matricea de incidenta
- pozitie++;
- for (i = 1; i <= n; i++) {
- if (mat_incidenta[i][j] == 1)//daca in matricea de incidenta gasim cifra 1, reprezinta faptul ca am gasit un nod superior
- la_e1[pozitie] = i;//pe care in adaugam in lista de noduri superioare(noduri predecesoare)
- if (mat_incidenta[i][j] == -1)//daca in matricea de incidenta gasim cifra -1, reprezinta faptul ca am gasit un nod inferior
- la_e2[pozitie] = i;//pe care il adauam in lista de noduri inferioare(noduri succesoare)
- }
- }
- afisare_vector(la_e1, pozitie);//afisam lista de arce reprezentata prin cei doi vectori
- afisare_vector(la_e2, pozitie); cout << endl; cout << endl; cout << endl;
- int k=1;
- pozitie = 0;
- lista_pozitie[k] = 1;//in lista de pozitii adaugam pe 1 deoarece in lista de succesori pe prima pozitie o sa adaugam succesori primului nod
- for (j = 1; j <= m; j++) {//parcurgem matricea de incidenta
- for (i = 1; i <= n; i++) {
- if (mat_incidenta[i][j] == -1) {//daca gasim cifra -1 reprezinta faptul ca am gasit un nod ce reprezinta partea inferioara a unui arc(adica nod succesor)
- pozitie++;//crestem pozitia
- lista_succesori[pozitie] = i;//adaugam nodul in lista de succesori
- }
- }
- k++;//crestem indicele de parcurgere a listei de pozitii
- lista_pozitie[k] = pozitie + 2;//adaugam pozitia de unde vom incepe sa adaugam noii succesori ai urmatorului nod
- }
- afisare_vector(lista_pozitie, k-1);//afisam lista de succesori, reprezentate prin cei doi vectori
- afisare_vector(lista_succesori, pozitie); cout << endl; cout << endl; cout << endl;
- k = 1;
- pozitie = 0;
- lista_pozitie[k] = 1;//in lista de pozitii adaugam pe 1 deoarece in lista de predecesori pe prima pozitie o sa adaugam succesori primului nod
- int indice;
- for (i = 1; i <= m; i++) {//parcurgem matricea de incidenta
- for (j = 1; j <= m; j++) {
- if (mat_incidenta[i][j] == -1) {//daca gasim cifra -1 ce reprezinta succesorul unui nod, va trebui sa cautam predecesorii sai pe aceiasi linie
- for (indice = 1; indice <= n; indice++)//cautam predecesorii pe aceiasi coloana pe care l-am gasit pe el
- {
- if (mat_incidenta[indice][j] == 1)//cand gasim un predecesor al nodului "j"
- {
- pozitie++;//crestem pozitia
- lista_predecesori[pozitie] = indice;//il adaugam in lista de predecesori
- }
- }
- }
- }
- k++;
- lista_pozitie[k] = pozitie + 1;//adaugam pozitia in lista de pozitii
- }
- k -= 2;
- afisare_vector(lista_pozitie, k);//afisam lista de predecesori
- afisare_vector(lista_predecesori, pozitie); cout << endl; cout << endl; cout << endl;
- }
- void lista_arce_toall() {
- int i, j;
- for (i = 1; i <= m; i++) {//parcurgem lista de arce
- mat_adiacenta[la_e1[i]][la_e2[i]] = 1;//pe pozitia [la_e1][la_e2] o sa adaugam 1 in matricea de adiacenta, deoarece in mat de adiacenta indicii de parcurgere sunt nodurile grafului
- }
- afisare_matrice(mat_adiacenta, n, n); cout << endl; cout << endl; cout << endl;//afisam matricea de adiacenta
- j = 0;
- for (i = 1; i <= m; i++) {//parcurgem lista de arce
- j++;
- mat_incidenta[la_e1[j]][i] = 1;//pe pozitia [la_e1][i] o sa adaugam 1 deoarece la_e1[i] reprezinta nodul superior(nodul predecesor) al arcului
- mat_incidenta[la_e2[j]][i] = -1;//pe pozitia [la_e2][i] o sa adaugam -1 deoarece la_e2[i] reprezinta nodul inferior(nodul succesor) al arcului
- }
- afisare_matrice(mat_incidenta, n, m); cout << endl; cout << endl; cout << endl;//afisam matricea de incidenta
- pozitie = 0;
- int k = 1;
- lista_pozitie[k] = 1;
- int arc = 1;
- for (i = 1; i <= m; i++) {//parcurgem lista de arce
- if (arc == la_e1[i]) {//daca gasim nodul in lista de noduri superioare
- pozitie++;//crestem pozitia
- lista_succesori[pozitie] = la_e2[i];//adaugam in lista de succesori pe corespondentul nodului superior, care este la_e2[i] adica succesorul sau
- }
- else {//daca nu-l gasim
- arc++;//trecem la urmatorul arc
- k++;//crestem indicele de parcurgere a listi de pozitie
- lista_pozitie[k] = pozitie + 1;//adaugam noua pozitie, de unde vom pune succesoruii urmatorului nod
- i--;
- }
- }
- k++;
- lista_pozitie[k] = pozitie + 1;
- afisare_vector(lista_pozitie, k);//afisam lista de succesori
- afisare_vector(lista_succesori, pozitie); cout << endl; cout << endl; cout << endl;
- arc = 1;
- pozitie = 0;
- k = 1;
- lista_pozitie[k] = 1;
- while (arc != m) {//parcurgem lista de arce
- for (i = 1; i <= m; i++) {
- if (arc == la_e2[i]) {//daca gasim nodul in lista de noduri inferioare
- pozitie++;//crestem pozitia
- lista_predecesori[pozitie] = la_e1[i];//adaugam in lista de predecesori pe corespondentul nodului inferior, care este la_e1[i] adica predecesorul sau
- }
- }
- arc++;//daca nu-l gasim
- k++;//crestem indicele de parcurgere a listi de pozitie
- lista_pozitie[k] = pozitie + 1;//adaugam noua pozitie, de unde vom pune predecesorii urmatorului nod
- }
- k--;
- afisare_vector(lista_pozitie, k);//afisam lista de predecesori
- afisare_vector(lista_predecesori, pozitie); cout << endl; cout << endl; cout << endl;
- }
- void lista_succesor_toall() {
- int i, j, nod, coloana;
- nod = i = 1;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//parcurgem lista de pozitie, in care intre 2 poziti se afla un nod, iar lista_succesori[j] reprezinta succesorul acestuia
- mat_adiacenta[nod][lista_succesori[j]] = 1;//introducem in matricea de adiacenta 1 pe pozitia [nod][lista_succesori[j]], unde lista_succesori[j] reprezinta succesorul nodului "nod"
- }
- nod++;// dupa ce terminam, trecem la urmatorul nod, pentru ai identifica succesorii
- i++;
- }
- afisare_matrice(mat_adiacenta, n, n);//afisam matricea
- i = nod = coloana = 1;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//parcurgem lista de pozitie, in care intre 2 poziti se afla un nod, iar lista_succesori[j] reprezinta succesorul acestuia
- mat_incidenta[nod][coloana] = 1;// introducem in matricea de incidenta 1 pe pozitia [nod][coloana] ce reprezinta capatul superior al arcului
- mat_incidenta[lista_succesori[j]][coloana] = -1;// introducem in matricea de incidenta -1 pe pozitia [lista_succesori[j]][coloana] ce reprezinta capatul inferior al arcului
- coloana++;//trecem la urmatoarea coloana(arc)
- }
- nod++;//trecem la urmatorul nod
- i++;
- }
- afisare_matrice(mat_incidenta, n, m);
- nod = i = 1;
- int k = 0;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {
- k++;
- la_e1[k] = nod;//in lista de noduri superioare introducem pe "nod"
- la_e2[k] = lista_succesori[j];//iar in lista de noduri inferioare il introducem pe nodul aferent nodului superior pentru a forma un arc.
- }
- nod++;
- i++;
- }
- afisare_vector(la_e1, k);
- afisare_vector(la_e2, k);
- cout << "\n";
- int lsPoz_pred[21] = { 0 }, predecesor, indice = 0;//initializari
- pozitie = 1;
- k = 1;
- lsPoz_pred[k] = pozitie;//adaugam pe 1 pe in lista de pozitii deoarece de acolo vom incepe sa punem predecesorii primului nod(daca exista)
- for (nod = 1; nod <= n; nod++) {//luam fiecare nod in parte
- i = 1;
- predecesor = 1;//ficare 2 intervale din lista_pozitii ii corespunde unui nod predecesor nodului din lista_succesori
- while (i < n + 1) {//parcurgem acele intervale
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//luam doua intervale unde se gaseste predecesorul
- if (nod == lista_succesori[j]) {//daca gasim un nod care exista in lista_succesori
- indice++;//crestem indicele de parcurgere a liste_predecesori
- lista_predecesori[indice] = predecesor; //il adaugam pe predecesor in lista
- pozitie++;//crestem pozitia
- }
- }
- i++;//trecem la urmatorul interval
- predecesor++;//trecem la urmatorul predecesor pe care il cautam
- }
- k++;//crestem indicele de parcurgere a ls_Poz_Pred
- lsPoz_pred[k] = pozitie;//adaugam pozitia de unde vom adauga nodurile predecesoare urmatorului nod succesor
- }
- afisare_vector(lsPoz_pred, k);//afisam lista de predecesori
- afisare_vector(lista_predecesori, indice);
- }
- void lista_predecesori_toall() {
- int i, j, nod, coloana;
- nod = i = 1;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//parcurgem lista de pozitie, in care intre 2 poziti se afla un nod, iar lista_predecesori[j] reprezinta predecesorul acestuia
- mat_adiacenta[lista_predecesori[j]][nod] = 1;//introducem in matricea de adiacenta 1 pe pozitia [nod][lista_predecesori[j]], unde lista_predecesori[j] reprezinta predecesorul nodului "nod"
- }
- nod++;//trecem la urmatorul nod
- i++;//trecem la urmatorul interval
- }
- afisare_matrice(mat_adiacenta, n, n);//afisam matricea de adiacenta
- i = nod = coloana = 1;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//parcurgem lista de pozitie, in care intre 2 poziti se afla un nod, iar lista_predecesori[j] reprezinta predecesorii acestuia
- mat_incidenta[nod][coloana] = -1;// introducem in matricea de incidenta -1 pe pozitia [nod][coloana] ce reprezinta capatul inferior al arcului
- mat_incidenta[lista_predecesori[j]][coloana] = 1;// introducem in matricea de incidenta 1 pe pozitia [lista_predecesori[j]][coloana] ce reprezinta capatul superior al arcului
- coloana++;//trecem la urmatoarea coloana
- }
- nod++;//trecem la urmatorul nod
- i++;//trecem la urmatorul interval
- }
- afisare_matrice(mat_incidenta, n, m);
- nod = i = 1;
- int k = 0;
- while (i < n + 1) {
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {
- k++;
- la_e1[k] = lista_predecesori[j];//in lista de noduri superioare introducem pe "lista_predecesori[j]"
- la_e2[k] = nod;//iar in lista de noduri inferioare il introducem pe nodul aferent nodului superior pentru a forma un arc.
- }
- nod++;//trecem la urmatorul nod
- i++;//trecem la urmatorul interval
- }
- afisare_vector(la_e1, k);
- afisare_vector(la_e2, k);
- cout << "\n";
- int lsPoz_succ[21] = { 0 }, succesor, indice = 0;//initializari
- pozitie = 1;
- k = 1;
- lsPoz_succ[k] = pozitie;//adaugam pe 1 pe in lista de pozitii deoarece de acolo vom incepe sa punem predecesorii primului nod(daca exista)
- for (nod = 1; nod <= n; nod++) {//luam fiecare nod in parte
- i = 1;
- succesor = 1;//ficare 2 intervale din lista_pozitii ii corespunde unui nod succesor nodului din lista_predecesori
- while (i < n + 1) {//parcurgem acele intervale
- for (j = lista_pozitie[i]; j < lista_pozitie[i + 1]; j++) {//luam doua intervale unde se gaseste succesorul
- if (nod == lista_predecesori[j]) {//daca gasim un nod care exista in lista_predecesori
- indice++;//crestem indicele de parcurgere a liste_succesori
- lista_succesori[indice] = succesor;//il adaugam pe predecesor in lista
- pozitie++;//crestem pozitia
- }
- }
- i++;//trecem la urmatorul interval
- succesor++;//trecem la urmatoul succesor pe care il cautam
- }
- k++;//crestem indicelui de parcurgere a lsPoz_Succ
- lsPoz_succ[k] = pozitie;//adaugam pozitia de unde vom adauga nodurile succesori urmatorului nod predecesor
- }
- afisare_vector(lsPoz_succ, k);//afisam lista de succesori
- afisare_vector(lista_succesori, indice);
- }
- int menu() {
- int opt;
- cout << "\nAlegeti una dintre optiunile(1-5)";
- cout << "\n1. Matricea de adiacenta la celelalte reprezentari;";
- cout << "\n2. Matricea de incidenta la celelalte reprezentari;";
- cout << "\n3. Lista arcelor la celelalte reprezentari;";
- cout << "\n4. Lista succesorilor la celelalte reprezentari;";
- cout << "\n5. Lista predecesorilor la celelalte reprezentari;";
- cout << "\n6. Iesire din meniu.";
- cout << "\nOptiunea dumneavoastra este: "; cin >> opt;
- return opt;
- }//functie de afisare a meniului
- int main()
- {
- int optiune;
- optiune = menu();
- switch (optiune)
- {
- case 1:
- citire_ma();
- mat_adiacenta_toall();
- break;
- case 2:
- citire_mi();
- mat_incidenta_toall();
- break;
- case 3:
- citire_la();
- lista_arce_toall();
- break;
- case 4:
- citire_ls();
- lista_succesor_toall();
- break;
- case 5:
- citire_lp();
- lista_predecesori_toall();
- break;
- case 6:
- exit(0);
- default:
- break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement