Listato 4.4: Configurazione degli influencer
Il file di configurazione nel listato 4.4 contiene la definizione di vari influencer per ognuno di essi và indicato il candidato di riferimento (il candidato verso il quale verranno spostati dei voti) e le probabilità di applicazione per ogni seggio.
Il progetto del simulatore è suddiviso in diversi moduli, l’organizzazione della build è gestita tramite Maven [11]. I progetti che compongono il simulatore sono:
• voting-system-simulator-builder: progetto padre che contiene solo i riferi- menti ai moduli figli
• voting-algorithm: contiene l’implementazione di tutti gli algoritmi di calcolo dei risultati di voto
• voting-system-simulator-core: il simulatore vero e proprio
• voting-system-simulator-gui: una semplice GUI che permette di interagire con il simulatore
• voting-launcher: lanciatore da console delle simulazioni
• voting-web-gui: Gui web per il lancio e la navigazione dei dati
• voting-test-generator: questo è un progetto di utility che è stato usato in fase di sviluppo per generare dei test case
4.1
Implementazione degli algoritmi
L’implementazione dei vari algoritmi è contenuta nel progetto voting-algorithm che contiene inoltre tutti i dto, le enumerazione e le principali interfacce che rappresentano le varie entità del sistema.
Tutti gli algoritmi implementano Algorithm (4.5), un’interfaccia con un generics che andrà implementato con il tipo di voto richiesto. I valori possibili per T sono: OrderedV ote W eighedV ote SingleP ref erenceV ote, ognuna di queste interfacce rappresenta uno dei tipi di voto precedentemente esposti. Poiché abbiamo stabili- to precedentemente che ogni voto, comunque espresso, dovrà poter essere passato come parametro ad ognuno degli algoritmi implementati, ogni implementazione concreta implementa tutte e tre le interfacce che, per semplicità, sono state rac- colte nell’interfaccia V ote in figura (Figura 4.1) il diagramma uml che mostra la struttura dei voti e delle loro implementazioni concrete.
46 4. Realizzazione del simulatore p u b l i c i n t e r f a c e A l g o r i t h m < T e x t e n d s B a s e V o t e > { 2 v o i d a d d V o t e ( T v ); 4 v o i d a d d V o t e s ( List < T > v o t e s ); 6 W i n n e r g e t W i n n e r () t h r o w s I n v a l i d W i n n e r E x c e p t i o n ; 8 W i n n e r g e t W i n n e r (int n ) t h r o w s I n v a l i d W i n n e r E x c e p t i o n ; 10 int g e t C o u n t (); 12 int g e t I n v a l i d (); 14 }
Listato 4.5: Interfaccia Algorithm
p u b l i c i n t e r f a c e O r d e r e d V o t e e x t e n d s S e r i a l i z a b l e { 2 /* * * @ r e t u r n R i t o r n a l ’ o r d i n a m e n t o dei c a n d i d a t i 4 * dal p r e f e r i t o al m e n o d e s i d e r a b i l e */ 6 List < V o t e I t e m > g e t O r d e r (); }
Listato 4.6: Interfacce dei voto a ordinamento
1 p u b l i c i n t e r f a c e W e i g h e d V o t e e x t e n d s S e r i a l i z a b l e { /* *
3 * @ r e t u r n R i t o r n a una m a p p a c o n t e n e n t e * per o g n i c a n d i d a t o il v o t o a s s e g n a t o g l i
5 */
Map < String , Integer > g e t V o t e s (); 7 }
Listato 4.7: Interfacce dei voto pesato
1 p u b l i c i n t e r f a c e S i n g l e P r e f e r e n c e V o t e e x t e n d s S e r i a l i z a b l e { /* *
3 * @ r e t u r n Il c a n d i d a t o s e l e z i o n a t o */
4.1 Implementazione degli algoritmi 47
}
Listato 4.8: Interfacce voto a preferenza singola
Figura 4.1: Uml dei tipi di voto
Ometto per brevità di riportare nel dettaglio tutte le implementazioni che sono comunque consultabili dal repository git del progetto.
Gli algoritmi implementati sono quelli illustrati nella sezione 1.4, ogni algoritmo accetta un certo tipo di voto tra quelli appena esposti
4.1.1
Condorcet
L’algoritmo di Condorcet si base su voti di tipo ordinamento.
Il calcolo dell’algoritmo di Condorcet si basa sulla costruzione di una matrice contenente i risultati di tutti i confronti di coppia come differenza tra il numero di vittorie e il numero di sconfitte. La matrice ha un numero di righe/colonne pari al numero di candidati. La costruzione della matrice avviene dinamicamente all’aggiunta di ogni nuova votazione, in questo modo lo stato interno della classe non deve memorizzare tutti i voti riportati.
Come esempio di costruzione della matrice, ipotizziamo una votazione con tre candidati A, B e C. Se aggiungiamo un primo voto A > B > C la matrice sarà:
48 4. Realizzazione del simulatore 0 1 1 −1 0 1 −1 −1 0
Se ora aggiungiamo un primo voto C > B > A la matrice diventa: 0 2 0 −2 0 0 0 0 0
In questo caso abbiamo che A batte B 2 volte (e di conseguenza B viene battuto due volte da A), tutti gli altri confronti sono in pareggio
Per quanto riguarda il calcolo del vincitore, la soluzione viene costruita per passi successivi: come prima cosa valuta, usando la matrice dei confronti, quale can- didato non è mai battuto da nessuno, poi procede cercando quei candidati che sono battuti solo dal primo classificato, poi quelli che sono battiti dal primo e dal secondo classificato e così via fino a costruire la soluzione completa. Ovviamente, come abbiamo visto nel capitolo 1, nel calcolo del vincitore di Condorcet bisogna prevedere l’esistenza di cicli, quando un ciclo viene rilevato la computazione viene arrestata e ci si limita a fornire una soluzione parziale.
p u b l i c c l a s s A l g o r i t h m C o n d o r c e t e x t e n d s B a s e O r d e r e d A l g o r i t h m { 2 f i n a l int[ ] [ ] m a t r i x ; 4 p u b l i c A l g o r i t h m C o n d o r c e t ( List < String > c a n d i d a t e s ) { s u p e r( c a n d i d a t e s ); 6 m a t r i x = new int[ c a n d i d a t e s . s i z e ( ) ] [ c a n d i d a t e s . s i z e ( ) ] ; } 8 @ O v e r r i d e 10 p r o t e c t e d v o i d a d d V o t e I n t e r n a l ( O r d e r e d V o t e v ) { for (int c1 = 0; c1 < c a n d i d a t e s . s i z e (); c1 ++) { 12 for (int c2 = c1 + 1; c2 < c a n d i d a t e s . s i z e (); c2 ++) { int i n d 1 = A l g o r i t h m U t i l s . i n d e x O f ( c a n d i d a t e s . get ( c1 ) , v ); 14 int i n d 2 = A l g o r i t h m U t i l s . i n d e x O f ( c a n d i d a t e s . get ( c2 ) , v ); 16 int c o m p a r e = I n t e g e r . c o m p a r e ( ind2 , i n d 1 ); m a t r i x [ c1 ][ c2 ] += c o m p a r e ; 18 m a t r i x [ c2 ][ c1 ] += - c o m p a r e ; } 20 } } 22
4.1 Implementazione degli algoritmi 49
@ O v e r r i d e
24 p u b l i c W i n n e r g e t W i n n e r () {
List < V o t e I t e m > v o t e s = new A r r a y L i s t < >(); 26 List < Integer > e x c l u d e = new A r r a y L i s t < >(); 28 w h i l e ( e x c l u d e . s i z e () < m a t r i x . l e n g t h ) {
List < Integer > w = f i n d M a i n W i n n e r ( e x c l u d e );
30 if ( w . i s E m p t y ()) r e t u r n new W i n n e r (true, v o t e s );
v o t e s . add (new V o t e I t e m ( w . s t r e a m (). map ( c a n d i d a t e s :: get ). c o l l e c t ( C o l l e c t o r s . t o L i s t ( ) ) ) ) ; 32 e x c l u d e = v o t e s . s t r e a m () . f l a t M a p ( v o t e I t e m - > v o t e I t e m . g e t C a n d i d a t e s (). s t r e a m ()) 34 . map ( c a n d i d a t e s :: i n d e x O f ) . c o l l e c t ( C o l l e c t o r s . t o L i s t ( ) ) ; 36 } 38 r e t u r n new W i n n e r ( v o t e s ); } 40
p r i v a t e List < Integer > f i n d M a i n W i n n e r ( List < Integer > e x c l u d e ) { 42 int n u m C a n d i d a t e = m a t r i x . l e n g t h ;
ext :
44 for (int c1 = 0; c1 < n u m C a n d i d a t e ; c1 ++) { List < Integer > ret = new A r r a y L i s t < >(); 46 if ( e x c l u d e . c o n t a i n s ( c1 )) c o n t i n u e; for (int c2 = 0; c2 < n u m C a n d i d a t e ; c2 ++) { 48 if ( e x c l u d e . c o n t a i n s ( c2 )) c o n t i n u e; if ( m a t r i x [ c1 ][ c2 ] < 0) c o n t i n u e ext ; 50 if ( m a t r i x [ c1 ][ c2 ] == 0) ret . add ( c2 ); } 52 r e t u r n ret ; } 54 r e t u r n C o l l e c t i o n s . e m p t y L i s t (); } 56 }
50 4. Realizzazione del simulatore
4.1.2
Copeland
L’algoritmo di Copeland è stato implementato come un’estensione di quello di Condorcet, come la classe padre richiede voti di tipo ordinamento.
La costruzione della matrice avviene esattamente come nell’algoritmo di Condor- cet, la differenza tra i due risiede nel calcolo del vincitore. Per Copeland vengono calcolate tutte le vittorie di ogni candidato nei confronti di coppia e vengono sottratte tutte le sconfitte.
Per come è stata realizzata la matrice, possiamo calcolare il numero di vittorie del candidato i come il numero di celle con valore > 0 nella riga i-esima meno il numero di celle con valore < 0 nella riga i-esima Una volta effettuato il calcolo, la sequenza vincitrice si ottiene semplicemente ordinando dal candidato col maggior numero di vittorie a quello con meno vittorie.
1 p u b l i c c l a s s A l g o r i t h m C o p e l a n d e x t e n d s A l g o r i t h m C o n d o r c e t { 3 p u b l i c A l g o r i t h m C o p e l a n d ( List < String > c a n d i d a t e s ) { s u p e r( c a n d i d a t e s ); 5 } 7 @ O v e r r i d e p u b l i c W i n n e r g e t W i n n e r () {
9 Map < String , Integer > v o t e = new HashMap < >( m a t r i x . l e n g t h ); 11 for (int i = 0; i < m a t r i x . l e n g t h ; i ++) {
int val = A r r a y s . s t r e a m ( m a t r i x [ i ]). map ( I n t e g e r :: s i g n u m ). sum (); 13 v o t e . put ( c a n d i d a t e s . get ( i ) , val );
} 15
Map < Integer , List < String > > r e v M a p = v o t e . e n t r y S e t (). s t r e a m ()
17 . map ( e - > new A b s t r a c t M a p . S i m p l e E n t r y < >( e . g e t V a l u e () , e . g e t K e y ( ) ) ) . c o l l e c t (
19 g r o u p i n g B y ( Map . E n t r y :: getKey , m a p p i n g ( Map . E n t r y :: g e t V a l u e , t o L i s t ( ) ) ) ); 21 List < V o t e I t e m > i t e m = r e v M a p . e n t r y S e t (). s t r e a m () . s o r t e d ( C o m p a r a t o r . c o m p a r i n g ( Map . E n t r y :: getKey , C o m p a r a t o r . r e v e r s e O r d e r ( ) ) ) 23 . map ( Map . E n t r y :: g e t V a l u e ) . map ( V o t e I t e m ::new) 25 . c o l l e c t ( t o L i s t ( ) ) ; r e t u r n new W i n n e r ( i t e m ); 27 }
4.1 Implementazione degli algoritmi 51
29 }
Listato 4.10: Implementazione dell’algoritmo di Copeland
4.1.3
Tideman
Anche l’algoritmo di Tideman è implementato come estensione di quello di Con- dorcet.
Come spiegato nel capitolo 1 l’algoritmo di Tideman costruisce la soluzione per passi successivi partendo dai confronti con margine maggiore. I vari confronti vengono quindi ordinati usando la matrice dei confronti, da quelli con il valore nella cella maggiore a quelli con il valore minore. Una volta ordinati i vari vincoli vengono via via aggiunti alla soluzione. Il calcolo del vincitore di Tideman viene realizzato con l’ausilio della libreria JGrapht [8] che fornisce algoritmi e classi di supporto per la gestione dei grafi. L’aggiunta di vincoli viene gestita come la costruzione di un grafo direzionato, all’aggiunta di ogni nuovo vincolo si verifica se sono presenti cicli, in quel caso il nuovo vincolo vine ignorato. Da notare che l’algoritmo di Tideman non gestisce la presenza di pareggi nella soluzione, nel caso in cui più vincoli abbiamo la stessa priorità la scelta di quale applicare è casuale. 1 p u b l i c c l a s s A l g o r i t h m T i d e m a n e x t e n d s A l g o r i t h m C o n d o r c e t { 3 p u b l i c A l g o r i t h m T i d e m a n ( List < String > c a n d i d a t e s ) { s u p e r( c a n d i d a t e s ); 5 } 7 @ O v e r r i d e /*
9 L ’ a l g o r i t m o di e s t r a z i o n e del v i n c i t o r e c o s t r u i s c e una l i s t a con t u t t i i c o n f r o n t i di c o p p i a e il l o r o e s i t o .
11 La l i s t a v i e n e r e a l i z z a t a b a s a n t o s i s u l a l m a p p a dei c o n f r o n t i
13 Una v o l t a o t t e n u t a la l i s t a dei c o n f r o n t i q u e s t a v i e n e o r d i n a t a dal c o n f r o n t o con m a r g i n e m a g g i o r e a q u e l l a con m a r g i n e m i n o r e . 15 I n f i n i la c o s t r u z i o n e d e l l a s o l u z i o n e e d e m a n d a t a a l l a c l a s s e T i d e m a n S o l u t i o n B u i l d e r che p e r m e t t e di a g g i u n g e r e i v a r i c o n f r o n t i ed e v i t a la n a s c i t a di c i c l i 17 In c a s o di p a r e g g i o v i e n e v a l u t a t o s o l o il p r i m o dei c o n f r o n t i 19 */
52 4. Realizzazione del simulatore p u b l i c W i n n e r g e t W i n n e r () { 21 List < Vs > c o m p a r i s o n = new A r r a y L i s t < >( m a t r i x . l e n g t h * m a t r i x . l e n g t h / 2); for (int c1 = 0; c1 < m a t r i x . l e n g t h ; c1 ++) { 23 for (int c2 = 0; c2 < m a t r i x . l e n g t h ; c2 ++) { if ( c1 == c2 ) c o n t i n u e; 25 S t r i n g f i r s t = c a n d i d a t e s . get ( c1 ); S t r i n g s e c o n d = c a n d i d a t e s . get ( c2 );
27 c o m p a r i s o n . add (new Vs ( first , second , m a t r i x [ c1 ][ c2 ] ) ) ; } 29 } 31 T i d e m a n S o l u t i o n B u i l d e r sb = new T i d e m a n S o l u t i o n B u i l d e r ( c a n d i d a t e s ); 33 c o m p a r i s o n . s t r e a m () . s o r t e d (( o1 , o2 ) - > I n t e g e r . c o m p a r e ( o2 . point , o1 . p o i n t )) 35 . f o r E a c h ( i - > sb . add ( i . f i r s t C a n d i d a t e , i . s e c o n d C a n d i d a t e )); 37 r e t u r n sb . r e s u l t (); } 39 /* * 41 * C l a s s e di u t i l i t y per g e s t i r e i c o n f r o n t i */ 43 p r i v a t e c l a s s Vs { p r i v a t e f i n a l S t r i n g f i r s t C a n d i d a t e ; 45 p r i v a t e f i n a l S t r i n g s e c o n d C a n d i d a t e ; p r i v a t e f i n a l int p o i n t ; 47 Vs ( S t r i n g f i r s t C a n d i d a t e , S t r i n g s e c o n d C a n d i d a t e , int p o i n t ) { 49 t h i s. f i r s t C a n d i d a t e = f i r s t C a n d i d a t e ; t h i s. s e c o n d C a n d i d a t e = s e c o n d C a n d i d a t e ; 51 t h i s. p o i n t = p o i n t ; } 53 } 55 }
4.1 Implementazione degli algoritmi 53
4.1.4
Schultze
L’implementazione dell’algoritmo di Schultze usa un approccio differente rispet- to agli altri metodi di Condorcet. In questo cosa all’aggiunta di un nuovo voto non viene popolata una matrice ma una semplice mappa contenente il numero complessivo di vittorie per ogni candidato. Per estrarre la soluzione si ordinano semplicemente i candidati da quello che a ottenuto più vittorie a quello che ne ha ottenute di meno.
1 p u b l i c c l a s s A l g o r i t h m S c h u l t z e e x t e n d s B a s e O r d e r e d A l g o r i t h m {
p r i v a t e f i n a l Map < String , Integer > v o t e = new HashMap < >(); 3
p u b l i c A l g o r i t h m S c h u l t z e ( List < String > c a n d i d a t e s ) { 5 s u p e r( c a n d i d a t e s );
} 7
p r i v a t e Map < Integer , Integer > m a p s = new L i n k e d H a s h M a p < >(); 9 @ O v e r r i d e 11 p r o t e c t e d v o i d a d d V o t e I n t e r n a l ( O r d e r e d V o t e v ) { for ( S t r i n g s : g e t C a n d i d a t e s ()) { 13 v o t e . m e r g e ( s , c o u n t W i n n i n g ( v , s ) , ( i1 , i2 ) - > i1 + i2 ); int p = A l g o r i t h m U t i l s . i n d e x O f (" A ", v ); 15 m a p s . m e r g e ( p , 1 , ( a , b ) - > a + b ); } 17 } 19 @ O v e r r i d e /* 21 L ’ a l g o r i t m o di s c e l t a del v i n c i t o r e si o t t i e n e o r d i n a n d o i c a n d i d a t i da q u e l l o che ha v i n t o piu ’ c o n f r o n t i 23 di c o p p i a in m a n i e r a d i s c e n d e n t e Una v o l t a o t t e n u t o l ’ o r d i n a m e n t o si c o s t r u i s c e a s o l u z i o n e 25 */ p u b l i c W i n n e r g e t W i n n e r () {
27 Map < Integer , List < String > > r e v M a p = v o t e . e n t r y S e t (). s t r e a m () . map ( e - > 29 new A b s t r a c t M a p . S i m p l e E n t r y < >( e . g e t V a l u e () , e . g e t K e y ()) ) 31 . c o l l e c t ( g r o u p i n g B y ( 33 Map . E n t r y :: getKey ,
54 4. Realizzazione del simulatore m a p p i n g ( Map . E n t r y :: g e t V a l u e , t o L i s t ()) 35 ) ); 37 List < V o t e I t e m > i t e m = r e v M a p . e n t r y S e t (). s t r e a m () 39 . s o r t e d ( C o m p a r a t o r . c o m p a r i n g ( Map . E n t r y :: getKey , 41 C o m p a r a t o r . r e v e r s e O r d e r ()) ) 43 . map ( Map . E n t r y :: g e t V a l u e ) . map ( V o t e I t e m ::new) 45 . c o l l e c t ( t o L i s t ( ) ) ; r e t u r n new W i n n e r ( i t e m ); 47 } 49 /* * * M e t o d o che c a l c o l a il n u m e r o di v i t t o r i e di un c a n d i d a t o 51 * nei c o n f r o n t i di c o p p i a in un c e r t o v o t o * 53 * @ p a r a m v V o t o * @ p a r a m c a n d i d a t e C a n d i d a t o 55 * @ r e t u r n N u m e r o di v i t t o r i e */ 57 p u b l i c s t a t i c int c o u n t W i n n i n g ( O r d e r e d V o t e v , S t r i n g c a n d i d a t e ) { int ind = A l g o r i t h m U t i l s . i n d e x O f ( c a n d i d a t e , v ); 59 if ( ind + 1 >= v . g e t O r d e r (). s i z e ()) r e t u r n 0; 61 r e t u r n v . g e t O r d e r (). s u b L i s t ( ind + 1 , v . g e t O r d e r (). s i z e ()) . s t r e a m () 63 . m a p T o I n t ( v o t e I t e m - > v o t e I t e m . g e t C a n d i d a t e s (). s i z e ( ) ) . sum (); } 65 }
Listato 4.12: Implementazione dell’algoritmo di Schultze
4.1.5
Contucci
L’algoritmo di Contucci merita qualche precisazione rispetto a quanto illustrato nel Capitolo 1. Abbiamo visto come Contucci individui le soluzioni vincitrici tra quelle che minimizzano sia la varianza della distanza sia la mu.
4.1 Implementazione degli algoritmi 55
Prima di procedere ad una implementazione dell’algoritmo dobbiamo stabilire co- me valutare quali soluzione considerare nell’insieme delle soluzioni ottime e como filtrare tra queste la soluzione vincitrice.
Per la scelta delle soluzioni ottime ho sfruttato il calcolo del fronte di pareto nel quale la regola di dominazione tra due soluzioni A e B è definita come:
seµ(A) < µ(B) e σ(A) < σ(B) −→ A domina B(A B) seµ(A) > µ(B) e σ(A) > σ(B) −→ B domina A(B A)
Una volta definite le soluzioni ottime, per l’individuazione della soluzione vincitrice ho individuato 3 possibilità:
1. Minimizzare µ: dato il sotto-insieme delle soluzioni ottime individuate dal fronte di pareto, selezioniamo quella che minimizza µ
2. Minimizzare σ: dato il sotto-insieme delle soluzioni ottime individuate dal fronte di pareto, selezioniamo quella che minimizza σ, on caso di pareggio, si sceglie la soluzione che minimizza anche µ
3. Minimizzare d: dato il sotto-insieme delle soluzioni ottime individuate dal fronte di pareto, per ognuna di esse calcolo la d come: d = √µ2+ σ2 e
seleziono la soluzione che minimizza il valore di d
Per quanto riguarda l’implementazione l’algoritmo per il calcolo di µ e σ è neces- sario avere a disposizione tutti i voti forniti, per ridurre la dimensione in memoria della lista, viene salvata una mappa contente la cardinalità di ogni votazione. L’algoritmo può essere configurato con due parametri che permetto di definire:
• La modalità di scelta della soluzione tra quelle del fronte di pareto. • Se includere o meno soluzioni con pareggi tra quelle valutate.
Per il calcolo delle sotto-soluzioni ottime l’algoritmo sfrutta una classe di supporto che si occupa di estrarre il fronte di pareto delle soluzioni fornite.
1 p u b l i c c l a s s A l g o r i t h m C o n t u c c i e x t e n d s B a s e O r d e r e d A l g o r i t h m {
p r i v a t e s t a t i c f i n a l L o g g e r log = L o g M a n a g e r . g e t L o g g e r ( A l g o r i t h m C o n t u c c i .c l a s s); 3 p r i v a t e f i n a l Map < O r d e r e d V o t e , Integer > v o t e s = new C o n c u r r e n t H a s h M a p < >();
p r i v a t e f i n a l A l g o r i t h m C o n t u c c i S e t t i n g s s e t t i n g s ; 5 p r i v a t e f i n a l List < O r d e r e d V o t e > s o l u t i o n S p a c e ; 7 p u b l i c A l g o r i t h m C o n t u c c i ( List < String > c a n d i d a t e s ,
56 4. Realizzazione del simulatore 9 s u p e r( c a n d i d a t e s ); t h i s. s e t t i n g s = s e t t i n g s ; 11 if ( s e t t i n g s . i s A v o i d T i e ()) { s o l u t i o n S p a c e = A l g o r i t h m U t i l s . g e n e r a t e A l l P e r m u t a t i o n W i t h o u t T i e ( c a n d i d a t e s ); 13 } e l s e { s o l u t i o n S p a c e = A l g o r i t h m U t i l s . g e n e r a t e A l l P e r m u t a t i o n ( c a n d i d a t e s ); 15 } } 17 @ O v e r r i d e 19 /* L ’ a l g o r i t m o di c o n t u c c i r i c h i e d e che per il c a l c o l o 21 d e l l a s o l u z i o n e si a b b i a n o t u t t i i v o t i forniti , per r i d u r r e la d i m e n s i o n e in m e m o r i a d e l l a lista , 23 s a l v o il v o t o con la r e l a t i v a c a r d i n a l i t a ’ */ 25 p r o t e c t e d v o i d a d d V o t e I n t e r n a l ( O r d e r e d V o t e v o t e ) t h r o w s I n v a l i d V o t e E x c e p t i o n { O r d e r e d V o t e n e w V o t e = A l g o r i t h m U t i l s . n o r m a l i z e ( c a n d i d a t e s , v o t e ); 27 v o t e s . c o m p u t e ( newVote , ( v , c ) - > c != n u l l ? c + 1 : 1); } 29 @ O v e r r i d e 31 p u b l i c W i n n e r g e t W i n n e r () t h r o w s I n v a l i d W i n n e r E x c e p t i o n { P a r e t o F r o n t i e r < ExtVote > p a r e t o = new P a r e t o F r o n t i e r < >( 33 ( a , b ) - > a . mu < b . mu && a . s i g m a < b . s i g m a ); 35 for ( O r d e r e d V o t e s : s o l u t i o n S p a c e ) { 37 d o u b l e mu = A l g o r i t h m U t i l s . mu ( c a n d i d a t e s , s , v o t e s ); d o u b l e sig = A l g o r i t h m U t i l s . s i g m a ( mu , c a n d i d a t e s , s , v o t e s ); 39 E x t V o t e tmp = new E x t V o t e ( s , mu , sig ); log . d e b u g ( tmp ); 41 p a r e t o . a d d I t e m ( tmp ); } 43 List < ExtVote > f r o n t i e r = p a r e t o . g e t F r o n t i e r (); 45 List < ExtVote > s o l u t i o n s ; s w i t c h ( s e t t i n g s . g e t F r o n t i e r S e l e c t i o n C r i t e r i a ()) { 47 c a s e M i n i m i z e M u : d o u b l e m i n M u = f r o n t i e r . s t r e a m () 49 . m a p T o D o u b l e ( a - > a . mu ). min (). o r E l s e ( 0 ) ;
4.1 Implementazione degli algoritmi 57 s o l u t i o n s = f r o n t i e r . s t r e a m () 51 . f i l t e r ( a - > a . mu == m i n M u ) . c o l l e c t ( C o l l e c t o r s . t o L i s t ( ) ) ; 53 b r e a k; c a s e M i n i m i z e S i g m a : 55 d o u b l e m i n S i g m a = f r o n t i e r . s t r e a m () . m a p T o D o u b l e ( a - > a . s i g m a ) 57 . min (). o r E l s e ( 0 ) ; s o l u t i o n s = f r o n t i e r . s t r e a m () 59 . f i l t e r ( a - > a . s i g m a == m i n S i g m a ) . c o l l e c t ( C o l l e c t o r s . t o L i s t ( ) ) ; 61 d o u b l e m i n M u S i g m a = s o l u t i o n s . s t r e a m () 63 . m a p T o D o u b l e ( a - > a . mu ). min () . o r E l s e ( 0 ) ; 65 s o l u t i o n s = s o l u t i o n s . s t r e a m () . f i l t e r ( a - > a . mu == m i n M u S i g m a ) 67 . c o l l e c t ( C o l l e c t o r s . t o L i s t ( ) ) ; b r e a k; 69 c a s e E q u a l i z e M u A n d S i g m a : d e f a u l t:
71 Map < Double , List < ExtVote > > tmp = f r o n t i e r . s t r e a m () . c o l l e c t (
73 C o l l e c t o r s . g r o u p i n g B y (
a - > M a t h . s q r t ( M a t h . pow ( a . mu , 2) + M a t h . pow ( a . sigma , 2)
75 ) ) 77 ); d o u b l e m i n D i s t = tmp . k e y S e t (). s t r e a m (). m a p T o D o u b l e ( a - > a ). min (). o r E l s e ( 0 ) ; 79 s o l u t i o n s = tmp . get ( m i n D i s t ); b r e a k; 81 } 83 if ( s o l u t i o n s == n u l l || s o l u t i o n s . s i z e () == 0) { 85 S t r i n g err = " W r o n g s o l u t i o n , u n a b l e to c o m p u t e a w i n n e r "; log . e r r o r ( err ); 87 t h r o w new I n v a l i d W i n n e r E x c e p t i o n ( err ); } 89 if ( s o l u t i o n s . s i z e () > 1) { S t r i n g err = " M o r e t h a n one s o l u t i o n , u n a b l e to c o m p u t e a w i n n e r ";
58 4. Realizzazione del simulatore 91 log . e r r o r ( err ); t h r o w new I n v a l i d W i n n e r E x c e p t i o n ( err ); 93 } r e t u r n new W i n n e r ( s o l u t i o n s . get ( 0 ) . v o t e . g e t O r d e r ( ) ) ; 95 } 97 p r i v a t e s t a t i c c l a s s E x t V o t e { p r i v a t e f i n a l O r d e r e d V o t e v o t e ; 99 p r i v a t e f i n a l d o u b l e mu ; p r i v a t e f i n a l d o u b l e s i g m a ; 101 E x t V o t e ( O r d e r e d V o t e vote , d o u b l e mu , d o u b l e s i g m a ) { 103 t h i s. v o t e = v o t e ; t h i s. mu = mu ; 105 t h i s. s i g m a = s i g m a ; } 107 @ O v e r r i d e 109 p u b l i c S t r i n g t o S t r i n g () { r e t u r n v o t e + " ; " + mu + " ; " + s i g m a ; 111 } } 113 }
Listato 4.13: Implementazione dell’algoritmo di Contucci
4.1.6
Maggioritario
Questo è l’unico tra gli algoritmi implementati a richiedere un tipo di voto a pre- ferenza singola. L’algoritmo è piuttosto banale e si limita a calcolare il candidato che ha ottenuto più preferenze.
1
p u b l i c c l a s s A l g o r i t h m M a j o r i t y e x t e n d s B a s e A l g o r i t h m < S i n g l e P r e f e r e n c e V o t e > { 3 p r i v a t e f i n a l Map < String , Integer > r e s u l t s = new HashMap < >();
5 p u b l i c A l g o r i t h m M a j o r i t y ( List < String > c a n d i d a t e s ) {
s u p e r( c a n d i d a t e s );
4.1 Implementazione degli algoritmi 59 9 @ O v e r r i d e p r o t e c t e d v o i d a d d V o t e I n t e r n a l ( S i n g l e P r e f e r e n c e V o t e v o t e ) 11 t h r o w s I n v a l i d V o t e E x c e p t i o n { if ( v o t e . g e t P r e f e r e n c e () == n u l l) r e t u r n; 13 t h r o w new I n v a l i d V o t e E x c e p t i o n (" I n v a l i d n u l l v o t e "); if (! c a n d i d a t e s . c o n t a i n s ( v o t e . g e t P r e f e r e n c e ( ) ) ) 15 t h r o w new I n v a l i d V o t e E x c e p t i o n (" I n v a l i d v o t e for c a n d i d a t e " + v o t e . g e t P r e f e r e n c e ( ) ) ; 17 r e s u l t s . c o m p u t e ( v o t e . g e t P r e f e r e n c e () , ( k , v ) - > v == n u l l ? 1 : v + 1); } 19 @ O v e r r i d e 21 p u b l i c W i n n e r g e t W i n n e r () {
Map < Integer , List < String > > r = r e s u l t s . e n t r y S e t (). s t r e a m () 23 . c o l l e c t ( C o l l e c t o r s . g r o u p i n g B y ( Map . E n t r y :: g e t V a l u e 25 C o l l e c t o r s . m a p p i n g ( Map . E n t r y :: getKey , C o l l e c t o r s . t o L i s t ()) ) 27 ); 29 W i n n e r w = new W i n n e r (); w . s e t O r d e r (new A r r a y L i s t < >()); 31 r . e n t r y S e t (). s t r e a m () . s o r t e d (( o1 , o2 ) - > I n t e g e r . c o m p a r e ( o2 . g e t K e y () , o1 . g e t K e y ( ) ) ) 33 . map ( Map . E n t r y :: g e t V a l u e ) . f o r E a c h ( l i s t - > w . g e t O r d e r (). add (new V o t e I t e m ( l i s t ) ) ) ; 35 r e t u r n w ; } 37 }
Listato 4.14: Implementazione dell’algoritmo Maggioritario
4.1.7
Borda
L’algoritmo di Borda implementato rappresenta una variante di quello mostrato nel capitolo 1. Nella versione implementata Borda accetta un tipo di voto pesato, ogni votante può quindi assegnare un punteggio ad ogni candidato.
Il vincitore è il candidato che ha ottenuto il maggior punteggio.
60 4. Realizzazione del simulatore
p r i v a t e f i n a l Map < String , Integer > r e s u l t s = new C o n c u r r e n t H a s h M a p < >(); 3 p u b l i c A l g o r i t h m B o r d a ( List < String > c a n d i d a t e s ) { 5 s u p e r( c a n d i d a t e s ); } 7 @ O v e r r i d e 9 p r o t e c t e d v o i d a d d V o t e I n t e r n a l ( W e i g h e d V o t e v o t e ) t h r o w s I n v a l i d V o t e E x c e p t i o n { if ( v o t e . g e t V o t e s () == n u l l) 11 t h r o w new I n v a l i d V o t e E x c e p t i o n (" I n v a l i d n u l l v o t e "); v o t e . g e t V o t e s (). f o r E a c h ( 13 ( k , v ) - > r e s u l t s . c o m p u t e ( k , ( rk , rv ) - > rv == n u l l ? v : rv + v ) ); 15 } 17 @ O v e r r i d e p u b l i c W i n n e r g e t W i n n e r () {
19 Map < Integer , List < String > > r = r e s u l t s . e n t r y S e t (). s t r e a m ( . c o l l e c t ( 21 C o l l e c t o r s . g r o u p i n g B y ( Map . E n t r y :: g e t V a l u e , 23 C o l l e c t o r s . m a p p i n g ( Map . E n t r y :: getKey , 25 C o l l e c t o r s . t o L i s t () ) 27 ) ); 29 W i n n e r w = new W i n n e r (); 31 w . s e t O r d e r (new A r r a y L i s t < >()); r . e n t r y S e t (). s t r e a m () 33 . s o r t e d (( o1 , o2 ) - > I n t e g e r . c o m p a r e ( o2 . g e t K e y () , o1 . g e t K e y ( ) ) ) . map ( Map . E n t r y :: g e t V a l u e ) 35 . f o r E a c h ( l i s t - > w . g e t O r d e r (). add (new V o t e I t e m ( l i s t ) ) ) ; r e t u r n w ; 37 } }
4.2 Simulatore 61
4.2
Simulatore
Il simulatore è realizzato all’interno del progetto voting-simulator-core che contiene tutta la logica applicativa. Il simulatore è stato realizzato utilizzando un approccio distribuito basato su TuCSoN [19] e Jade [7].
Grazie all’utilizzo del servizio per Jade "T4j" [20], gli agenti JADE hanno la pos- sibilità di comunicare tramite un tuple centre, nel quale avverrà la maggior parte della coordinazione della simulazione.
La simulazione è stata progettata per permettere la distribuzione dei vari agenti, su nodi distribuiti. Avviando il programma con l’opzione -remote {porta}, creiamo un nodo della simulazione in attesa di ricevere richieste sulla porta passata come parametro.
Se avviato senza l’opzione remote sarà possibile passare come parametro al simula- tore gli host a cui connettersi per creare la rete distribuita di calcolo. I vari agenti (nello specifico i vari seggi) saranno distribuiti tra i vari nodi.
Nel progetto trovano posto 3 tipi di agenti:
4.2.1
SimulationLoaderAgent
Questo agente si occupa di inizializzare tutte le componenti del simulatore e di avviare la simulazione. In particolare ha il compito di gestire la topologia degli agent container e la distribuzione dei vari agenti sulle diverse macchine. L’agente, una volta avviate tutte le componenti del sistema, si occupa di pubblicare la tupla di start nel tuple center che sancisce l’avvio della simulazione.
4.2.2
PolingStationAgent
Gli agenti di tipo PolingStationAgent rappresentano i seggi elettorali. Una volta avviato, ogni agente rimane in attessa della tupla di inizio turno; quando viene avviato un turno la polling station si occupa di inviare i voti sotto forma di tuple nel tuple center.
I voti vengono letti da file nel formato base indicato nel listato 4.2, una volta letti viene applicata l’azione degli influencer (se configurati), infine il voto viene convertito nel tipo richiesto e pubblicato nel tuple center.
62 4. Realizzazione del simulatore
Una volta letti e pubblicati tutti i voti, il seggio rimane in attessa del turno successivo.
4.2.3
ResultAgent
Il ResultAgent si occupa di raccogliere i voti dal tuple center e di passarli all’algo- ritmo della simulazione. Inoltre ha il compito di pubblicare la tupla di fine turno e i risultati attraverso il gestore di eventi 1
L’algoritmo di applicazione degli influencer merita una puntualizzazione:
Algoritmo Influencer L’applicazione dell’effetto degli influencer è stata rea- lizzata mediante l’utilizzo della classe Random. Come illustrato precedentemen- te l’implementazione si basa sul calcolo di un delta da applicare alla preferen- za del candidato oggetto dell’influencer, il calcolo avviene mediante il metodo nextGaussian() della classe Random di seguito un estratto della classe VoteUtils con i metodi che si occupano dell’applicazione del calcolo.
/* * 2 * A p p l i c a la r e g o l a di i n f l u e n z a al v o t o * 4 * @ p a r a m w r a p p e r W r a p p e r del v o t o a cui a p p l i c a r e l ’ i n f l u e n z a * @ p a r a m c a n d i d a t e C a n d i d a t o per il q u a l e a p p l i c a r e l ’ i n f l u e n z a 6 * @ p a r a m m a x V a l u e V a l o r e m a s s i m o d e l l a p r e f e r e n z a * @ p a r a m std p a r a m e t r o di d e f i n i z i o n e del l i v e l l o di i n f l u e n z a 8 */ p u b l i c s t a t i c v o i d a p p l y I n f l u e n c e ( V o t e W r a p p e r wrapper , S t r i n g c a n d i d a t e , 10 int m a x V a l u e , D o u b l e std ) { try {
12 for ( Map . Entry < String , Integer > e : w r a p p e r . g e t C a n d i d a t e P o i n t (). e n t r y S e t ()) {
if (! c a n d i d a t e . c o n t a i n s ( e . g e t K e y ( ) ) ) c o n t i n u e; 14 I n t e g e r n e w V a l = a p p l y P r o b ( e . g e t V a l u e () , m a x V a l u e , std ); if ( O b j e c t s . e q u a l s ( newVal , e . g e t V a l u e ( ) ) ) c o n t i n u e; 16 log . d e b u g (" M o d i f i e d v o t e for c a n d i d a t e {} f r o m {} to {} ", e . g e t K e y () , e . g e t V a l u e () , n e w V a l ); 18 e . s e t V a l u e ( n e w V a l ); r e t u r n;
1Per la gestione delle comunicazioni è stato implementato un semplice gestore di eventi, per
4.2 Simulatore 63 20 } } c a t c h ( E x c e p t i o n e ) { 22 log . e r r o r ( e , e ); } 24 } Listato 4.16: Influencer
4.2.4
Sistema ad eventi
La componente core del simulatore è pensata come un modulo software da richia- mare da altre applicazioni, per questa sua natura è utile pensare ad un meccanismo di comunicazione verso l’esterno che esuli dalla specifica implementazione. Data la natura distribuita del sistema ho deciso di implementare un sistema di eventi. La mia implementazione si basa principalmente su 3 entità:
Event L’interfaccia Event rappresenta un evento, non presenta alcun metodo e viene usata solo come raggruppamento identificativo degli eventi, riporto il banale codice per completezza.
i n t e r f a c e E v e n t { 2 }
Listato 4.17: Interfaccia evento
EventHandler Questa interfaccia permette di definire un gestore da agganciare ad un particolare evento, L’Implementazione dell’azione da eseguire sarà all’inter- no del metogo run(T ) dove T è l’evento che si intende intercettare . Il metodo getT ype() permette all’EventDispatcher di instradare correttamente i vari eventi al loro gestore.
p u b l i c i n t e r f a c e E v e n t H a n d l e r < T e x t e n d s Event > { 2 Class < T > g e t T y p e ();
v o i d run ( T e v e n t ); 4 }
64 4. Realizzazione del simulatore
EventDispatcher Questa classe implementa un singleton a cui andranno ag- ganciati i vari event handler configurati.
2 p u b l i c c l a s s E v e n t D i s p a t c h e r {
p r i v a t e s t a t i c E v e n t D i s p a t c h e r s i n g l e t o n ;
4 p r i v a t e f i n a l Map < Class <? e x t e n d s Event > , List < E v e n t H a n d l e r > > e v e n t s B u s ; 6 p r i v a t e E v e n t D i s p a t c h e r () { e v e n t s B u s = new W e a k H a s h M a p < >(); 8 } 10 p u b l i c s t a t i c E v e n t D i s p a t c h e r get () { if ( s i n g l e t o n == n u l l) { 12 s i n g l e t o n = new E v e n t D i s p a t c h e r (); } 14 r e t u r n s i n g l e t o n ; } 16 p u b l i c < T e x t e n d s Event > v o i d a d d E v e n t H a n d l e r ( E v e n t H a n d l e r < T > h a n d l e r ) { 18 Class < T > e v e n t T y p e = h a n d l e r . g e t T y p e (); e v e n t s B u s . c o m p u t e I f A b s e n t ( e v e n t T y p e , k - > new A r r a y L i s t < >()); 20 e v e n t s B u s . get ( e v e n t T y p e ). add ( h a n d l e r ); } 22 p u b l i c < T e x t e n d s Event > v o i d f i r e E v e n t ( T e v e n t ) { 24 List < E v e n t H a n d l e r > h a n d l e r s = e v e n t s B u s . get ( e v e n t . g e t C l a s s ( ) ) ; if ( h a n d l e r s != n u l l) { 26 for ( E v e n t H a n d l e r < T > h : h a n d l e r s ) { h . run ( e v e n t ); 28 } } 30 } 32 }
Listato 4.19: Classe di gestione degli eventi
Gli eventi configurati per la simulazione sono:
• SimulationStateChangeEvent: evento lanciato ad ogni cambio di stato della simulazione, contiene una enum che indica lo stato corrente (Running, Stop)
4.3 GUI Swing 65
• TurnStartEvent: evento lanciato all’inizio di ogni turno
• TurnEndEvent: evento lanciato alla fine di ogni turno, contiene anche infor- mazioni statistiche relative al turno appena concluso
• ResultUpdateEvent: evento lanciato periodicamente contenente i risultati parziali per il turno in corso
• StatsEvent: evento contenente le statiche di voto delle varie polling station
Tutti gli eventi vengono lanciati dal ResultAgent, essendo in un sistema distribuito il ResultAgent deve essere sempre lanciato nella macchina di avvio della simulazio- ne, in caso contrario non sarebbe possibile agganciarsi agli eventi nel dispatcher; Questo vincolo topologico è gestito all’interno del SimulatorAgent.
La realizzazione distribuita sfruttando gli agenti mi ha permesso di separare net- tamente le competenze tra gli agenti: le polling station si occupano della pubbli- cazione dei voti e non hanno alcuna conoscenza dell’algoritmo che verrà applicato mentre il result agent si occupa esclusivamente di applicare l’algoritmo, ignorando completamente la topologia dei seggi o l’esistenza degli influencer.
4.3
GUI Swing
Per semplificare la fase di sviluppo e permettesse di verificate il funzionamento della gestione ad eventi, ho deciso di implementare una semplice interfaccia swing che mi permettesse di testare diverse configurazioni di lancio, non scenderò nei dettagli implementativi dell’interfaccia che risultano abbastanza banali e per la cui consultazione rimando al codice sorgente.
66 4. Realizzazione del simulatore
Figura 4.2: Interfaccia di test SWING
L’interfaccia permette di caricare i file di configurazione che vengono poi mostrati nella parte sinistra della GUI. Sulla destra viene visualizzato il log delle operazione gestito interamente grazie al sistema di eventi.
4.4
Il Lanciatore
Durante lo sviluppo del simulatore mi sono dovuto confrontare con un problema legato alla ripetibilità dei test. Per alcune simulazione avevo la necessità di ese- guire lo stesso test più volte per verificare la consistenza dei risultati ottenuti, il sistema distribuito basato su TuCSon e Jade non consentiva per svariati motivi di terminare l’intero sistema (tuple center e jade container) e di riavviare la si- mulazione, questo portava inevitabilmente a delle inconsistenze nel sistema dopo un certo numero di simulazioni. Per ovviare a questo problema ho deciso di ag- giungere un modulo software che faccia da strato di separazione tra la componente core e la GUI (GUI web che illustrerò nel paragrafo successivo). Il lanciatore verrà avviato in un JVM separata, questo mi permetterà di ripetere le simulazione senza mai incorrere in rischi di interferenza tra i vari agenti.
Il lanciatore è stato pensato per raccogliere i dati elaborati e immagazzinarli per successive analisi. I dati raccogli dagli eventi lanciati dal simulatore sono imma- gazzinati all’interno di un database Postgresql. La gestione del salvataggio delle
4.5 La GUI web 67
informazioni su db è stata realizzata grazie al framework JPA [9] nella sua im- plementazione eclipse-link [5], in figura (Figura 4.3) il diagramma ER della base dati.
Figura 4.3: Diagramma ER della base dati implementata
Il lanciatore presenta due modalità di avvio, una tramite file i file di configurazione visti precedentemente ( listati 4.1, 4.2, 4.3, 5.1 ) l’altra tramite la configurazio- ne della simulazione nel database. In particolare questa seconda modalità verrà utilizzata per lo sviluppo della webgui.
4.5
La GUI web
Come artefatto finale della simulazione ho realizzato un’interfaccia web per il lancio delle simulazioni e la consultazione dei dati.
Il simulatore web è basato sul framework SpringBoot [17] usando Thymeleaf [18] come template engine per la realizzazione delle pagine web. Il progetto è composto da due sezioni, la sezione di lancio della simulazione e la sezione di consultazione dei dati consultabili attraverso il menù laterale. L’applicazione è stata predisposta per poter essere fruita sia da pc che da dispositivi mobile sfruttando le potenzialità responsive offerte dal framework css Bootstrap [3].
68 4. Realizzazione del simulatore
4.5.1
Launcher
Il lancio della simulazione permette di configurare i vari parametri del modello, l’interfaccia è suddivisa in diverse card ognuna delle quali permette di configurare determinati parametri di lancio. Le informazioni configurabili sono:
• Scelta di un test set (Figura 4.4), per ogni test disponibile vengono mostrati: il numero di seggi, il numero complessivo di voti, il numero di candidati e il valore massimo di preferenza espresso per ogni candidato
• Scelta degli algoritmi (Figura 4.5), è possibili indicare uno o più algoritmi da utilizzare per effettuare la simulazione, in caso di doppio turni multipli, la selezione dei candidati vincitori si baserà sul primo algoritmo selezionato
• Configurazione dei turni (Figura 4.6): si possono selezionare fino a tre turni distinti, per ognuno è possible definire il tipo di voto (preferenza singola,