1.1 --- a/core.sql	Tue Sep 25 13:54:24 2012 +0200
     1.2 +++ b/core.sql	Sat Sep 29 23:41:37 2012 +0200
     1.3 @@ -7,7 +7,7 @@
     1.4  BEGIN;
     1.5  
     1.6  CREATE VIEW "liquid_feedback_version" AS
     1.7 -  SELECT * FROM (VALUES ('2.1.0', 2, 1, 0))
     1.8 +  SELECT * FROM (VALUES ('2.2.0', 2, 2, 0))
     1.9    AS "subquery"("string", "major", "minor", "revision");
    1.10  
    1.11  
    1.12 @@ -329,6 +329,11 @@
    1.13  COMMENT ON COLUMN "session"."lang"              IS 'Language code of the selected language';
    1.14  
    1.15  
    1.16 +CREATE TYPE "schulze_variant" AS ENUM ('absolute_strength', 'tuple_strength', 'partial_tie_breaking', 'tie_breaking_with_negative_strength');
    1.17 +
    1.18 +COMMENT ON TYPE "schulze_variant" IS 'Variant of schulze method, which differ by complexity; greater values have a higher complexity';
    1.19 +
    1.20 +
    1.21  CREATE TABLE "policy" (
    1.22          "id"                    SERIAL4         PRIMARY KEY,
    1.23          "index"                 INT4            NOT NULL,
    1.24 @@ -356,6 +361,7 @@
    1.25          "indirect_majority_non_negative" INT4   NOT NULL DEFAULT 0,
    1.26          "no_reverse_beat_path"          BOOLEAN NOT NULL DEFAULT TRUE,
    1.27          "no_multistage_majority"        BOOLEAN NOT NULL DEFAULT FALSE,
    1.28 +        "schulze_variant"     "schulze_variant" NOT NULL DEFAULT 'tie_breaking_with_negative_strength',
    1.29          CONSTRAINT "timing" CHECK (
    1.30            ( "polling" = FALSE AND
    1.31              "admission_time" NOTNULL AND "discussion_time" NOTNULL AND
    1.32 @@ -671,13 +677,13 @@
    1.33  COMMENT ON COLUMN "initiative"."negative_votes"         IS 'Calculated from table "direct_voter"';
    1.34  COMMENT ON COLUMN "initiative"."direct_majority"        IS 'TRUE, if "positive_votes"/("positive_votes"+"negative_votes") is strictly greater or greater-equal than "direct_majority_num"/"direct_majority_den", and "positive_votes" is greater-equal than "direct_majority_positive", and ("positive_votes"+abstentions) is greater-equal than "direct_majority_non_negative"';
    1.35  COMMENT ON COLUMN "initiative"."indirect_majority"      IS 'Same as "direct_majority", but also considering indirect beat paths';
    1.36 -COMMENT ON COLUMN "initiative"."schulze_rank"           IS 'Schulze-Ranking without tie-breaking';
    1.37 -COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo (without tie-breaking)';
    1.38 -COMMENT ON COLUMN "initiative"."worse_than_status_quo"  IS 'TRUE, if initiative has a schulze-ranking worse than the status quo (without tie-breaking)';
    1.39 +COMMENT ON COLUMN "initiative"."schulze_rank"           IS 'Schulze-Ranking';
    1.40 +COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo';
    1.41 +COMMENT ON COLUMN "initiative"."worse_than_status_quo"  IS 'TRUE, if initiative has a schulze-ranking worse than the status quo';
    1.42  COMMENT ON COLUMN "initiative"."reverse_beat_path"      IS 'TRUE, if there is a beat path (may include ties) from this initiative to the status quo';
    1.43  COMMENT ON COLUMN "initiative"."multistage_majority"    IS 'TRUE, if either (a) this initiative has no better rank than the status quo, or (b) there exists a better ranked initiative X, which directly beats this initiative, and either more voters prefer X to this initiative than voters preferring X to the status quo or less voters prefer this initiative to X than voters preferring the status quo to X';
    1.44  COMMENT ON COLUMN "initiative"."eligible"               IS 'Initiative has a "direct_majority" and an "indirect_majority", is "better_than_status_quo" and depending on selected policy the initiative has no "reverse_beat_path" or "multistage_majority"';
    1.45 -COMMENT ON COLUMN "initiative"."winner"                 IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of ties with lowest "id"';
    1.46 +COMMENT ON COLUMN "initiative"."winner"                 IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of unresolved ties with lowest "id"';
    1.47  COMMENT ON COLUMN "initiative"."rank"                   IS 'Unique ranking for all "admitted" initiatives per issue; lower rank is better; a winner always has rank 1, but rank 1 does not imply that an initiative is winner; initiatives with "direct_majority" AND "indirect_majority" always have a better (lower) rank than other initiatives';
    1.48  
    1.49  
    1.50 @@ -3848,22 +3854,47 @@
    1.51    IS 'Closes the voting on an issue, and calculates positive and negative votes for each initiative; The ranking is not calculated yet, to keep the (locking) transaction short.';
    1.52  
    1.53  
    1.54 +CREATE FUNCTION "impossible_defeat_strength"()
    1.55 +  RETURNS INT8
    1.56 +  LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.57 +    BEGIN
    1.58 +      RETURN -1::INT8 << 63;
    1.59 +    END;
    1.60 +  $$;
    1.61 +
    1.62 +COMMENT ON FUNCTION "impossible_defeat_strength"() IS 'An INT8 value lower than any other value returned by function "defeat_strength"(INT4, INT4)';
    1.63 +
    1.64 +
    1.65  CREATE FUNCTION "defeat_strength"
    1.66 -  ( "positive_votes_p" INT4, "negative_votes_p" INT4 )
    1.67 +  ( "schulze_variant_p" "schulze_variant",
    1.68 +    "positive_votes_p" INT4,
    1.69 +    "negative_votes_p" INT4 )
    1.70    RETURNS INT8
    1.71    LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.72      BEGIN
    1.73 -      IF "positive_votes_p" > "negative_votes_p" THEN
    1.74 -        RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;
    1.75 -      ELSIF "positive_votes_p" = "negative_votes_p" THEN
    1.76 -        RETURN 0;
    1.77 +      IF "schulze_variant_p" >= 'tuple_strength'::"schulze_variant" THEN
    1.78 +        IF "positive_votes_p" > "negative_votes_p" THEN
    1.79 +          RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;
    1.80 +        ELSIF "positive_votes_p" = "negative_votes_p" THEN
    1.81 +          RETURN 0::INT8;
    1.82 +        ELSE
    1.83 +          IF "schulze_variant_p" >= 'tie_breaking_with_negative_strength'::"schulze_variant" THEN
    1.84 +            RETURN "positive_votes_p"::INT8 - ("negative_votes_p"::INT8 << 31);
    1.85 +          ELSE
    1.86 +            RETURN "impossible_defeat_strength"();
    1.87 +          END IF;
    1.88 +        END IF;
    1.89        ELSE
    1.90 -        RETURN -1;
    1.91 +        IF "positive_votes_p" > "negative_votes_p" THEN
    1.92 +          RETURN "positive_votes_p"::INT8;
    1.93 +        ELSE
    1.94 +          RETURN 0::INT8;
    1.95 +        END IF;
    1.96        END IF;
    1.97      END;
    1.98    $$;
    1.99  
   1.100 -COMMENT ON FUNCTION "defeat_strength"(INT4, INT4) IS 'Calculates defeat strength (INT8!) of a pairwise defeat primarily by the absolute number of votes for the winner and secondarily by the absolute number of votes for the loser';
   1.101 +COMMENT ON FUNCTION "defeat_strength"("schulze_variant", INT4, INT4) IS 'Calculates defeat strength (INT8!) of a pairwise defeat primarily by the absolute number of votes for the winner and secondarily by the absolute number of votes for the loser. A tie has a strength of zero.';
   1.102  
   1.103  
   1.104  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
   1.105 @@ -3873,11 +3904,17 @@
   1.106        "issue_row"         "issue"%ROWTYPE;
   1.107        "policy_row"        "policy"%ROWTYPE;
   1.108        "dimension_v"       INTEGER;
   1.109 -      "vote_matrix"       INT4[][];  -- absolute votes
   1.110 -      "matrix"            INT8[][];  -- defeat strength / best paths
   1.111 +      "vote_matrix"       INT4[][];     -- absolute votes
   1.112 +      "direct_matrix"     INT8[][];     -- direct defeat strength
   1.113 +      "path_matrix"       INT8[][];     -- defeat strength of best path
   1.114 +      "compare_matrix"    BOOLEAN[][];  -- binary relation to create schulze-rank
   1.115 +      "forbidden_matrix"  BOOLEAN[][];  -- forbidden links for tie-breaking
   1.116 +      "modified_matrix"   INT8[][];     -- defeat strength after tie-breaking
   1.117        "i"                 INTEGER;
   1.118        "j"                 INTEGER;
   1.119        "k"                 INTEGER;
   1.120 +      "m"                 INTEGER;
   1.121 +      "n"                 INTEGER;
   1.122        "battle_row"        "battle"%ROWTYPE;
   1.123        "rank_ary"          INT4[];
   1.124        "rank_v"            INT4;
   1.125 @@ -3917,15 +3954,16 @@
   1.126        IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN
   1.127          RAISE EXCEPTION 'Wrong battle count (should not happen)';
   1.128        END IF;
   1.129 -      -- Store defeat strengths in "matrix" using "defeat_strength"
   1.130 +      -- Store defeat strengths in "path_matrix" using "defeat_strength"
   1.131        -- function:
   1.132 -      "matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.133 +      "direct_matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.134        "i" := 1;
   1.135        LOOP
   1.136          "j" := 1;
   1.137          LOOP
   1.138            IF "i" != "j" THEN
   1.139 -            "matrix"["i"]["j"] := "defeat_strength"(
   1.140 +            "direct_matrix"["i"]["j"] := "defeat_strength"(
   1.141 +              "policy_row"."schulze_variant",
   1.142                "vote_matrix"["i"]["j"],
   1.143                "vote_matrix"["j"]["i"]
   1.144              );
   1.145 @@ -3937,6 +3975,7 @@
   1.146          "i" := "i" + 1;
   1.147        END LOOP;
   1.148        -- Find best paths:
   1.149 +      "path_matrix" := "direct_matrix";
   1.150        "i" := 1;
   1.151        LOOP
   1.152          "j" := 1;
   1.153 @@ -3945,13 +3984,13 @@
   1.154              "k" := 1;
   1.155              LOOP
   1.156                IF "i" != "k" AND "j" != "k" THEN
   1.157 -                IF "matrix"["j"]["i"] < "matrix"["i"]["k"] THEN
   1.158 -                  IF "matrix"["j"]["i"] > "matrix"["j"]["k"] THEN
   1.159 -                    "matrix"["j"]["k"] := "matrix"["j"]["i"];
   1.160 +                IF "path_matrix"["j"]["i"] < "path_matrix"["i"]["k"] THEN
   1.161 +                  IF "path_matrix"["j"]["i"] > "path_matrix"["j"]["k"] THEN
   1.162 +                    "path_matrix"["j"]["k"] := "path_matrix"["j"]["i"];
   1.163                    END IF;
   1.164                  ELSE
   1.165 -                  IF "matrix"["i"]["k"] > "matrix"["j"]["k"] THEN
   1.166 -                    "matrix"["j"]["k"] := "matrix"["i"]["k"];
   1.167 +                  IF "path_matrix"["i"]["k"] > "path_matrix"["j"]["k"] THEN
   1.168 +                    "path_matrix"["j"]["k"] := "path_matrix"["i"]["k"];
   1.169                    END IF;
   1.170                  END IF;
   1.171                END IF;
   1.172 @@ -3965,6 +4004,131 @@
   1.173          EXIT WHEN "i" = "dimension_v";
   1.174          "i" := "i" + 1;
   1.175        END LOOP;
   1.176 +      -- initial calculation of binary relation:
   1.177 +      "compare_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
   1.178 +      "i" := 1;
   1.179 +      LOOP
   1.180 +        "j" := 1;
   1.181 +        LOOP
   1.182 +          IF "i" != "j" THEN
   1.183 +            IF "path_matrix"["i"]["j"] > "path_matrix"["j"]["i"] THEN
   1.184 +              "compare_matrix"["i"]["j"] = TRUE;
   1.185 +              "compare_matrix"["j"]["i"] = FALSE;
   1.186 +            ELSIF "path_matrix"["i"]["j"] < "path_matrix"["j"]["i"] THEN
   1.187 +              "compare_matrix"["i"]["j"] = FALSE;
   1.188 +              "compare_matrix"["j"]["i"] = TRUE;
   1.189 +            END IF;
   1.190 +          END IF;
   1.191 +          EXIT WHEN "j" = "dimension_v";
   1.192 +          "j" := "j" + 1;
   1.193 +        END LOOP;
   1.194 +        EXIT WHEN "i" = "dimension_v";
   1.195 +        "i" := "i" + 1;
   1.196 +      END LOOP;
   1.197 +      -- tie-breaking:
   1.198 +      IF "policy_row"."schulze_variant" >= 'partial_tie_breaking'::"schulze_variant" THEN
   1.199 +        "modified_matrix"  := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
   1.200 +        "forbidden_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
   1.201 +        "m" := 1;
   1.202 +        LOOP
   1.203 +          "n" := "m" + 1;
   1.204 +          LOOP
   1.205 +            IF "compare_matrix"["m"]["n"] ISNULL THEN
   1.206 +              "i" := 1;
   1.207 +              LOOP
   1.208 +                "j" := 1;
   1.209 +                LOOP
   1.210 +                  IF "i" != "j" THEN
   1.211 +                    "forbidden_matrix"["i"]["j"] := FALSE;
   1.212 +                    "modified_matrix"["i"]["j"] := "path_matrix"["i"]["j"];
   1.213 +                  END IF;
   1.214 +                  EXIT WHEN "j" = "dimension_v";
   1.215 +                  "j" := "j" + 1;
   1.216 +                END LOOP;
   1.217 +                EXIT WHEN "i" = "dimension_v";
   1.218 +                "i" := "i" + 1;
   1.219 +              END LOOP;
   1.220 +              LOOP
   1.221 +                "i" := 1;
   1.222 +                LOOP
   1.223 +                  "j" := 1;
   1.224 +                  LOOP
   1.225 +                    IF "i" != "j" THEN
   1.226 +                      IF "modified_matrix"["m"]["n"] = "direct_matrix"["i"]["j"] THEN
   1.227 +                        "forbidden_matrix"["i"]["j"] := TRUE;
   1.228 +                      END IF;
   1.229 +                    END IF;
   1.230 +                    EXIT WHEN "j" = "dimension_v";
   1.231 +                    "j" := "j" + 1;
   1.232 +                  END LOOP;
   1.233 +                  EXIT WHEN "i" = "dimension_v";
   1.234 +                  "i" := "i" + 1;
   1.235 +                END LOOP;
   1.236 +                "i" := 1;
   1.237 +                LOOP
   1.238 +                  "j" := 1;
   1.239 +                  LOOP
   1.240 +                    IF "i" != "j" THEN
   1.241 +                      IF "forbidden_matrix"["i"]["j"] THEN
   1.242 +                        "modified_matrix"["i"]["j"] := "impossible_defeat_strength"();
   1.243 +                      ELSE
   1.244 +                        "modified_matrix"["i"]["j"] := "direct_matrix"["i"]["j"];
   1.245 +                      END IF;
   1.246 +                    END IF;
   1.247 +                    EXIT WHEN "j" = "dimension_v";
   1.248 +                    "j" := "j" + 1;
   1.249 +                  END LOOP;
   1.250 +                  EXIT WHEN "i" = "dimension_v";
   1.251 +                  "i" := "i" + 1;
   1.252 +                END LOOP;
   1.253 +                "i" := 1;
   1.254 +                LOOP
   1.255 +                  "j" := 1;
   1.256 +                  LOOP
   1.257 +                    IF "i" != "j" THEN
   1.258 +                      "k" := 1;
   1.259 +                      LOOP
   1.260 +                        IF "i" != "k" AND "j" != "k" THEN
   1.261 +                          IF "modified_matrix"["j"]["i"] < "modified_matrix"["i"]["k"] THEN
   1.262 +                            IF "modified_matrix"["j"]["i"] > "modified_matrix"["j"]["k"] THEN
   1.263 +                              "modified_matrix"["j"]["k"] := "modified_matrix"["j"]["i"];
   1.264 +                            END IF;
   1.265 +                          ELSE
   1.266 +                            IF "modified_matrix"["i"]["k"] > "modified_matrix"["j"]["k"] THEN
   1.267 +                              "modified_matrix"["j"]["k"] := "modified_matrix"["i"]["k"];
   1.268 +                            END IF;
   1.269 +                          END IF;
   1.270 +                        END IF;
   1.271 +                        EXIT WHEN "k" = "dimension_v";
   1.272 +                        "k" := "k" + 1;
   1.273 +                      END LOOP;
   1.274 +                    END IF;
   1.275 +                    EXIT WHEN "j" = "dimension_v";
   1.276 +                    "j" := "j" + 1;
   1.277 +                  END LOOP;
   1.278 +                  EXIT WHEN "i" = "dimension_v";
   1.279 +                  "i" := "i" + 1;
   1.280 +                END LOOP;
   1.281 +                IF "modified_matrix"["m"]["n"] > "modified_matrix"["n"]["m"] THEN
   1.282 +                  "compare_matrix"["m"]["n"] := TRUE;
   1.283 +                  "compare_matrix"["n"]["m"] := FALSE;
   1.284 +                  EXIT;
   1.285 +                ELSIF "modified_matrix"["m"]["n"] < "modified_matrix"["n"]["m"] THEN
   1.286 +                  "compare_matrix"["m"]["n"] := FALSE;
   1.287 +                  "compare_matrix"["n"]["m"] := TRUE;
   1.288 +                  EXIT;
   1.289 +                ELSIF "modified_matrix"["m"]["n"] = "impossible_defeat_strength"() THEN
   1.290 +                  EXIT;
   1.291 +                END IF;
   1.292 +              END LOOP;
   1.293 +            END IF;
   1.294 +            EXIT WHEN "n" = "dimension_v";
   1.295 +            "n" := "n" + 1;
   1.296 +          END LOOP;
   1.297 +          EXIT WHEN "m" = "dimension_v" - 1;
   1.298 +          "m" := "m" + 1;
   1.299 +        END LOOP;
   1.300 +      END IF;
   1.301        -- Determine order of winners:
   1.302        "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]);
   1.303        "rank_v" := 1;
   1.304 @@ -3979,7 +4143,7 @@
   1.305                IF
   1.306                  "i" != "j" AND
   1.307                  "rank_ary"["j"] ISNULL AND
   1.308 -                "matrix"["j"]["i"] > "matrix"["i"]["j"]
   1.309 +                "compare_matrix"["j"]["i"]
   1.310                THEN
   1.311                  -- someone else is better
   1.312                  EXIT;
   1.313 @@ -4039,7 +4203,7 @@
   1.314            "better_than_status_quo" = "rank_ary"["i"] < "rank_ary"["dimension_v"],
   1.315            "worse_than_status_quo"  = "rank_ary"["i"] > "rank_ary"["dimension_v"],
   1.316            "multistage_majority"    = "rank_ary"["i"] >= "rank_ary"["dimension_v"],
   1.317 -          "reverse_beat_path"      = "matrix"["dimension_v"]["i"] >= 0,
   1.318 +          "reverse_beat_path"      = "path_matrix"["dimension_v"]["i"] >= 0,
   1.319            "eligible"               = FALSE,
   1.320            "winner"                 = FALSE,
   1.321            "rank"                   = NULL  -- NOTE: in cases of manual reset of issue state