diff --git a/server/src/ranking.rs b/server/src/ranking.rs index 3710c9f64437f5bef3b2121905b6f3bcb7611047..38e6d09b4370e5f8cbae09c0e5760b4e7f1ef7db 100644 --- a/server/src/ranking.rs +++ b/server/src/ranking.rs @@ -1,4 +1,4 @@ -use std::collections::HashMap; +use std::collections::{HashMap, HashSet}; use crate::path_types::ItemId; use crate::reducer::GroupState; @@ -143,23 +143,35 @@ fn compute_scores_from_edges(n: usize, edges: impl Iterator 0 for every non-maximum-degree node, and for max-degree + // nodes whenever any neighbor weight is below 1 (i.e. not a unanimous + // loss). Without this, regular comparison graphs (e.g. a pure star at + // ratio 2:1) produce a bipartite chain that oscillates instead of + // converging — see issue #146. let mut out_edges: Vec> = vec![Vec::new(); n]; - let mut out_deg: Vec = vec![0.0; n]; + let mut neighbors: Vec> = vec![HashSet::new(); n]; for ((src, dst), w) in &normalized { out_edges[*src].push((*dst, *w)); - out_deg[*src] += w; + neighbors[*src].insert(*dst); + neighbors[*dst].insert(*src); } - let mut max_out = 0.0f64; - for &d in &out_deg { - if d > max_out { - max_out = d; - } - } - if max_out <= 1e-12 { + let weight_sum: Vec = out_edges + .iter() + .map(|es| es.iter().map(|(_, w)| *w).sum()) + .collect(); + let d_max = neighbors.iter().map(|s| s.len()).max().unwrap_or(0); + if d_max == 0 { return vec![1.0 / n as f64; n]; } + let d_max_f = d_max as f64; let mut scores = vec![1.0 / n as f64; n]; let mut next = vec![0.0f64; n]; @@ -167,14 +179,14 @@ fn compute_scores_from_edges(n: usize, edges: impl Iterator` ratio (2:1). + /// Under the old (sum-of-weights) divisor every node had P_ii = 0 and the + /// chain was bipartite; power iteration oscillated and returned the + /// uniform initial distribution after an even number of steps. Using the + /// paper's degree-based d_max gives every node a positive self-loop and + /// the chain converges to the correct stationary distribution. + #[test] + fn star_topology_winner_at_top_via_subset() { + let mut g = mk_group(); + g.apply_vote(vote(1, "zebra", "alpha", 2, 1)); + g.apply_vote(vote(2, "zebra", "beta", 2, 1)); + + let mut items: Vec<(usize, String)> = g + .idx_to_item + .iter() + .enumerate() + .map(|(i, it)| (i, it.as_str().to_string())) + .collect(); + items.sort_by(|a, b| a.1.cmp(&b.1)); + let idxs: Vec = items.iter().map(|(i, _)| *i).collect(); + + let ranked = ranked_items_subset(&g, &idxs, 10000, 1e-8); + for r in &ranked { + eprintln!("{}: {}", r.item.as_str(), r.score); + } + assert_eq!( + ranked[0].item.as_str(), + "https://slug.social/zebra", + "zebra won both votes and should rank #1" + ); + } + #[test] fn group_ranking_cache_dirty_flow() { let mut g = mk_group(); diff --git a/test/fixtures/ranking/chain.sorter b/test/fixtures/ranking/chain.sorter new file mode 100644 index 0000000000000000000000000000000000000000..912a96bdc08f631be27f3c9afc7e05004a2457c0 --- /dev/null +++ b/test/fixtures/ranking/chain.sorter @@ -0,0 +1,10 @@ +#t3 + +~/t3/a { head of chain } +~/t3/b { middle } +~/t3/c { tail } + +{ a > b } +~/t3/a > ~/t3/b +{ b > c } +~/t3/b > ~/t3/c diff --git a/test/fixtures/ranking/cycle.sorter b/test/fixtures/ranking/cycle.sorter new file mode 100644 index 0000000000000000000000000000000000000000..771731ae176e5d77e00ab89767ff2d7465bb7c6b --- /dev/null +++ b/test/fixtures/ranking/cycle.sorter @@ -0,0 +1,12 @@ +#t4 + +~/t4/a { node a } +~/t4/b { node b } +~/t4/c { node c } + +{ a > b } +~/t4/a > ~/t4/b +{ b > c } +~/t4/b > ~/t4/c +{ c > a } +~/t4/c > ~/t4/a diff --git a/test/fixtures/ranking/star.sorter b/test/fixtures/ranking/star.sorter new file mode 100644 index 0000000000000000000000000000000000000000..135c9f9097d57b73c7ab18fac737ed3598d76fbe --- /dev/null +++ b/test/fixtures/ranking/star.sorter @@ -0,0 +1,11 @@ +#repro + +~/repro/zebra { winner — beats both others } +~/repro/alpha { loser — alphabetically first } +~/repro/beta { loser — alphabetically middle } + +{ zebra beats alpha } +~/repro/zebra > ~/repro/alpha + +{ zebra beats beta } +~/repro/zebra > ~/repro/beta diff --git a/test/fixtures/ranking/star_inverse.sorter b/test/fixtures/ranking/star_inverse.sorter new file mode 100644 index 0000000000000000000000000000000000000000..dab842fa924e5124865ee216b9565f6c7471c812 --- /dev/null +++ b/test/fixtures/ranking/star_inverse.sorter @@ -0,0 +1,11 @@ +#t2 + +~/t2/win { source of incoming edges (loses both) } +~/t2/loss-a { winner } +~/t2/loss-b { winner } + +{ loss-a beats win } +~/t2/loss-a > ~/t2/win + +{ loss-b beats win } +~/t2/loss-b > ~/t2/win diff --git a/test/ranking.clj b/test/ranking.clj new file mode 100644 index 0000000000000000000000000000000000000000..e1358783a84a264ee633bd79151ba29750b717cf --- /dev/null +++ b/test/ranking.clj @@ -0,0 +1,74 @@ +(ns test.ranking + "Drives sorterc on .sorter fixtures and asserts ranking properties. + + Regression coverage for issue #146 — pure forward star at default ratio + (2:1 for `>`) used to produce tied uniform scores because the random walk + on the normalized edge weights was bipartite. Fixed by switching to the + degree-based d_max from Negahban–Oh–Shah rank centrality (§3.1)." + (:require [clojure.test :refer [deftest is testing]] + [babashka.process :as p] + [cheshire.core :as json] + [clojure.java.io :as io])) + +(def sorterc-bin + "Path to the locally-built sorterc binary. Builds on demand if missing." + (let [dbg "target/debug/sorterc" + release "target/release/sorterc"] + (cond + (.exists (io/file release)) release + (.exists (io/file dbg)) dbg + :else + (do (println "building sorterc…") + (let [r (p/shell {:out :string :err :string :continue true} + "cargo build -p sorterc")] + (when-not (zero? (:exit r)) + (throw (ex-info "cargo build -p sorterc failed" + {:stderr (:err r)})))) + dbg)))) + +(defn compile-sorter [fixture-path] + (let [{:keys [out exit]} (p/shell {:out :string :err :string :continue true} + sorterc-bin "compile" fixture-path)] + (when-not (zero? exit) + (throw (ex-info "sorterc exit nonzero" {:fixture fixture-path :out out}))) + (json/parse-string out true))) + +(defn first-component-ranking [result] + (-> result :rankings first :components first :ranking)) + +(defn item-leaf [item] + (last (clojure.string/split item #"/"))) + +(deftest chain-ranks-head-first + (let [ranking (first-component-ranking (compile-sorter "test/fixtures/ranking/chain.sorter")) + names (mapv (comp item-leaf :item) ranking)] + (is (= ["a" "b" "c"] names) + "chain a>b>c should rank a, b, c in order") + (is (apply > (map :score ranking)) + "scores should attenuate strictly down the chain"))) + +(deftest inverse-star-puts-winners-on-top + (let [ranking (first-component-ranking (compile-sorter "test/fixtures/ranking/star_inverse.sorter")) + names (mapv (comp item-leaf :item) ranking)] + (is (= "win" (last names)) + "the item that lost to both others should be ranked last"))) + +(deftest cycle-produces-uniform-scores + (let [ranking (first-component-ranking (compile-sorter "test/fixtures/ranking/cycle.sorter")) + scores (map :score ranking)] + (is (every? #(< (Math/abs (- % 1/3)) 1e-3) scores) + "a perfectly symmetric 3-cycle should give every node ~1/3"))) + +(deftest star-topology-winner-at-top + ;; Issue #146 regression: source-only star at default `>` ratio (2:1). + ;; Pre-fix produced uniform 1/3 scores; alphabetical fallback put the + ;; unambiguous winner at the bottom. Post-fix the chain is aperiodic and + ;; converges to π_zebra = 1/2, π_alpha = π_beta = 1/4. + (let [ranking (first-component-ranking (compile-sorter "test/fixtures/ranking/star.sorter")) + names (mapv (comp item-leaf :item) ranking) + by-name (into {} (map (juxt (comp item-leaf :item) :score) ranking))] + (is (= "zebra" (first names)) + "zebra won both votes and should rank #1") + (is (< (Math/abs (- (by-name "zebra") 0.5)) 1e-3)) + (is (< (Math/abs (- (by-name "alpha") 0.25)) 1e-3)) + (is (< (Math/abs (- (by-name "beta") 0.25)) 1e-3))))