[MN-dev] [mndiff]: r166 - trunk/ffvotetov/ffvotetov.c
michael
subversion at mplayerhq.hu
Wed Dec 16 02:09:18 CET 2009
Author: michael
Date: Wed Dec 16 02:09:18 2009
New Revision: 166
Log:
Restructure code so things are run twice once based on votes and once
based on margins.
Modified:
trunk/ffvotetov/ffvotetov.c
Modified: trunk/ffvotetov/ffvotetov.c
==============================================================================
--- trunk/ffvotetov/ffvotetov.c Wed Dec 16 01:14:52 2009 (r165)
+++ trunk/ffvotetov/ffvotetov.c Wed Dec 16 02:09:18 2009 (r166)
@@ -77,7 +77,7 @@ void print_condorcet_winners(const int m
break;
}
if(k==canditate_count)
- printf(" %s\n", canditates[j]);
+ printf(" %s\n", canditates[j]);
}
}
@@ -85,13 +85,13 @@ void beatpath(int strength[CANDIDATES_MA
int i, j, changed;
for(i=0; i<canditate_count; i++)
- strength[i]= matrix[a][i] - matrix[i][a];
+ strength[i]= matrix[a][i] > matrix[i][a] ? matrix[a][i] : 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];
+ int diff= matrix[i][j] > matrix[j][i] ? matrix[i][j]: 0;
if(strength[i] < diff)
diff= strength[i];
if(strength[j] < diff){
@@ -103,15 +103,7 @@ void beatpath(int strength[CANDIDATES_MA
}while(changed);
}
-int64_t margins_cmp(int xy, int yx){
- return xy - yx;
-}
-
-int64_t votes_cmp(int xy, int yx){
- return ((int64_t)xy<<24) - yx;
-}
-
-void ranked_pairs(int pair_ranking_matrix[CANDIDATES_MAX][CANDIDATES_MAX], int (*score_fn)(int xy, int yx)){
+void ranked_pairs(int pair_ranking_matrix[CANDIDATES_MAX][CANDIDATES_MAX]){
int j, k;
int64_t limit;
@@ -119,14 +111,14 @@ void ranked_pairs(int pair_ranking_matri
int64_t max=1;
for(j=0; j<canditate_count; j++){
for(k=0; k<canditate_count; k++){
- int64_t diff= score_fn(pair_matrix[j][k], pair_matrix[k][j]);
+ int64_t diff= ((int64_t)pair_matrix[j][k]<<24) - pair_matrix[k][j];
if(diff > max && diff < limit) max=diff;
}
}
limit=max;
for(j=0; j<canditate_count; j++){
for(k=0; k<canditate_count; k++){
- int64_t diff= score_fn(pair_matrix[j][k], pair_matrix[k][j]);
+ int64_t diff= ((int64_t)pair_matrix[j][k]<<24) - pair_matrix[k][j];
if(diff==max){
pair_ranking_matrix[j][k] = pair_matrix[j][k];
pair_ranking_matrix[k][j] = pair_matrix[k][j];
@@ -136,9 +128,9 @@ void ranked_pairs(int pair_ranking_matri
if(contains_loop(pair_ranking_matrix)){
for(j=0; j<canditate_count; j++){
for(k=0; k<canditate_count; k++){
- int64_t diff= score_fn(pair_matrix[j][k], pair_matrix[k][j]);
+ int64_t diff= ((int64_t)pair_matrix[j][k]<<24) - pair_matrix[k][j];
if(diff==max){
- printf("Cycle, ignoring pair %d %d with score of %lld\n", j, k, max);
+ printf(" Cycle, ignoring pair %d %d with score of %lld\n", j, k, max);
pair_ranking_matrix[j][k] =
pair_ranking_matrix[k][j] = 0;
}
@@ -148,6 +140,68 @@ void ranked_pairs(int pair_ranking_matri
}
}
+void do_condercets(void){
+ int i,j,k;
+ int64_t max;
+
+ memset(pair_ranking_matrix, 0, sizeof(pair_ranking_matrix));
+
+ printf(" Pair table:\n");
+ for(j=0; j<canditate_count; j++){
+ for(k=0; k<canditate_count; k++){
+ printf("%4d", pair_matrix[j][k]);
+ }
+ printf("\n");
+ }
+
+ printf(" Condorcet winner(s):\n");
+ print_condorcet_winners(pair_matrix, 0);
+
+ printf(" minimax winner(s):\n");
+ max= INT_MIN;
+ for(j=0; j<canditate_count; j++){
+ int min= INT_MAX;
+ for(k=0; k<canditate_count; k++){
+ int diff= pair_matrix[j][k] - pair_matrix[k][j];
+ if(diff < min) min=diff;
+ }
+ if(min>max) max= min;
+ }
+ print_condorcet_winners(pair_matrix, -max);
+
+ printf(" nameless? sum:\n");
+ max= INT64_MIN;
+ for(i=0; i<2; i++){
+ for(j=0; j<canditate_count; j++){
+ int64_t sum=0;
+ for(k=0; k<canditate_count; k++){
+ if(pair_matrix[j][k] < pair_matrix[k][j]){
+ sum-= (int64_t)pair_matrix[k][j]<<24;
+ }else
+ sum+= pair_matrix[j][k];
+ }
+ if(sum>max) max= sum;
+ if(sum == max && i)
+ printf(" %s\n", canditates[j]);
+ }
+ }
+ ranked_pairs(pair_ranking_matrix);
+ printf(" Ranked pairs winner(s):\n");
+ print_condorcet_winners(pair_ranking_matrix, 0);
+
+ printf(" Cloneproof schwartz sequential droping / beatpath winner(s):\n");
+ for(i=0; i<canditate_count; i++)
+ beatpath(cssd_beats[i], pair_matrix, i);
+ for(i=0; i<canditate_count; i++){
+ for(j=0; j<canditate_count; j++){
+ if(cssd_beats[i][j] < cssd_beats[j][i])
+ break;
+ }
+ if(j==canditate_count)
+ printf(" %s\n", canditates[i]);
+ }
+}
+
void add_vote(int vote[CANDIDATES_MAX]){
int j,k;
@@ -208,64 +262,19 @@ int main(){
for(cand_idx=0; cand_idx<canditate_count; cand_idx++)
printf(" Borda:%3d \"%s\"\n", sums[cand_idx], canditates[cand_idx]);
- printf("Pair table:\n");
- for(j=0; j<canditate_count; j++){
- for(k=0; k<canditate_count; k++){
- printf(" [%4d%4d]", pair_matrix[j][k], pair_matrix[j][k] - pair_matrix[k][j]);
- }
- printf("\n");
- }
-
- printf("Condorcet winner(s):\n");
- print_condorcet_winners(pair_matrix, 0);
+ printf("Condorcet methods based on votes:\n");
+ do_condercets();
- printf("minimax winner(s):\n");
- max= INT_MIN;
for(j=0; j<canditate_count; j++){
- int min= INT_MAX;
for(k=0; k<canditate_count; k++){
- int diff= pair_matrix[j][k] - pair_matrix[k][j];
- if(diff < min) min=diff;
- }
- if(min>max) max= min;
- }
- print_condorcet_winners(pair_matrix, -max);
-
- printf("nameless? sum:\n");
- max= INT64_MIN;
- for(i=0; i<2; i++){
- for(j=0; j<canditate_count; j++){
- int64_t sum=0;
- for(k=0; k<canditate_count; k++){
- int64_t diff= pair_matrix[j][k] - pair_matrix[k][j];
- if(diff < 0) sum+=diff<<24;
- else sum+=diff;
- }
- if(sum>max) max= sum;
- if(sum == max && i)
- printf(" %s\n", canditates[j]);
+ pair_matrix[j][k] -= pair_matrix[k][j];
+ pair_matrix[k][j] = -pair_matrix[j][k];
}
}
- ranked_pairs(pair_ranking_matrix, margins_cmp);
- printf("Ranked pairs (margins) winner(s):\n");
- print_condorcet_winners(pair_ranking_matrix, 0);
- memset(pair_ranking_matrix, 0, sizeof(pair_ranking_matrix));
- ranked_pairs(pair_ranking_matrix, votes_cmp);
- printf("Ranked pairs (votes) winner(s):\n");
- print_condorcet_winners(pair_ranking_matrix, 0);
+ printf("Condorcet methods based on margins:\n");
+ do_condercets();
- printf("Cloneproof schwartz sequential droping / beatpath winner(s):\n");
- for(i=0; i<canditate_count; i++)
- beatpath(cssd_beats[i], pair_matrix, i);
- for(i=0; i<canditate_count; i++){
- for(j=0; j<canditate_count; j++){
- if(cssd_beats[i][j] < cssd_beats[j][i])
- break;
- }
- if(j==canditate_count)
- printf(" %s\n", canditates[i]);
- }
return 0;
}
\ No newline at end of file
More information about the Mndiff-dev
mailing list