December 2009 - Mndiff-dev - lists.mplayerhq.hu

[mndiff]: r179 - trunk/ffvotetov/input.txt
by michael 21 Dec '09

21 Dec '09

Author: michael Date: Mon Dec 21 21:32:17 2009 New Revision: 179 Log: The remaining votes. Modified: trunk/ffvotetov/input.txt Modified: trunk/ffvotetov/input.txt ============================================================================== --- trunk/ffvotetov/input.txt Fri Dec 18 20:51:02 2009 (r178) +++ trunk/ffvotetov/input.txt Mon Dec 21 21:32:17 2009 (r179) @@ -132,3 +132,46 @@ From: Alexander Strange 2. FFMTech (Foundation for Free Multimedia Technologies) 3. FFmedia (Foundation for Free MultimEDIA) +From: Me: +1. FFmedia (Foundation for Free Multimedia) +2. FFm.org (Foundation for Free Multimedia) +3. FFmpeg Foundation +4. Free Multimedia Tech / freemediatech.org + +From: Fran�ois Revol + +2. FFmedia (Foundation for Free MultimEDIA) +3. FFMTech (Foundation for Free Multimedia Technologies) +1. Free Multimedia Tech / freemediatech.org +4. FFmpeg Foundation + +From: Reimar D�ffinger + +1. FFmedia (Foundation for Free MultimEDIA) +2. FFmpeg Foundation +3. Free Multimedia Tech / freemediatech.org + +From: Sascha Sommer + +1. FFmedia (Foundation for Free MultimEDIA) +2. FFmpeg Foundation + +From: Carl Eugen Hoyos + +1 FFMTech (Foundation for Free Multimedia Technologies) +2 FFmedia (Foundation for Free MultimEDIA) +3 Free Multimedia Tech / freemediatech.org + +From: pross + +1. FFmedia (Foundation for Free MultimEDIA) +2. FFmpeg Foundation + +From: Baptiste Coudurier + +1) FFMTech (Foundation for Free Multimedia Technologies) +2) FFmedia (Foundation for Free MultimEDIA) +3) FFm.org (Foundation for Free Multimedia) + + +___ \ No newline at end of file

1 0

[mndiff]: r178 - trunk/ffvotetov/ffvotetov.c
by michael 18 Dec '09

18 Dec '09

