Tema 2: The Network

• Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
• Aplicarea algoritmilor studiați pe topologie graf într-un exemplu practic
• Înțelegerea unor anumite concepte din reţelistică.

1. Deadline hard, 06 mai ora 23:59 (termen limită - nu se obţin puncte pe soluţiile trimise mai târziu)
2. Trimiterea temelor se face pe platforma vmchecker (folosiți numele de utilizator şi parola de pe http://acs.curs.pub.ro).
3. Checker-ul offline poate fi descărcat de la această adresă
4. Puteţi cere ajutor oricând la această adresă email

1. 30/04/2018 19:40
   • corectură enunţ - cerinţe - comanda add primeşte şi distanţa pentru legătură, nu doar ip-urile;
2. 02/05/2018 00:20
   • menţiuni suplimentare - format date ieşire - ordinea în care sunt verificate ip-urile;

Flavius e un student pasionat al Facultăţii de Automatică. Cea mai mare pasiune a sa a fost mereu reţelistica, astfel el a urmat modulele de la CISCO. La CISCO, el a învăţat despre OSPF ( Open Shortest Path First ), un protocol care l-a captivat pe Flavius. Aflând că la baza ideii de OSPF se află algoritmul lui Dijkstra, algoritm pe care îl va studia la cursul de SDA, i-a venit o idee. El s-a gândit să simuleze o reţea ce are la bază protocolul OSPF, pentru a aprofuda algoritmul lui Dijkstra (pentru cursul de SDA şi, mai ales, pentru el). Din păcate, săracul Flavius, student silitor, are o problemă. Flavius nu s-a înţeles foarte bine cu programarea şi nici acum nu e foarte priceput, aşa că s-a gândit să vă ceară ajutor cu codul sursă.

Fişierul cu date de intrare va conţine următoarele date:

1. numărul de routere;
2. pentru fiecare router, fiecare atribut pe câte un rând:
   • nume router;
   • IP router;
   • numărul de pc-uri care se conectează la router;
3. pentru fiecare pc care se conectează la router-ul curent, fiecare atribut pe câte un rând:
   • nume pc;
   • IP pc;
   • stare (0 pentru închis, 1 pentru deschis);
4. numărul de conexiuni între routere
5. fiecare conexiune este descrisă pe câte un rând de următoarele, separate print-un spaţiu:
   • numele router-ului de la un capăt;
   • numele router-ului de la celelalt capăt;
   • „distanţa“ (număr întreg) dintre router-e;
6. numărul de operaţii cerute;
7. fiecare operaţie descrisă pe câte un rând.

Ordinea în care sunt scrise operaţiile în fişierul de intrare este ordinea în care vor fi aplicate. Pentru toate operaţiile, pc-urile sau router-ele sunt identificate prin IP.

Operațiile posibile asupra datelor din fișier vor fi:

• ping x.x.x.x x.x.x.x : spune dacă este conexiune între două staţii (ţine cont de conexiunile dintre toate router-ele şi de stările capetelor);
• sipn x.x.x.x : afişează routerele cu care ai legatură directă;
• si x.x.x.x : afişează ce PC-uri sunt conectate (au starea = 1) direct la router;
• trace x.x.x.x x.x.x.x : afişează traseul de la echipament la echipament (ip-urile routerelor ce formează „drumul cel mai scurt“)
• up x.x.x.x : dechide un PC;
• lc x.x.x.x x.x.x.x : distruge legătura dintre 2 routere;
• broke x.x.x.x : închide un PC;
• add x.x.x.x x.x.x.x d: adaugă o legătură între 2 routere, cu „distanţa“ d;

Fişierul de ieşire va conţine rezultatele operaţiilor ce generează un răspuns. Rezultatele sunt scrise în ordinea în care sunt scrise operaţiile primite la intrare, fiecare rezultat este urmat de un final de linie.

1. ping scrie unul din răspunsurile „OK“ sau „NO“;
2. trace, si şi sipn scriu ca răspuns o listă de IP-uri, separate între ele printr-un spaţiu.

Flavius s-a simţit cam vinovat pentru sarcinile pe care vi le-a dat, aşa că s-a gândit să vă dea un exemplu:

date.in

6
Router1
192.0.1.1
1
pc1
192.0.1.2
1
Router2
192.0.2.1
1
pc1
192.0.2.2
1
Router3
192.0.3.1
1
pc1
192.0.3.2
1
Router4
192.0.4.1
1
pc1
192.0.4.2
0
Router5
192.0.5.1
1
pc1
192.0.5.2
1
Router6
192.0.6.1
1
pc1
192.0.6.2
1
8
Router1 Router2 10
Router1 Router3 1
Router3 Router4 5
Router3 Router5 1
Router4 Router2 3
Router4 Router6 1
Router5 Router4 1
Router6 Router2 1
14
ping 192.0.1.2 192.0.4.2
sipn 192.0.4.1
si 192.0.2.1
trace 192.0.1.2 192.0.2.2
up 192.0.4.2
ping 192.0.1.2 192.0.4.2
lc 192.0.3.1 192.0.5.1
trace 192.0.1.2 192.0.2.2
broke 192.0.2.2
add 192.0.3.1 192.0.5.1 10
trace 192.0.1.2 192.0.2.2
up 192.0.2.2
add 192.0.2.1 192.0.4.1 1
trace 192.0.1.2 192.0.2.2

date.out

NO
192.0.2.1 192.0.3.1 192.0.5.1 192.0.6.1
192.0.2.2
192.0.1.1 192.0.3.1 192.0.5.1 192.0.4.1 192.0.6.1 192.0.2.1 
OK
192.0.1.1 192.0.3.1 192.0.4.1 192.0.6.1 192.0.2.1 
 
192.0.1.1 192.0.3.1 192.0.4.1 192.0.2.1

• puteţi încărca mai multe soluţii, se va lua în considerare soluţia cu cel mai mare punctaj trimisă până la termenul limită (6 mai, ora 23:59)
• Arhiva temei va avea numele GrupaSerie_Nume_Prenume_TemaNr.zip și va fi încărcată pe vmchecker, folosind datele de autentificare de pe http://acs.curs.pub.ro/
• Arhiva trimisă conține (direct în rădăcină):
  1. fișierele sursă
  2. Makefile-ul (cu regulile make build și make clean). Executabilul generat trebuie să se numească main
  3. fișierul README în care va fi descrisă soluția problemei

• Implementarea pentru comanda trace se va face pe baza algoritmului lui Dijkstra.
• Nu se acceptă implementări cu memorie alocată static pentru tipurile de date folosite (se acceptă numai variabile locale ce ocupă spaţiu O(1) sau de tip buffer pentru stocare temporară înainte de alocare).
• Menţineţi cel puţin un nivel minimal de aspect al codului şi evitaţi inconsistenţa (indentare haotică, numeroase combinaţii de caractere de tip „leading/trailing whitespace“, numirea variabilelor şi a funcţiilor în ordinea literelor din alfabet).
• Se va depuncta lucrul nemodularizat (fără funcţii) până la 50 pct (din 100) (pentru tot codul scris în main).
• Memoria trebuie eliberată. Dacă nu se respectă această cerință, depunctarea este de pana la 5 pct (din 100) (pentru mai mult de O(1) memorie alocată fără eliberare).
• Dacă soluția voastră nu compilează, dar ideea este bună și trimiteți o încercare de implementare, puteți primi până la 20 pct (din 100).
• Temele care vor fi copiate vor primi 0 pct. Studenţii implicaţi vor figura pe blacklist-ul cursului de SDA.