car-topology 0.55.0

//! Directed communication topologies over a fixed-size agent team.
//!
//! A topology is a directed adjacency matrix `A ∈ {0,1}^{N×N}` without
//! self-loops, where `A[i][j] = 1` routes agent `i`'s output into agent `j`'s
//! context. A decision node outside the matrix aggregates the final answers,
//! so a topology with no edges is still a valid team — `N` agents answering
//! independently.
//!
//! The matrix is stored as the flattened off-diagonal vector `vec(A)` of length
//! `N(N-1)` in row-major order, skipping `i == j`. That is the representation
//! the codebook quantizes and the proxy reads, so keeping it as the storage
//! form means no conversion sits between the two.

use serde::{Deserialize, Serialize};

use crate::error::TopologyError;

/// A directed, self-loop-free communication topology over `n` agents.
///
/// Equality and [`Topology::key`] are structural: two topologies with the same
/// `n` and the same edge set are the same topology, whatever built them.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(try_from = "TopologyWire")]
pub struct Topology {
    n: usize,
    /// Off-diagonal entries in row-major order, length `n * (n - 1)`.
    edges: Vec<bool>,
}

/// The on-disk shape of a [`Topology`], deserialized through
/// [`Topology::from_flat`] so the length invariant cannot be bypassed.
///
/// Without this, a *well-formed* JSON line whose `edges` array is the wrong
/// length produces a `Topology` that every constructor would have rejected, and
/// the first [`Topology::edge`] read panics on an out-of-bounds index. The
/// journal is a plain JSONL file on disk that a person can edit, and its
/// torn-line tolerance does not help here: the line parses, it is simply
/// inconsistent. Validating at the serde boundary turns that into a skipped
/// line, which is what the journal already does with anything it cannot read.
#[derive(Deserialize)]
struct TopologyWire {
    n: usize,
    edges: Vec<bool>,
}

impl TryFrom<TopologyWire> for Topology {
    type Error = TopologyError;

    fn try_from(wire: TopologyWire) -> Result<Self, Self::Error> {
        Topology::from_flat(wire.n, wire.edges)
    }
}

impl Topology {
    /// The empty topology over `n` agents: every agent answers independently
    /// and only the decision node sees the results.
    ///
    /// Returns [`TopologyError::TeamTooSmall`] below two agents — a one-agent
    /// team has no adjacency space to search, so it is a degenerate input to
    /// every stage of the pipeline rather than a topology to represent.
    pub fn empty(n: usize) -> Result<Self, TopologyError> {
        if n < 2 {
            return Err(TopologyError::TeamTooSmall { n });
        }
        Ok(Self {
            n,
            edges: vec![false; n * (n - 1)],
        })
    }

    /// Build from a full `n × n` boolean matrix. Diagonal entries are ignored
    /// rather than rejected: callers routinely hand in a matrix whose diagonal
    /// is whatever their generator left there, and a self-loop has no meaning
    /// in this representation.
    pub fn from_matrix(matrix: &[Vec<bool>]) -> Result<Self, TopologyError> {
        let n = matrix.len();
        let mut topology = Self::empty(n)?;
        for (i, row) in matrix.iter().enumerate() {
            if row.len() != n {
                return Err(TopologyError::NotSquare {
                    rows: n,
                    row_len: row.len(),
                });
            }
            for (j, &on) in row.iter().enumerate() {
                if i != j && on {
                    topology.set_edge(i, j, true)?;
                }
            }
        }
        Ok(topology)
    }

    /// Build directly from a flattened off-diagonal vector of length `n(n-1)`.
    pub fn from_flat(n: usize, edges: Vec<bool>) -> Result<Self, TopologyError> {
        if n < 2 {
            return Err(TopologyError::TeamTooSmall { n });
        }
        let expected = n * (n - 1);
        if edges.len() != expected {
            return Err(TopologyError::FlatLength {
                expected,
                found: edges.len(),
            });
        }
        Ok(Self { n, edges })
    }

    /// Number of agents in the team.
    pub fn n(&self) -> usize {
        self.n
    }

    /// The flattened off-diagonal vector `vec(A)`.
    pub fn flat(&self) -> &[bool] {
        &self.edges
    }

