Table of Contents

Tema 1 - Social Network

Obiective

Descriere

Francis şi Claire, două dintre cele mai populare şi influente persoane publice ale momentului, sunt mereu preocupate de opinia publică. Având în vedere faptul că astăzi cele mai multe informaţii sunt împărtăşite de persoane din toate colţurile globului prin intermediul reţelelor sociale, Francis şi Claire manifestă un interes special pentru acest mod de interacţiune.

Pentru a înţelege cât mai bine modelul şi funcţionalitatea unei astfel de reţele, cei doi s-au gândit să ceară consultanţă studenţilor de la Automatică şi Calculatoare. Cum cel mai bun mod de a explica un concept este printr-un exemplu practic, sarcina voastră fiind să implementaţi o reţea socială cu un model simplificat, dar din care să poată fi extrase informaţii relevante.

Arhitectura reţelei

Vom descrie o reţea socială cu ajutorul unui graf neorientat. Nodurile grafului vor reprezenta utilizatorii, iar muchiile vor descrie relaţiile dintre aceştia. Astfel, va exista o muchie între oricare două noduri dacă şi numai dacă utilizatorii reprezentaţi de cele două noduri sunt prieteni.

Putem exprima această condiţie şi într-un mod formal: 

               ∀ u, v ∈ V(G), (u, v) ∈ E(G) ⇔ prieteni(u, v) = True
                 V - mulţimea nodurilor din G
                 E - mulţimea muchiilor din G

Reprezentarea datelor

Aşa cum am învăţat din primele laboratoare ne vom folosi de conceptul de încapsulare pentru a stoca şi manipula datele într-un mod cât mai simplu şi transparent.

Acestea fiind spuse vom modela utilizatorii reţelei cu ajutorul unei clase User, ce va conţine următoarele informaţii:

Reţeaua propriu-zisă va fi o clasă separată, Network, ce va menţine informaţii despre utilizatorii înregistraţi:

Am evideţiat pentru ambele clase doar membrii relevanţi. Funcţionalităţile expuse de fiecare (prin intermediul metodelor), precum şi informaţiile suplimentare ce ar trebui stocate intern, rămân la latitudinea voastră.

Din descrierea de mai sus a claselor putem deduce faptul că reprezentarea grafului reţelei se va face prin intermediul listelor de adiacenţă. Vom folosi această abordare pentru a simplifica implementarea şi pentru a nu impune regula ca ID-urile utilizatorilor să fie neapărat numere naturale consecutive.

Listă de adiacenţă este o denumire generică. Pentru a stoca informaţiile necesare reţelei puteţi folosi orice structură de date pe care o consideraţi potrivită în acest context, cu condiţia să respecte toate restricţiile enunţate anterior.

Cerințe

Task 1 - Topologia reţelei (30p)

Prima voastră sarcină este să implementaţi funcţionalităţile de bază ale reţelei sociale: adăugarea / ştergerea unui utilizator, adăugarea / ştergerea unei relaţii de prietenie între doi utilizatori, etc.

Pentru a realiza acţiunile enumerate mai sus, reţeaua va trebui să accepte următoarele comenzi:

Task 2 - Comunităţi (30p)

Acum că avem la dispoziţie o reţea socială funcţională ne dorim să extragem informaţii cât mai relevante despre modul în care interacţionează utilizatorii acesteia. Astfel, ne propunem să identificăm, pe baza topologiei grafului, toate comunităţile existente în reţea.

Definim o comunitate ca fiind o componentă conexă a grafului reţelei. O componentă conexă a unui graf neorientat G este reprezentată de un subgraf S cu următoarele proprietăţi:

Mai pe scurt, o comunitate este formată dintr-un grup de utilizatori izolaţi ai reţelei.

Pentru a obţine informaţii despre comunităţile existente vom adăuga funcţionalitate comenzii PRINT descrisă anterior. Aceasta va fi apelată cu parametrul:

Exemplu componente conexe

În graful din imagine am abstractizat utilizatorii prin noduri, notând doar id-urile acestora.

În urma parcurgerii în adâncime (DFS), plecând din nodul 0, vom descoperi componenta conexă (0, 2, 1, 3), apoi, plecând cu o nouă parcurgere din următorul nod rămas nevizitat, vom descoperi componenta (4), iar în final (5, 6, 7).

Output final: 

4: 0 2 1 3
1: 4
3: 5 6 7
Remarcaţi faptul că, deşi nodurile sunt reţinute sortat, output poate să nu fie sortat, datorită modului de operare al algoritmului de parcurgere.

Task 3 - Gradul de socializare (30p)

Ultimul pas, după ce am identificat comunităţile existente în cadrul reţelei de socializare, ar fi să putem determina cât de puternică este o astfel de comunitate. Puterea unei comunităţi sau gradul de socializare îl vom determina în funcţie de diametrul comunităţii la care ne referim.

