liquid_feedback_core
changeset 427:97f85b51e3d9
Implemented tie-breaking according to chapter 5 of schulze1.pdf (draft, 2 July 2012)
author | jbe |
---|---|
date | Thu May 22 03:27:39 2014 +0200 (2014-05-22) |
parents | c83b2ac5477b |
children | d0b4fa073ad3 |
files | core.sql |
line diff
1.1 --- a/core.sql Wed May 21 22:01:43 2014 +0200 1.2 +++ b/core.sql Thu May 22 03:27:39 2014 +0200 1.3 @@ -3894,24 +3894,77 @@ 1.4 "primary" INT8, 1.5 "secondary" INT8 ); 1.6 1.7 +COMMENT ON TYPE "link_strength" IS 'TODO'; 1.8 + 1.9 + 1.10 +CREATE FUNCTION "find_best_paths"("matrix_d" "link_strength"[][]) 1.11 + RETURNS "link_strength"[][] 1.12 + LANGUAGE 'plpgsql' IMMUTABLE AS $$ 1.13 + DECLARE 1.14 + "dimension_v" INT4; 1.15 + "matrix_p" "link_strength"[][]; 1.16 + "i" INT4; 1.17 + "j" INT4; 1.18 + "k" INT4; 1.19 + BEGIN 1.20 + "dimension_v" := array_upper("matrix_d", 1); 1.21 + "matrix_p" := "matrix_d"; 1.22 + "i" := 1; 1.23 + LOOP 1.24 + "j" := 1; 1.25 + LOOP 1.26 + IF "i" != "j" THEN 1.27 + "k" := 1; 1.28 + LOOP 1.29 + IF "i" != "k" AND "j" != "k" THEN 1.30 + IF "matrix_p"["j"]["i"] < "matrix_p"["i"]["k"] THEN 1.31 + IF "matrix_p"["j"]["i"] > "matrix_p"["j"]["k"] THEN 1.32 + "matrix_p"["j"]["k"] := "matrix_p"["j"]["i"]; 1.33 + END IF; 1.34 + ELSE 1.35 + IF "matrix_p"["i"]["k"] > "matrix_p"["j"]["k"] THEN 1.36 + "matrix_p"["j"]["k"] := "matrix_p"["i"]["k"]; 1.37 + END IF; 1.38 + END IF; 1.39 + END IF; 1.40 + EXIT WHEN "k" = "dimension_v"; 1.41 + "k" := "k" + 1; 1.42 + END LOOP; 1.43 + END IF; 1.44 + EXIT WHEN "j" = "dimension_v"; 1.45 + "j" := "j" + 1; 1.46 + END LOOP; 1.47 + EXIT WHEN "i" = "dimension_v"; 1.48 + "i" := "i" + 1; 1.49 + END LOOP; 1.50 + RETURN "matrix_p"; 1.51 + END; 1.52 + $$; 1.53 + 1.54 +COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'TODO'; 1.55 1.56 1.57 CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE) 1.58 RETURNS VOID 1.59 LANGUAGE 'plpgsql' VOLATILE AS $$ 1.60 DECLARE 1.61 - "issue_row" "issue"%ROWTYPE; 1.62 - "policy_row" "policy"%ROWTYPE; 1.63 - "dimension_v" INT4; 1.64 - "vote_matrix" INT4[][]; -- absolute votes 1.65 - "matrix" "link_strength"[][]; -- defeat strength / best paths 1.66 - "i" INT4; 1.67 - "j" INT4; 1.68 - "k" INT4; 1.69 - "battle_row" "battle"%ROWTYPE; 1.70 - "rank_ary" INT4[]; 1.71 - "rank_v" INT4; 1.72 - "initiative_id_v" "initiative"."id"%TYPE; 1.73 + "issue_row" "issue"%ROWTYPE; 1.74 + "policy_row" "policy"%ROWTYPE; 1.75 + "dimension_v" INT4; 1.76 + "matrix_a" INT4[][]; -- absolute votes 1.77 + "matrix_d" "link_strength"[][]; -- defeat strength (direct) 1.78 + "matrix_p" "link_strength"[][]; -- defeat strength (best path) 1.79 + "matrix_t" "link_strength"[][]; -- defeat strength (tie-breaking) 1.80 + "matrix_f" BOOLEAN[][]; -- forbidden link (tie-breaking) 1.81 + "matrix_b" BOOLEAN[][]; -- final order (who beats who) 1.82 + "i" INT4; 1.83 + "j" INT4; 1.84 + "m" INT4; 1.85 + "n" INT4; 1.86 + "battle_row" "battle"%ROWTYPE; 1.87 + "rank_ary" INT4[]; 1.88 + "rank_v" INT4; 1.89 + "initiative_id_v" "initiative"."id"%TYPE; 1.90 BEGIN 1.91 PERFORM "require_transaction_isolation"(); 1.92 SELECT * INTO "issue_row" 1.93 @@ -3920,9 +3973,9 @@ 1.94 FROM "policy" WHERE "id" = "issue_row"."policy_id"; 1.95 SELECT count(1) INTO "dimension_v" 1.96 FROM "battle_participant" WHERE "issue_id" = "issue_id_p"; 1.97 - -- Create "vote_matrix" with absolute number of votes in pairwise 1.98 + -- Create "matrix_a" with absolute number of votes in pairwise 1.99 -- comparison: 1.100 - "vote_matrix" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]); 1.101 + "matrix_a" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]); 1.102 "i" := 1; 1.103 "j" := 2; 1.104 FOR "battle_row" IN 1.105 @@ -3931,7 +3984,7 @@ 1.106 "winning_initiative_id" NULLS FIRST, 1.107 "losing_initiative_id" NULLS FIRST 1.108 LOOP 1.109 - "vote_matrix"["i"]["j"] := "battle_row"."count"; 1.110 + "matrix_a"["i"]["j"] := "battle_row"."count"; 1.111 IF "j" = "dimension_v" THEN 1.112 "i" := "i" + 1; 1.113 "j" := 1; 1.114 @@ -3945,18 +3998,18 @@ 1.115 IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN 1.116 RAISE EXCEPTION 'Wrong battle count (should not happen)'; 1.117 END IF; 1.118 - -- Store defeat strengths in "matrix" using "defeat_strength" 1.119 - -- function: 1.120 - "matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); 1.121 + -- Store direct defeat strengths in "matrix_d" using "defeat_strength" 1.122 + -- and "secondary_link_strength" functions: 1.123 + "matrix_d" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); 1.124 "i" := 1; 1.125 LOOP 1.126 "j" := 1; 1.127 LOOP 1.128 IF "i" != "j" THEN 1.129 - "matrix"["i"]["j"] := ( 1.130 + "matrix_d"["i"]["j"] := ( 1.131 "defeat_strength"( 1.132 - "vote_matrix"["i"]["j"], 1.133 - "vote_matrix"["j"]["i"], 1.134 + "matrix_a"["i"]["j"], 1.135 + "matrix_a"["j"]["i"], 1.136 "policy_row"."defeat_strength" 1.137 ), 1.138 "secondary_link_strength"( 1.139 @@ -3973,34 +4026,94 @@ 1.140 "i" := "i" + 1; 1.141 END LOOP; 1.142 -- Find best paths: 1.143 + "matrix_p" := "find_best_paths"("matrix_d"); 1.144 + -- Create partial order: 1.145 + "matrix_b" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]); 1.146 "i" := 1; 1.147 LOOP 1.148 - "j" := 1; 1.149 + "j" := "i" + 1; 1.150 LOOP 1.151 IF "i" != "j" THEN 1.152 - "k" := 1; 1.153 - LOOP 1.154 - IF "i" != "k" AND "j" != "k" THEN 1.155 - IF "matrix"["j"]["i"] < "matrix"["i"]["k"] THEN 1.156 - IF "matrix"["j"]["i"] > "matrix"["j"]["k"] THEN 1.157 - "matrix"["j"]["k"] := "matrix"["j"]["i"]; 1.158 - END IF; 1.159 - ELSE 1.160 - IF "matrix"["i"]["k"] > "matrix"["j"]["k"] THEN 1.161 - "matrix"["j"]["k"] := "matrix"["i"]["k"]; 1.162 - END IF; 1.163 - END IF; 1.164 - END IF; 1.165 - EXIT WHEN "k" = "dimension_v"; 1.166 - "k" := "k" + 1; 1.167 - END LOOP; 1.168 + IF "matrix_p"["i"]["j"] > "matrix_p"["j"]["i"] THEN 1.169 + "matrix_b"["i"]["j"] := TRUE; 1.170 + "matrix_b"["j"]["i"] := FALSE; 1.171 + ELSIF "matrix_p"["i"]["j"] < "matrix_p"["j"]["i"] THEN 1.172 + "matrix_b"["i"]["j"] := FALSE; 1.173 + "matrix_b"["j"]["i"] := TRUE; 1.174 + END IF; 1.175 END IF; 1.176 EXIT WHEN "j" = "dimension_v"; 1.177 "j" := "j" + 1; 1.178 END LOOP; 1.179 - EXIT WHEN "i" = "dimension_v"; 1.180 + EXIT WHEN "i" = "dimension_v" - 1; 1.181 "i" := "i" + 1; 1.182 END LOOP; 1.183 + -- Tie-breaking: 1.184 + IF "policy_row"."tie_breaking" != 'simple'::"tie_breaking" THEN 1.185 + "m" := 1; 1.186 + LOOP 1.187 + "n" := "m" + 1; 1.188 + LOOP 1.189 + IF "matrix_b"["m"]["n"] ISNULL THEN 1.190 + "matrix_t" := "matrix_p"; 1.191 + "matrix_f" := array_fill(FALSE, ARRAY["dimension_v", "dimension_v"]); 1.192 + LOOP 1.193 + "i" := 1; 1.194 + <<forbid_one_link>> 1.195 + LOOP 1.196 + "j" := 1; 1.197 + LOOP 1.198 + IF "i" != "j" THEN 1.199 + IF "matrix_d"["i"]["j"] = "matrix_t"["m"]["n"] THEN 1.200 + "matrix_f"["i"]["j"] := TRUE; 1.201 + -- exit for performance reasons, 1.202 + -- as only one link will be found: 1.203 + EXIT forbid_one_link; 1.204 + END IF; 1.205 + END IF; 1.206 + EXIT WHEN "j" = "dimension_v"; 1.207 + "j" := "j" + 1; 1.208 + END LOOP; 1.209 + IF "i" = "dimension_v" THEN 1.210 + RAISE EXCEPTION 'Schulze tie-breaking does not compute (should not happen)'; 1.211 + END IF; 1.212 + "i" := "i" + 1; 1.213 + END LOOP; 1.214 + "i" := 1; 1.215 + LOOP 1.216 + "j" := 1; 1.217 + LOOP 1.218 + IF "i" != "j" THEN 1.219 + "matrix_t"["i"]["j"] := CASE 1.220 + WHEN "matrix_f"["i"]["j"] 1.221 + THEN (-1::INT8) << 63 1.222 + ELSE "matrix_d"["i"]["j"] END; 1.223 + END IF; 1.224 + EXIT WHEN "j" = "dimension_v"; 1.225 + "j" := "j" + 1; 1.226 + END LOOP; 1.227 + EXIT WHEN "i" = "dimension_v"; 1.228 + "i" := "i" + 1; 1.229 + END LOOP; 1.230 + "matrix_t" := "find_best_paths"("matrix_t"); 1.231 + IF "matrix_t"["m"]["n"] > "matrix_t"["n"]["m"] THEN 1.232 + "matrix_b"["m"]["n"] := TRUE; 1.233 + "matrix_b"["n"]["m"] := FALSE; 1.234 + EXIT; 1.235 + ELSIF "matrix_t"["m"]["n"] < "matrix_t"["n"]["m"] THEN 1.236 + "matrix_b"["m"]["n"] := FALSE; 1.237 + "matrix_b"["n"]["m"] := TRUE; 1.238 + EXIT; 1.239 + END IF; 1.240 + END LOOP; 1.241 + END IF; 1.242 + EXIT WHEN "n" = "dimension_v"; 1.243 + "n" := "n" + 1; 1.244 + END LOOP; 1.245 + EXIT WHEN "m" = "dimension_v" - 1; 1.246 + "m" := "m" + 1; 1.247 + END LOOP; 1.248 + END IF; 1.249 -- Determine order of winners: 1.250 "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]); 1.251 "rank_v" := 1; 1.252 @@ -4013,9 +4126,9 @@ 1.253 IF 1.254 "i" != "j" AND 1.255 "rank_ary"["j"] ISNULL AND 1.256 - ( "matrix"["j"]["i"] > "matrix"["i"]["j"] OR 1.257 + ( "matrix_b"["j"]["i"] OR 1.258 -- tie-breaking by "id" 1.259 - ( "matrix"["j"]["i"] = "matrix"["i"]["j"] AND 1.260 + ( "matrix_b"["j"]["i"] ISNULL AND 1.261 "j" < "i" ) ) 1.262 THEN 1.263 -- someone else is better