Author: michael Date: Fri Dec 18 20:51:02 2009 New Revision: 178 Log: Better tie breaking for IRV. Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Fri Dec 18 19:52:51 2009 (r177) +++ trunk/ffvotetov/ffvotetov.c Fri Dec 18 20:51:02 2009 (r178) @@ -212,6 +212,7 @@ void print_irv(void){ printf("Instant runoff winners:\n"); for(;;){ int votes[CANDIDATES_MAX]={0}; + int votes2[CANDIDATES_MAX]={0}; int min= INT_MAX; int non_min= 0; @@ -222,19 +223,33 @@ void print_irv(void){ } for(i=0; i<canditate_count; i++){ fprintf(stderr, "%3d", votes[i]); + if(!droped_canditates[i] && votes[i] < min) + min=votes[i]; + } + + for(i=0; i<vote_count; i++){ + for(j=0; j<canditate_count && irv[i][j] && droped_canditates[irv[i][j]-1]; j++); + if(j<canditate_count && irv[i][j] && votes[ irv[i][j]-1 ]== min) + j++; + for(; j<canditate_count && irv[i][j] && droped_canditates[irv[i][j]-1]; j++); + if(irv[i][j]) + votes2[ irv[i][j]-1 ]++; + } + min= INT_MAX; + for(i=0; i<canditate_count; i++){ + fprintf(stderr, "%3d", votes2[i]); if(!droped_canditates[i]){ - if(min != INT_MAX && votes[i] != min) - non_min=1; - if(votes[i] <= min){ - min=votes[i]; - } + if(min != INT_MAX && votes2[i] != min) + non_min= 1; + if(votes2[i] <= min) + min=votes2[i]; } } fprintf(stderr, "\n"); if(!non_min) break; for(i=0; i<canditate_count; i++){ - if(votes[i] == min) + if(votes2[i] == min) droped_canditates[i]=1; } }

1 0

[mndiff]: r177 - trunk/ffvotetov/ffvotetov.c
by michael 18 Dec '09

18 Dec '09

Author: michael Date: Fri Dec 18 19:52:51 2009 New Revision: 177 Log: Remove unused variables Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Fri Dec 18 19:50:50 2009 (r176) +++ trunk/ffvotetov/ffvotetov.c Fri Dec 18 19:52:51 2009 (r177) @@ -245,7 +245,6 @@ void print_irv(void){ void add_vote(int vote[CANDIDATES_MAX]){ int j,k; - int irv_count=0; irv= realloc(irv, sizeof(*irv)*(vote_count+1)); if(!irv){ @@ -278,8 +277,7 @@ void add_vote(int vote[CANDIDATES_MAX]){ } int main(){ - int i,j, k, num, cand_idx; - int64_t max; + int j, k, num, cand_idx; char line[1000], *p; int vote[CANDIDATES_MAX]={0};

1 0

[mndiff]: r176 - trunk/ffvotetov/ffvotetov.c
by michael 18 Dec '09

18 Dec '09

Author: michael Date: Fri Dec 18 19:50:50 2009 New Revision: 176 Log: Add instant runoff voting support. Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Thu Dec 17 04:13:42 2009 (r175) +++ trunk/ffvotetov/ffvotetov.c Fri Dec 18 19:50:50 2009 (r176) @@ -37,6 +37,9 @@ int pair_ranking_matrix[CANDIDATES_MAX][ int64_t cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX]; +int (*irv)[CANDIDATES_MAX]; +int vote_count; + int contains_loop(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX]){ int m[CANDIDATES_MAX][CANDIDATES_MAX]; int s[CANDIDATES_MAX]={0}; @@ -202,8 +205,55 @@ void do_condercets(void){ } } +void print_irv(void){ + int droped_canditates[CANDIDATES_MAX]={0}; + int i, j; + + printf("Instant runoff winners:\n"); + for(;;){ + int votes[CANDIDATES_MAX]={0}; + int min= INT_MAX; + int non_min= 0; + + for(i=0; i<vote_count; i++){ + for(j=0; j<canditate_count && irv[i][j] && droped_canditates[irv[i][j]-1]; j++); + if(irv[i][j]) + votes[ irv[i][j]-1 ]++; + } + for(i=0; i<canditate_count; i++){ + fprintf(stderr, "%3d", votes[i]); + if(!droped_canditates[i]){ + if(min != INT_MAX && votes[i] != min) + non_min=1; + if(votes[i] <= min){ + min=votes[i]; + } + } + } + fprintf(stderr, "\n"); + if(!non_min) + break; + for(i=0; i<canditate_count; i++){ + if(votes[i] == min) + droped_canditates[i]=1; + } + } + for(i=0; i<canditate_count; i++) + if(!droped_canditates[i]) + printf(" %s\n", canditates[i]); +} + void add_vote(int vote[CANDIDATES_MAX]){ int j,k; + int irv_count=0; + + irv= realloc(irv, sizeof(*irv)*(vote_count+1)); + if(!irv){ + fprintf(stderr, "out of memory\n"); + exit(1); + } + for(j=0; j<CANDIDATES_MAX; j++) + irv[vote_count][j]=0; for(j=0; j<CANDIDATES_MAX; j++){ if(vote[j]>0 && vote[j] <=10){ @@ -218,7 +268,10 @@ void add_vote(int vote[CANDIDATES_MAX]){ if(score_j > score_k) pair_matrix[k][j]++; } + if(vote[j]>0 && vote[j]<=CANDIDATES_MAX) + irv[vote_count][ vote[j] - 1 ]= j+1; } + vote_count++; for(j=0; j<CANDIDATES_MAX; j++) vote[j]=0; @@ -257,6 +310,8 @@ int main(){ for(cand_idx=0; cand_idx<canditate_count; cand_idx++) printf(" Borda:%3d %3d\"%s\"\n", sums[cand_idx] + subs[cand_idx]*canditate_count, sums[cand_idx] + 10*subs[cand_idx], canditates[cand_idx]); + print_irv(); + printf("Condorcet methods based on votes:\n"); do_condercets();

1 0

[mndiff]: r175 - trunk/ffvotetov/ffvotetov.c
by michael 17 Dec '09

17 Dec '09

Author: michael Date: Thu Dec 17 04:13:42 2009 New Revision: 175 Log: ;;->; [precommit script is buggy we need fake text] Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Thu Dec 17 03:44:59 2009 (r174) +++ trunk/ffvotetov/ffvotetov.c Thu Dec 17 04:13:42 2009 (r175) @@ -35,7 +35,7 @@ int sums[CANDIDATES_MAX], subs[CANDIDATE int pair_matrix[CANDIDATES_MAX][CANDIDATES_MAX]; int pair_ranking_matrix[CANDIDATES_MAX][CANDIDATES_MAX]; -int64_t cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX];; +int64_t cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX]; int contains_loop(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX]){ int m[CANDIDATES_MAX][CANDIDATES_MAX];

1 0

[mndiff]: r174 - trunk/ffvotetov/ffvotetov.c
by michael 17 Dec '09

17 Dec '09

Author: michael Date: Thu Dec 17 03:44:59 2009 New Revision: 174 Log: Add a borda count based on 10points in addition to a candidate based one. (for future votes) Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Thu Dec 17 02:03:52 2009 (r173) +++ trunk/ffvotetov/ffvotetov.c Thu Dec 17 03:44:59 2009 (r174) @@ -206,7 +206,7 @@ void add_vote(int vote[CANDIDATES_MAX]){ int j,k; for(j=0; j<CANDIDATES_MAX; j++){ - if(vote[j]){ + if(vote[j]>0 && vote[j] <=10){ sums[j] -= vote[j]; subs[j] ++; } @@ -252,12 +252,10 @@ int main(){ add_vote(vote); } add_vote(vote); - for(j=0; j<canditate_count; j++) - sums[j] += subs[j]*canditate_count; printf("Candidates:\n"); for(cand_idx=0; cand_idx<canditate_count; cand_idx++) - printf(" Borda:%3d \"%s\"\n", sums[cand_idx], canditates[cand_idx]); + printf(" Borda:%3d %3d\"%s\"\n", sums[cand_idx] + subs[cand_idx]*canditate_count, sums[cand_idx] + 10*subs[cand_idx], canditates[cand_idx]); printf("Condorcet methods based on votes:\n"); do_condercets();

1 0

[mndiff]: r173 - trunk/ffvotetov/ffvotetov.c
by michael 17 Dec '09

17 Dec '09

Author: michael Date: Thu Dec 17 02:03:52 2009 New Revision: 173 Log: Never implement an algorithm based on its description on wikipedia. Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Wed Dec 16 14:42:18 2009 (r172) +++ trunk/ffvotetov/ffvotetov.c Thu Dec 17 02:03:52 2009 (r173) @@ -35,7 +35,7 @@ int sums[CANDIDATES_MAX], subs[CANDIDATE int pair_matrix[CANDIDATES_MAX][CANDIDATES_MAX]; int pair_ranking_matrix[CANDIDATES_MAX][CANDIDATES_MAX]; -int cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX];; +int64_t cssd_beats[CANDIDATES_MAX][CANDIDATES_MAX];; int contains_loop(const int matrix[CANDIDATES_MAX][CANDIDATES_MAX]){ int m[CANDIDATES_MAX][CANDIDATES_MAX]; @@ -81,17 +81,17 @@ void print_condorcet_winners(const int m } } -void beatpath(int strength[CANDIDATES_MAX], const int matrix[CANDIDATES_MAX][CANDIDATES_MAX], int a){ +void beatpath(int64_t strength[CANDIDATES_MAX], const int matrix[CANDIDATES_MAX][CANDIDATES_MAX], int a){ int i, j, changed; for(i=0; i<canditate_count; i++) - strength[i]= matrix[a][i] > matrix[i][a] ? matrix[a][i] : 0; + strength[i]= matrix[a][i] > matrix[i][a] ? (matrix[a][i]<<24) - matrix[i][a] : 0; do{ changed=0; for(i=0; i<canditate_count; i++){ for(j=0; j<canditate_count; j++){ - int diff= matrix[i][j] > matrix[j][i] ? matrix[i][j]: 0; + int64_t diff= matrix[i][j] > matrix[j][i] ? (matrix[i][j]<<24) - matrix[j][i]: 0; if(strength[i] < diff) diff= strength[i]; if(strength[j] < diff){

1 0

[mndiff]: r172 - trunk/ffvotetov/input.txt
by michael 16 Dec '09

16 Dec '09

Author: michael Date: Wed Dec 16 14:42:18 2009 New Revision: 172 Log: 3 more votes. Modified: trunk/ffvotetov/input.txt Modified: trunk/ffvotetov/input.txt ============================================================================== --- trunk/ffvotetov/input.txt Wed Dec 16 03:05:58 2009 (r171) +++ trunk/ffvotetov/input.txt Wed Dec 16 14:42:18 2009 (r172) @@ -110,3 +110,25 @@ From: "Reynaldo H. Verdejo Pinochet" 2.- FFmpeg Foundation 3.- FFmedia (Foundation for Free MultimEDIA) 4.- FFm.org (Foundation for Free Multimedia) + +From: Dominik 'Rathann' Mierzejewski + +1 OMF (Open Multimedia Foundation) +2 FFMTech (Foundation for Free Multimedia Technologies) +3 Free Multimedia Tech / freemediatech.org +4 FFmedia (Foundation for Free MultimEDIA) + +From: Robert Swain + +1 Free Multimedia Tech / freemediatech.org +2 FFMTech (Foundation for Free Multimedia Technologies) +3 OMF (Open Multimedia Foundation) +4 FFmpeg Foundation +5 FFm.org (Foundation for Free Multimedia) + +From: Alexander Strange + +1. FFmpeg Foundation +2. FFMTech (Foundation for Free Multimedia Technologies) +3. FFmedia (Foundation for Free MultimEDIA) +

1 0

[mndiff]: r171 - trunk/ffvotetov/ffvotetov.c
by michael 16 Dec '09

16 Dec '09

Author: michael Date: Wed Dec 16 03:05:58 2009 New Revision: 171 Log: Fix harmless *2 bug. Modified: trunk/ffvotetov/ffvotetov.c Modified: trunk/ffvotetov/ffvotetov.c ============================================================================== --- trunk/ffvotetov/ffvotetov.c Wed Dec 16 02:30:08 2009 (r170) +++ trunk/ffvotetov/ffvotetov.c Wed Dec 16 03:05:58 2009 (r171) @@ -263,7 +263,7 @@ int main(){ do_condercets(); for(j=0; j<canditate_count; j++){ - for(k=0; k<canditate_count; k++){ + for(k=j+1; k<canditate_count; k++){ pair_matrix[j][k] -= pair_matrix[k][j]; pair_matrix[k][j] = -pair_matrix[j][k]; }

1 0

[mndiff]: r170 - trunk/ffvotetov/marginstest.txt
by michael 16 Dec '09

16 Dec '09

Author: michael Date: Wed Dec 16 02:30:08 2009 New Revision: 170 Log: Input to test margins vs. votes and rating of candidates equal. Added: trunk/ffvotetov/marginstest.txt Added: trunk/ffvotetov/marginstest.txt ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/ffvotetov/marginstest.txt Wed Dec 16 02:30:08 2009 (r170) @@ -0,0 +1,53 @@ +1 B +1 C +2 A +- +1 B +1 C +2 A +- +1 B +1 C +2 A +- +1 B +1 C +2 A +- +1 A +- +1 A +- +1 A +- +1 A +- +1 A +2 B +3 C +- +1 B +2 C +3 A +- +1 C +2 A +3 B +- + +1 B +2 C +3 A +- +1 A +2 B +3 C +- +1 B +2 C +3 A +- +1 A +2 B +3 C +- \ No newline at end of file

1 0