[MN-dev] [mndiff]: r165 - trunk/ffvotetov/ffvotetov.c

[michael]

Author: michael
Date: Wed Dec 16 01:14:52 2009
New Revision: 165

Log:
Support Ranked Pairs with votes instead of margins.

Modified:
   trunk/ffvotetov/ffvotetov.c

Modified: trunk/ffvotetov/ffvotetov.c
==============================================================================
--- trunk/ffvotetov/ffvotetov.c	Tue Dec 15 23:51:41 2009	(r164)
+++ trunk/ffvotetov/ffvotetov.c	Wed Dec 16 01:14:52 2009	(r165)
@@ -103,6 +103,51 @@ 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)){
+    int j, k;
+    int64_t limit;
+
+    for(limit=INT_MAX; limit>1; ){
+        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]);
+                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]);
+                if(diff==max){
+                    pair_ranking_matrix[j][k] = pair_matrix[j][k];
+                    pair_ranking_matrix[k][j] = pair_matrix[k][j];
+                }
+            }
+        }
+        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]);
+                    if(diff==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;
+                    }
+                }
+            }
+        }
+    }
+}
+
 void add_vote(int vote[CANDIDATES_MAX]){
     int j,k;
 
@@ -126,7 +171,7 @@ void add_vote(int vote[CANDIDATES_MAX]){
 }
 
 int main(){
-    int i,j, k, num, cand_idx, limit;
+    int i,j, k, num, cand_idx;
     int64_t max;
     char line[1000], *p;
     int last_num=-1;
@@ -201,39 +246,13 @@ int main(){
                 printf(" %s\n", canditates[j]);
         }
     }
+    ranked_pairs(pair_ranking_matrix, margins_cmp);
+    printf("Ranked pairs (margins) winner(s):\n");
+    print_condorcet_winners(pair_ranking_matrix, 0);
 
-    for(limit=INT_MAX; limit>1; ){
-        int max=1; 
-        for(j=0; j<canditate_count; j++){
-            for(k=0; k<canditate_count; k++){
-                int diff= pair_matrix[j][k] - 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++){
-                int diff= pair_matrix[j][k] - 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];
-                }
-            }
-        }
-        if(contains_loop(pair_ranking_matrix)){
-            for(j=0; j<canditate_count; j++){
-                for(k=0; k<canditate_count; k++){
-                    int diff= pair_matrix[j][k] - pair_matrix[k][j];
-                    if(diff==max){
-                        printf("Cycle, ignoring pair %d %d with score of %d\n", j, k, max);
-                        pair_ranking_matrix[j][k] =
-                        pair_ranking_matrix[k][j] = 0;
-                    }
-                }
-            }
-        }
-    }
-    printf("Ranked pairs winner(s):\n");
+    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("Cloneproof schwartz sequential droping / beatpath winner(s):\n");