Diametrul unui graf neorientat şi fără costuri pe muchii (în cazul nostru al unei comunităţi) este dat de lungimea celui mai lung drum între oricare două noduri ale sale. Cel mai simplu mod de a calcula diametrul este să efectuăm câte o parcurgere în lăţime din fiecare nod al grafului, reţinând de fiecare dată distanţa celei mai lungi căi descoperite. Cu cât această cale este mai scurtă, cu atât o comunitate este mai unită, deci mai puternică.

Lungimea unei căi de la un nod de start la nodul curent, într-o parcurgere în lăţime, este dată de numărul de noduri intermediare explorate între nodul start şi nodul curent, inclusiv. Pentru a calcula mai uşor distanţa faţă de nodul de start, puteţi să vă folosiţi de relaţia: 

                  d(curent) = d(părinte) + 1, curent != start
                  d(curent) = 0,              curent == start

După ce am obţinut diametrul comunităţii vom calcula, pe baza lui, gradul de socializare după cum urmează: 

                  g = (N - D) * 100 / (N - 1), N != 1
                  g = 0,                       N == 1
                    N - numărul de utilizatori din comunitate
                    D - diametrul comunităţii

Accesul la această informaţie se va face prin intermediul comenzii PRINT, care va fi apelată cu doi parametri:

Exemplu grad de socializare

Pentru simplitate vom folosi acelaşi graf ca în exemplu anterior.

Considerăm ca am primit comanda PRINT STRENGTH 2.

Pasul I

Pasul II

Pasul III

Pasul IV

Output final: 

33
Analog, aplicând acelaşi algoritm pentru comunităţile (4) şi (5, 6, 7) vom obţine g = 0(%), respectiv g = 100(%). Observaţi că un utilizator fără prieteni are un grad de socializare nul, iar o comunitate în care toţi utilizatorii sunt prieteni între ei are un grad de socializare maxim.

Precizări

Comenzile descrise în secţiunea Cerinţe vor fi citite dintr-un fişier primit ca parametru în terminal. Pentru a putea accesa parametrii cu care a fost lansată în execuţie aplicaţia, Java VM îi pasează metodei public static void main(String[] args), sub forma array-ului args.

Fiecare comandă din fişierul de intrare se va afla pe câte o linie.

Output-ul fiecărei comenzi se va afişa la stdout utilizând metoda System.out.println.

Implementare

File I/O & Entry Point

Deoarece Java I/O, în special lucrul cu fişiere, reprezintă un subiect abordat în cea de a doua parte a cursului (Pattern-ul Decorator), vă punem la dispoziţie clasa FileParser care implementează funcţionalităţile de bază pentru citirea din fişiere.

De asemenea, clasa ce va conţine metoda public static void main(String[] args) va trebui să poarte numele Main.

The Network

Din punct de vedere logic, reţeaua socială reprezintă o entitate globală, unică. Acest detaliu ne forţează să permitem instanţierea clasei Network o singură dată. Pentru a realiza asta vom folosi pattern-ul Singleton.

Pattern-ul Singleton este un design pattern care restricţionează instanţierea unei clase la un singur obiect. Pattern-ul este folosit adesea în cazuri în care, din punct de vedere logic, design-ul unei aplicaţii nu permite sau nu necesită mai multe instanţe ale unei clase, aşa cum se întâmplă şi în cazul nostru.

Pentru a putea limita instanţierea unei clase la un singur obiect va trebui să marcăm toţi constructorii clasei cu modificatorul de acces private, acest trick impiedicând instaţierea explicită. Atenţie: chiar dacă nu dorim să definim constructor(i) pentru clasa singleton, deoarece constructorul default are modificatorul de acces public, va trebui totuşi să definim un contructor private (cu sau fără parametrii), al cărui corp să nu conţină nici o instrucţiune, pentru a suprascrie constructorul default.

Tot ce ne mai rămâne de făcut este să găsim un mecanism prin care să accesăm, în siguranţă, unica instanţă a clasei singleton. Soluţia este să reţinem această instanţă intern (private), şi să o expunem prin intermediul unei metode publice getInstance(). Cum nu putem apela metoda getInstance() pe un obiect, aceasta va fi precedată de cuvântul-cheie static şi va aparţine clasei. Din considerente de corectitudine, vom utiliza cuvântul-cheie static şi la declararea internă a instanţei.

Exemplu Singleton

Singleton.java
public class Singleton {
 
    /* eager instantiation */
    private static final Singleton INSTANCE = new Singleton();
 
    private Singleton() {
        /* initialization code */
    }
 
    /* obtain the one and only instance */
    public static Singleton getInstance() {
        return INSTANCE;
    }
 
}

Punctaj

Comentariile tuturor claselor şi metodelor relevante vor trebui să respecte formatul Javadoc.

Nu uitați de paginile wiki: indicații pentru teme şi coding style.

Temele vor fi testate împotriva plagiatului. Orice tentativă de copiere va duce la anularea punctajului de pe parcursul semestrului şi repetarea materiei atât pentru sursă(e) cât şi pentru destinație(ii), fără excepție.

Format arhivă

Arhiva pe care o veţi urca pe Vmchecker va trebui să conţină în directorul rădăcină:

Resurse

Referințe