liquid_feedback_core
changeset 428:d0b4fa073ad3
Code cleanup regarding new tie-breaking
author | jbe |
---|---|
date | Thu May 22 04:35:26 2014 +0200 (2014-05-22) |
parents | 97f85b51e3d9 |
children | a16072fc288a |
files | core.sql |
line diff
1.1 --- a/core.sql Thu May 22 03:27:39 2014 +0200 1.2 +++ b/core.sql Thu May 22 04:35:26 2014 +0200 1.3 @@ -415,8 +415,8 @@ 1.4 COMMENT ON COLUMN "policy"."issue_quorum_den" IS 'Denominator of potential supporter quorum to be reached by one initiative of an issue to be "accepted" and enter issue state ''discussion'''; 1.5 COMMENT ON COLUMN "policy"."initiative_quorum_num" IS 'Numerator of satisfied supporter quorum to be reached by an initiative to be "admitted" for voting'; 1.6 COMMENT ON COLUMN "policy"."initiative_quorum_den" IS 'Denominator of satisfied supporter quorum to be reached by an initiative to be "admitted" for voting'; 1.7 -COMMENT ON COLUMN "policy"."defeat_strength" IS 'How pairwise defeats are measured for the Schulze method; see type "defeat_strength"'; 1.8 -COMMENT ON COLUMN "policy"."tie_breaking" IS 'Tie-breaker for the Schulze method; see type "tie_breaking"'; 1.9 +COMMENT ON COLUMN "policy"."defeat_strength" IS 'How pairwise defeats are measured for the Schulze method; see type "defeat_strength"; ''tuple'' is the recommended setting'; 1.10 +COMMENT ON COLUMN "policy"."tie_breaking" IS 'Tie-breaker for the Schulze method; see type "tie_breaking"; ''variant1'' or ''variant2'' are recommended'; 1.11 COMMENT ON COLUMN "policy"."direct_majority_num" IS 'Numerator of fraction of neccessary direct majority for initiatives to be attainable as winner'; 1.12 COMMENT ON COLUMN "policy"."direct_majority_den" IS 'Denominator of fraction of neccessary direct majority for initaitives to be attainable as winner'; 1.13 COMMENT ON COLUMN "policy"."direct_majority_strict" IS 'If TRUE, then the direct majority must be strictly greater than "direct_majority_num"/"direct_majority_den", otherwise it may also be equal.'; 1.14 @@ -3894,7 +3894,7 @@ 1.15 "primary" INT8, 1.16 "secondary" INT8 ); 1.17 1.18 -COMMENT ON TYPE "link_strength" IS 'TODO'; 1.19 +COMMENT ON TYPE "link_strength" IS 'Type to store the defeat strength of a link between two candidates plus a secondary criterion to create unique link strengths between the candidates (needed for tie-breaking ''variant1'' and ''variant2'')'; 1.20 1.21 1.22 CREATE FUNCTION "find_best_paths"("matrix_d" "link_strength"[][]) 1.23 @@ -3941,7 +3941,7 @@ 1.24 END; 1.25 $$; 1.26 1.27 -COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'TODO'; 1.28 +COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'Computes the strengths of the best beat-paths from a square matrix'; 1.29 1.30 1.31 CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE) 1.32 @@ -3973,7 +3973,7 @@ 1.33 FROM "policy" WHERE "id" = "issue_row"."policy_id"; 1.34 SELECT count(1) INTO "dimension_v" 1.35 FROM "battle_participant" WHERE "issue_id" = "issue_id_p"; 1.36 - -- Create "matrix_a" with absolute number of votes in pairwise 1.37 + -- create "matrix_a" with absolute number of votes in pairwise 1.38 -- comparison: 1.39 "matrix_a" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]); 1.40 "i" := 1; 1.41 @@ -3998,7 +3998,7 @@ 1.42 IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN 1.43 RAISE EXCEPTION 'Wrong battle count (should not happen)'; 1.44 END IF; 1.45 - -- Store direct defeat strengths in "matrix_d" using "defeat_strength" 1.46 + -- store direct defeat strengths in "matrix_d" using "defeat_strength" 1.47 -- and "secondary_link_strength" functions: 1.48 "matrix_d" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); 1.49 "i" := 1; 1.50 @@ -4025,9 +4025,9 @@ 1.51 EXIT WHEN "i" = "dimension_v"; 1.52 "i" := "i" + 1; 1.53 END LOOP; 1.54 - -- Find best paths: 1.55 + -- find best paths: 1.56 "matrix_p" := "find_best_paths"("matrix_d"); 1.57 - -- Create partial order: 1.58 + -- create partial order: 1.59 "matrix_b" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]); 1.60 "i" := 1; 1.61 LOOP 1.62 @@ -4048,16 +4048,24 @@ 1.63 EXIT WHEN "i" = "dimension_v" - 1; 1.64 "i" := "i" + 1; 1.65 END LOOP; 1.66 - -- Tie-breaking: 1.67 + -- tie-breaking by forbidding shared weakest links in beat-paths 1.68 + -- (unless "tie_breaking" is set to 'simple', in which case tie-breaking 1.69 + -- is performed later by initiative id): 1.70 IF "policy_row"."tie_breaking" != 'simple'::"tie_breaking" THEN 1.71 "m" := 1; 1.72 LOOP 1.73 "n" := "m" + 1; 1.74 LOOP 1.75 + -- only process those candidates m and n, which are tied: 1.76 IF "matrix_b"["m"]["n"] ISNULL THEN 1.77 + -- start with beat-paths prior tie-breaking: 1.78 "matrix_t" := "matrix_p"; 1.79 + -- start with all links allowed: 1.80 "matrix_f" := array_fill(FALSE, ARRAY["dimension_v", "dimension_v"]); 1.81 LOOP 1.82 + -- determine (and forbid) that link that is the weakest link 1.83 + -- in both the best path from candidate m to candidate n and 1.84 + -- from candidate n to candidate m: 1.85 "i" := 1; 1.86 <<forbid_one_link>> 1.87 LOOP 1.88 @@ -4067,7 +4075,7 @@ 1.89 IF "matrix_d"["i"]["j"] = "matrix_t"["m"]["n"] THEN 1.90 "matrix_f"["i"]["j"] := TRUE; 1.91 -- exit for performance reasons, 1.92 - -- as only one link will be found: 1.93 + -- as exactly one link will be found: 1.94 EXIT forbid_one_link; 1.95 END IF; 1.96 END IF; 1.97 @@ -4075,10 +4083,11 @@ 1.98 "j" := "j" + 1; 1.99 END LOOP; 1.100 IF "i" = "dimension_v" THEN 1.101 - RAISE EXCEPTION 'Schulze tie-breaking does not compute (should not happen)'; 1.102 + RAISE EXCEPTION 'Did not find shared weakest link for tie-breaking (should not happen)'; 1.103 END IF; 1.104 "i" := "i" + 1; 1.105 END LOOP; 1.106 + -- calculate best beat-paths while ignoring forbidden links: 1.107 "i" := 1; 1.108 LOOP 1.109 "j" := 1; 1.110 @@ -4086,7 +4095,7 @@ 1.111 IF "i" != "j" THEN 1.112 "matrix_t"["i"]["j"] := CASE 1.113 WHEN "matrix_f"["i"]["j"] 1.114 - THEN (-1::INT8) << 63 1.115 + THEN (-1::INT8) << 63 -- worst possible value 1.116 ELSE "matrix_d"["i"]["j"] END; 1.117 END IF; 1.118 EXIT WHEN "j" = "dimension_v"; 1.119 @@ -4096,6 +4105,7 @@ 1.120 "i" := "i" + 1; 1.121 END LOOP; 1.122 "matrix_t" := "find_best_paths"("matrix_t"); 1.123 + -- extend partial order, if tie-breaking was successful: 1.124 IF "matrix_t"["m"]["n"] > "matrix_t"["n"]["m"] THEN 1.125 "matrix_b"["m"]["n"] := TRUE; 1.126 "matrix_b"["n"]["m"] := FALSE; 1.127 @@ -4114,11 +4124,12 @@ 1.128 "m" := "m" + 1; 1.129 END LOOP; 1.130 END IF; 1.131 - -- Determine order of winners: 1.132 + -- store a unique ranking in "rank_ary": 1.133 "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]); 1.134 "rank_v" := 1; 1.135 LOOP 1.136 "i" := 1; 1.137 + <<assign_next_rank>> 1.138 LOOP 1.139 IF "rank_ary"["i"] ISNULL THEN 1.140 "j" := 1; 1.141 @@ -4134,14 +4145,13 @@ 1.142 -- someone else is better 1.143 EXIT; 1.144 END IF; 1.145 - "j" := "j" + 1; 1.146 - IF "j" = "dimension_v" + 1 THEN 1.147 + IF "j" = "dimension_v" THEN 1.148 -- noone is better 1.149 "rank_ary"["i"] := "rank_v"; 1.150 - EXIT; 1.151 + EXIT assign_next_rank; 1.152 END IF; 1.153 + "j" := "j" + 1; 1.154 END LOOP; 1.155 - EXIT WHEN "j" = "dimension_v" + 1; 1.156 END IF; 1.157 "i" := "i" + 1; 1.158 IF "i" > "dimension_v" THEN