    /// Index of `(i, j)` within [`Topology::flat`], or `None` for the diagonal
    /// and out-of-range pairs.
    fn flat_index(&self, i: usize, j: usize) -> Option<usize> {
        if i >= self.n || j >= self.n || i == j {
            return None;
        }
        // Row `i` contributes `n - 1` entries; within it, `j` shifts down by one
        // once it passes the skipped diagonal entry.
        let within = if j < i { j } else { j - 1 };
        Some(i * (self.n - 1) + within)
    }

    /// Whether agent `i`'s output is routed into agent `j`.
    pub fn edge(&self, i: usize, j: usize) -> bool {
        self.flat_index(i, j)
            .map(|k| self.edges[k])
            .unwrap_or(false)
    }

    /// Set or clear the `i → j` edge. Rejects self-loops and out-of-range
    /// indices; a silently-dropped edge would make two callers disagree about
    /// what topology they built.
    pub fn set_edge(&mut self, i: usize, j: usize, on: bool) -> Result<(), TopologyError> {
        let idx = self
            .flat_index(i, j)
            .ok_or(TopologyError::BadEdge { i, j, n: self.n })?;
        self.edges[idx] = on;
        Ok(())
    }

    /// `|E|` — the number of directed edges.
    ///
    /// This is the structural cost surrogate the published designers minimize.
    /// [`crate::diagnostics::edge_count_token_correlation`] is the reason CAR
    /// does not: on the paper's records `|E|` correlates with measured tokens
    /// at `r ≈ -0.4`, so minimizing it maximizes the bill.
    pub fn edge_count(&self) -> usize {
        self.edges.iter().filter(|&&e| e).count()
    }

    /// Edge density in `[0, 1]` — `|E| / N(N-1)`.
    pub fn density(&self) -> f32 {
        if self.edges.is_empty() {
            return 0.0;
        }
        self.edge_count() as f32 / self.edges.len() as f32
    }

    /// Hamming distance to another topology of the same size — the metric the
    /// codebook quantizes under.
    pub fn hamming(&self, other: &Topology) -> Result<usize, TopologyError> {
        if self.n != other.n {
            return Err(TopologyError::SizeMismatch {
                expected: self.n,
                found: other.n,
            });
        }
        Ok(self
            .edges
            .iter()
            .zip(other.edges.iter())
            .filter(|(a, b)| a != b)
            .count())
    }

    /// Stable structural key: `"<n>:<bitstring>"`. Sorting by this key gives a
    /// total order that does not depend on insertion order, which is what makes
    /// codebook fitting reproducible across runs.
    pub fn key(&self) -> String {
        let mut s = String::with_capacity(self.edges.len() + 4);
        s.push_str(&self.n.to_string());
        s.push(':');
        for &e in &self.edges {
            s.push(if e { '1' } else { '0' });
        }
        s
    }

    // --- The fixed families used for record collection -------------------
    //
    // The paper's collection protocol executes each training task under six
    // fixed topologies — complete, chain, star, and three Erdős–Rényi samples.
    // These constructors are that protocol, so a CAR operator collecting their
    // own records covers the same span of the adjacency space.

    /// Fully connected: every agent sees every other agent's output.
    pub fn complete(n: usize) -> Result<Self, TopologyError> {
        let mut t = Self::empty(n)?;
        for i in 0..n {
            for j in 0..n {
                if i != j {
                    t.set_edge(i, j, true)?;
                }
            }
        }
        Ok(t)
    }

    /// Linear chain `0 → 1 → … → n-1`.
    ///
    /// Sparsest connected family, and — measured, not assumed — the most
    /// token-expensive one on every math-format benchmark in the paper. It is
    /// the positive control for the inverted cost surrogate.
    pub fn chain(n: usize) -> Result<Self, TopologyError> {
        let mut t = Self::empty(n)?;
        for i in 0..n.saturating_sub(1) {
            t.set_edge(i, i + 1, true)?;
        }
        Ok(t)
    }

