au-detect-edge.rs

/// Epistomological puzzle implemented in Rust.
/// 
/// There are two players in cooperative game. They are given a shared bipartite
/// graph and secretly assigned a vertex each. They need to determine if those
/// vertices are connected with an edge, and to that end players can exchange
/// their probability estimates. By Aumann's agreement theorem, they will agree
/// eventually.
/// 
/// Thought up and implemented by
/// (c) ProgramCrafter, 2025

#![feature(btree_extract_if)]
use std::collections::{BTreeSet, BTreeMap};
use std::marker::PhantomData;


#[derive(Debug)]
struct Bimap<A: Ord, B: Ord> {
    fwd: BTreeMap<A, BTreeSet<B>>,
    bck: BTreeMap<B, BTreeSet<A>>,
}
impl<A: Ord, B: Ord> Bimap<A, B> {
    fn new() -> Self {
        Self {fwd: BTreeMap::new(), bck: BTreeMap::new()}
    }
    fn connect(&mut self, i: A, j: B) where A: Clone, B: Clone {
        self.fwd.entry(i.clone())
                .or_insert(Default::default())
                .insert(j.clone());
        self.bck.entry(j.clone())
                .or_insert(Default::default())
                .insert(i.clone());
    }
    /*
    fn has(&self, i: &A, j: &B) -> bool {
        self.fwd.get(i)
                .map(|i_adj| i_adj.contains(j)).unwrap_or(false)
    }
    fn disconnect_left(&mut self, i: &A) {
        if let Some(i_adj) = self.fwd.remove(i) {
            for j in i_adj {
                self.bck.get_mut(&j).unwrap().remove(i);
            }
        }
    }
    fn disconnect_right(&mut self, j: &B) {
        if let Some(j_adj) = self.bck.remove(j) {
            for i in j_adj {
                self.fwd.get_mut(&i).unwrap().remove(j);
            }
        }
    }
    */
    fn extract_left(&mut self,
                    needs_drop: impl FnMut(&A, &mut BTreeSet<B>) -> bool) {
        for (i, i_adj) in self.fwd.extract_if(needs_drop) {
            for j in i_adj {
                self.bck.get_mut(&j).unwrap().remove(&i);
            }
        }
    }
    fn extract_right(&mut self,
                     needs_drop: impl FnMut(&B, &mut BTreeSet<A>) -> bool) {
        for (j, j_adj) in self.bck.extract_if(needs_drop) {
            for i in j_adj {
                self.fwd.get_mut(&i).unwrap().remove(&j);
            }
        }
    }
    fn degree_left(&self, i: &A) -> usize {
        self.fwd.get(i).map(|i_adj| i_adj.len()).unwrap_or(0)
    }
    fn degree_right(&self, j: &B) -> usize {
        self.bck.get(j).map(|j_adj| j_adj.len()).unwrap_or(0)
    }
    fn size_left(&self) -> usize {
        self.fwd.len()
    }
    fn size_right(&self) -> usize {
        self.bck.len()
    }
}

impl<A: Ord+Clone, B: Ord+Clone> From<&Vec<(A, B)>> for Bimap<A, B> {
    fn from(src: &Vec<(A, B)>) -> Self {
        let mut bim = Bimap::new();
        for (a, b) in src.iter().cloned() {
            bim.connect(a, b);
        }
        bim
    }
}

////////////////////////////////////

struct Bipartite {
    n: usize,
    m: usize,
    edges: Vec<(usize, usize)>
}

#[derive(Debug)]
struct Aumann<'bp> {
    sel_a: usize,
    sel_b: usize,
    edges: Bimap<usize, usize>,
    graph: PhantomData<&'bp Bipartite>,
}
impl<'bp> Aumann<'bp> {
    fn new(graph: &'bp Bipartite, sel_a: usize, sel_b: usize) -> Self {
        assert!(sel_a < graph.n);
        assert!(sel_b < graph.m);
        let edges = (&graph.edges).into();
        Self {
            sel_a,
            sel_b,
            edges,
            graph: PhantomData
        }
    }
    fn just_report_a(&self) -> f64 {
        let deg = self.edges.degree_left(&self.sel_a);
        let den = self.edges.size_right();
        (deg as f64) / (den as f64)
    }
    fn just_report_b(&self) -> f64 {
        let deg = self.edges.degree_right(&self.sel_b);
        let den = self.edges.size_left();
        (deg as f64) / (den as f64)
    }
    fn step_a(&mut self) -> f64 {
        let deg = self.edges.degree_left(&self.sel_a);
        let report = self.just_report_a();
        self.edges.extract_left(|_, i_adj| i_adj.len() != deg);
        report
    }
    fn step_b(&mut self) -> f64 {
        let deg = self.edges.degree_right(&self.sel_b);
        let report = self.just_report_b();
        self.edges.extract_right(|_, j_adj| j_adj.len() != deg);
        report
    }
}


fn main() {
    let bp = Bipartite {
        n: 7,
        m: 8,
        edges: vec![(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 4),
                    (1, 5), (2, 0), (2, 2), (2, 6), (3, 0), (3, 1),
                    (3, 2), (3, 3), (4, 0), (4, 1), (4, 2), (4, 3),
                    (5, 2), (5, 4), (5, 5), (6, 2), (6, 4), (6, 6),
                    (6, 7)]
    };
    let selected = (5, 4);
    let mut au = Aumann::new(&bp, selected.0, selected.1);
    
    let mut last_p_a = f64::NAN;
    let mut last_p_b = f64::NAN;
    while last_p_a != last_p_b {
        last_p_a = au.step_a();
        println!("Aumann | A reports {last_p_a:.7}");
        last_p_b = au.step_b();
        println!("Aumann | B reports {last_p_b:.7}");
    }
    
    println!("\nAgreed upon:  {last_p_a:.7}");
    
    let had = bp.edges.iter().position(|it| *it == selected).is_some();
    println!("Ground truth: {:.7}", had as u8 as f64);
}