    /// Star with agent `hub` at the centre: every other agent feeds the hub and
    /// reads back from it.
    pub fn star(n: usize, hub: usize) -> Result<Self, TopologyError> {
        let mut t = Self::empty(n)?;
        if hub >= n {
            return Err(TopologyError::BadEdge { i: hub, j: hub, n });
        }
        debug_assert!(n >= 2, "empty() rejects a smaller team");
        for i in 0..n {
            if i != hub {
                t.set_edge(i, hub, true)?;
                t.set_edge(hub, i, true)?;
            }
        }
        Ok(t)
    }

    /// Erdős–Rényi sample at edge probability `p`, drawn from a deterministic
    /// 64-bit LCG seeded by `seed`.
    ///
    /// Deterministic on purpose: record collection costs real LLM calls, so the
    /// families a run was collected under must be reconstructible from the seed
    /// alone rather than re-sampled and quietly different.
    pub fn erdos_renyi(n: usize, p: f32, seed: u64) -> Result<Self, TopologyError> {
        let mut t = Self::empty(n)?;
        let p = p.clamp(0.0, 1.0);
        let mut state = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
        for i in 0..n {
            for j in 0..n {
                if i == j {
                    continue;
                }
                state = state
                    .wrapping_mul(6_364_136_223_846_793_005)
                    .wrapping_add(1_442_695_040_888_963_407);
                let draw = ((state >> 11) as f64 / (1u64 << 53) as f64) as f32;
                if draw < p {
                    t.set_edge(i, j, true)?;
                }
            }
        }
        Ok(t)
    }

    /// The six-topology collection protocol: complete, chain, star (hub 0), and
    /// three Erdős–Rényi samples at p = 0.3 / 0.5 / 0.7.
    ///
    /// Execute every training task under all six and log
    /// [`crate::ExecutionRecord`] for each pair; that is the whole training
    /// input, and nothing downstream calls a model again.
    pub fn collection_protocol(n: usize) -> Result<Vec<Self>, TopologyError> {
        Ok(vec![
            Self::complete(n)?,
            Self::chain(n)?,
            Self::star(n, 0)?,
            Self::erdos_renyi(n, 0.3, 1)?,
            Self::erdos_renyi(n, 0.5, 2)?,
            Self::erdos_renyi(n, 0.7, 3)?,
        ])
    }
}

/// CAR's coordination patterns, expressed as topologies.
///
/// The paper's claim that the useful design space is a short list is, for CAR,
/// not a finding to reproduce but the shape of the existing API: `car-multi`
/// already ships a fixed set of coordination patterns and
/// `car_agents::coordinator::Pattern` already picks among four of them. This
/// enum is the bridge — it gives the selector an output a `car-multi` caller
/// can actually execute, instead of an adjacency matrix nothing consumes.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum CoordinationShape {
    /// One agent, no routing. Agent `0` answers; the rest are unused.
    Solo,
    /// Sequential chain — each agent's output feeds the next.
    Pipeline,
    /// Parallel independent answers, aggregated by the decision node.
    Swarm,
    /// Debate — every agent sees every other agent's output.
    Debate,
    /// Workers feed a reviewer (the last agent), who feeds back to them.
    Supervisor,
}

impl CoordinationShape {
    /// Every shape, in a fixed order. Used to label a selected topology and to
    /// seed a codebook when an operator has no execution records yet.
    pub const ALL: [CoordinationShape; 5] = [
        CoordinationShape::Solo,
        CoordinationShape::Pipeline,
        CoordinationShape::Swarm,
        CoordinationShape::Debate,
        CoordinationShape::Supervisor,
    ];

    /// The topology this shape induces over an `n`-agent team.
    pub fn topology(self, n: usize) -> Result<Topology, TopologyError> {
        match self {
            // Solo and Swarm share the empty adjacency: both route nothing
            // between agents. They differ in how many agents the caller starts,
            // which is a team-size decision, not a topology one — so
            // `shape_of` can never recover Solo from a matrix, and says so.
            CoordinationShape::Solo | CoordinationShape::Swarm => Topology::empty(n),
            CoordinationShape::Pipeline => Topology::chain(n),
            CoordinationShape::Debate => Topology::complete(n),
            // `n - 1` must not be computed before the team-size guard: at
            // n = 0 it underflows, which panics in debug and silently wraps to
            // usize::MAX in release — two different behaviours for the same
            // degenerate input, neither of them `TeamTooSmall`.
            CoordinationShape::Supervisor => {
                if n < 2 {
                    return Err(TopologyError::TeamTooSmall { n });
                }
                Topology::star(n, n - 1)
            }
        }
    }

    /// Name used in serialized records and diagnostics.
    pub fn as_str(self) -> &'static str {
        match self {
            CoordinationShape::Solo => "solo",
            CoordinationShape::Pipeline => "pipeline",
            CoordinationShape::Swarm => "swarm",
            CoordinationShape::Debate => "debate",
            CoordinationShape::Supervisor => "supervisor",
        }
    }
}

/// The shape a topology corresponds to, when it corresponds to one.
///
/// Returns `Swarm` — never `Solo` — for the empty adjacency, because the two
/// are the same matrix and only the caller's team size separates them.
/// Topologies the codebook learned from real records frequently match no shape
/// at all; that is the case worth reporting honestly rather than rounding to
/// the nearest family.
pub fn shape_of(topology: &Topology) -> Option<CoordinationShape> {
    for shape in CoordinationShape::ALL {
        if shape == CoordinationShape::Solo {
            continue;
        }
        if let Ok(candidate) = shape.topology(topology.n()) {
            if &candidate == topology {
                return Some(shape);
            }
        }
    }
    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn flat_index_round_trips_every_pair() {
        let n = 5;
        let mut t = Topology::empty(n).unwrap();
        for i in 0..n {
            for j in 0..n {
                if i == j {
                    continue;
                }
                t.set_edge(i, j, true).unwrap();
                assert!(t.edge(i, j), "edge {i}->{j} did not read back");
                t.set_edge(i, j, false).unwrap();
                assert!(!t.edge(i, j));
            }
        }
        assert_eq!(t.edge_count(), 0);
    }

    #[test]
    fn flat_index_is_injective() {
        let n = 6;
        let t = Topology::empty(n).unwrap();
        let mut seen = vec![false; n * (n - 1)];
        for i in 0..n {
            for j in 0..n {
                if i == j {
                    continue;
                }
                let idx = t.flat_index(i, j).unwrap();
                assert!(!seen[idx], "index {idx} reused by {i}->{j}");
                seen[idx] = true;
            }
        }
        assert!(seen.iter().all(|&s| s));
    }

    #[test]
    fn self_loops_and_out_of_range_are_rejected() {
        let mut t = Topology::empty(3).unwrap();
        assert!(t.set_edge(1, 1, true).is_err());
        assert!(t.set_edge(0, 3, true).is_err());
        assert!(!t.edge(1, 1));
    }

    #[test]
    fn one_agent_teams_are_rejected() {
        assert!(matches!(
            Topology::empty(1),
            Err(TopologyError::TeamTooSmall { n: 1 })
        ));
    }

    #[test]
    fn families_have_the_expected_edge_counts() {
        let n = 4;
        assert_eq!(Topology::complete(n).unwrap().edge_count(), n * (n - 1));
        assert_eq!(Topology::chain(n).unwrap().edge_count(), n - 1);
        assert_eq!(Topology::star(n, 0).unwrap().edge_count(), 2 * (n - 1));
        assert_eq!(Topology::empty(n).unwrap().edge_count(), 0);
    }

    #[test]
    fn from_matrix_ignores_the_diagonal() {
        let m = vec![
            vec![true, true, false],
            vec![false, true, true],
            vec![false, false, true],
        ];
        let t = Topology::from_matrix(&m).unwrap();
        assert_eq!(t.edge_count(), 2);
        assert!(t.edge(0, 1) && t.edge(1, 2));
    }

    #[test]
    fn erdos_renyi_is_deterministic_in_the_seed() {
        let a = Topology::erdos_renyi(5, 0.5, 42).unwrap();
        let b = Topology::erdos_renyi(5, 0.5, 42).unwrap();
        let c = Topology::erdos_renyi(5, 0.5, 43).unwrap();
        assert_eq!(a, b);
        assert_ne!(a.key(), c.key());
    }

    #[test]
    fn erdos_renyi_density_tracks_p() {
        let sparse = Topology::erdos_renyi(12, 0.1, 7).unwrap();
        let dense = Topology::erdos_renyi(12, 0.9, 7).unwrap();
        assert!(sparse.density() < 0.35, "got {}", sparse.density());
        assert!(dense.density() > 0.65, "got {}", dense.density());
    }

    #[test]
    fn hamming_rejects_size_mismatch_and_counts_differences() {
        let chain = Topology::chain(4).unwrap();
        let complete = Topology::complete(4).unwrap();
        assert_eq!(chain.hamming(&chain).unwrap(), 0);
        assert_eq!(
            chain.hamming(&complete).unwrap(),
            complete.edge_count() - chain.edge_count()
        );
        assert!(chain.hamming(&Topology::chain(5).unwrap()).is_err());
    }

    #[test]
    fn key_is_structural_not_construction_order() {
        let mut a = Topology::empty(3).unwrap();
        a.set_edge(0, 1, true).unwrap();
        a.set_edge(2, 0, true).unwrap();
        let mut b = Topology::empty(3).unwrap();
        b.set_edge(2, 0, true).unwrap();
        b.set_edge(0, 1, true).unwrap();
        assert_eq!(a.key(), b.key());
        assert_eq!(a, b);
    }

    #[test]
    fn collection_protocol_spans_six_topologies() {
        let protocol = Topology::collection_protocol(4).unwrap();
        assert_eq!(protocol.len(), 6);
        assert!(protocol.iter().all(|t| t.n() == 4));
    }

    #[test]
    fn shapes_map_to_distinct_topologies_and_back() {
        let n = 4;
        assert_eq!(
            shape_of(&CoordinationShape::Pipeline.topology(n).unwrap()),
            Some(CoordinationShape::Pipeline)
        );
        assert_eq!(
            shape_of(&CoordinationShape::Debate.topology(n).unwrap()),
            Some(CoordinationShape::Debate)
        );
        assert_eq!(
            shape_of(&CoordinationShape::Supervisor.topology(n).unwrap()),
            Some(CoordinationShape::Supervisor)
        );
    }

    #[test]
    fn solo_and_swarm_share_a_matrix_and_recovery_prefers_swarm() {
        let n = 3;
        assert_eq!(
            CoordinationShape::Solo.topology(n).unwrap(),
            CoordinationShape::Swarm.topology(n).unwrap()
        );
        assert_eq!(
            shape_of(&CoordinationShape::Solo.topology(n).unwrap()),
            Some(CoordinationShape::Swarm)
        );
    }

    #[test]
    fn a_wrong_length_edge_array_is_refused_at_the_serde_boundary() {
        // The journal is a file a person can edit, and a line like this PARSES
        // — torn-line tolerance does not catch it. Before the `try_from`
        // boundary this deserialized happily and then panicked on the first
        // edge read with an out-of-bounds index.
        for json in [
            r#"{"n":4,"edges":[true]}"#,
            r#"{"n":4,"edges":[]}"#,
            r#"{"n":2,"edges":[true,false,true]}"#,
        ] {
            assert!(
                serde_json::from_str::<Topology>(json).is_err(),
                "should have been refused: {json}"
            );
        }
    }

    #[test]
    fn a_degenerate_team_size_is_refused_at_the_serde_boundary() {
        for json in [r#"{"n":1,"edges":[]}"#, r#"{"n":0,"edges":[]}"#] {
            assert!(
                serde_json::from_str::<Topology>(json).is_err(),
                "should have been refused: {json}"
            );
        }
    }

    #[test]
    fn a_well_formed_topology_still_round_trips() {
        for topology in Topology::collection_protocol(4).unwrap() {
            let json = serde_json::to_string(&topology).unwrap();
            let back: Topology = serde_json::from_str(&json).unwrap();
            assert_eq!(topology, back);
            // And every edge is readable without panicking.
            for i in 0..back.n() {
                for j in 0..back.n() {
                    let _ = back.edge(i, j);
                }
            }
        }
    }

    #[test]
    fn a_learned_topology_need_not_be_any_shape() {
        let mut t = Topology::empty(4).unwrap();
        t.set_edge(0, 1, true).unwrap();
        t.set_edge(0, 2, true).unwrap();
        t.set_edge(3, 1, true).unwrap();
        assert_eq!(shape_of(&t), None);
    }
}