Struct GraphSums 

pub struct GraphSums {
    indices: HashMap<Vec<usize>, usize>,
    outcomes: GraphOutcomes,
}

Fields

indices: HashMap<Vec<usize>, usize>

outcomes: GraphOutcomes

Implementations

impl GraphSums

fn prepare(&mut self, state: Vec<usize>, components: &[Vec<usize>]) -> usize

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 513)

    fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
        match state {
            [] => return GameOutcome::from_win(misere),
            [single] => return self.outcome(single, misere),
            _ => {}
        }
        let indices = self.sum_indices(state);
        if !misere {
            self.solve_generalized_grundy();
            return self.sum_normal_outcome(&indices);
        }
        let edges = &self.index.as_ref().unwrap().edges;
        let root = self.sums.prepare(indices, edges);
        self.sums.outcomes.values[root]
    }

fn canonical(state: Vec<usize>, components: &[Vec<usize>]) -> Vec<usize>

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 310)

    pub fn winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return Vec::new();
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .winning_moves(single)
                .into_iter()
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)))
                .collect();
        }
        if self.eval(state) != GameOutcome::Win {
            return Vec::new();
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        let mut xor = 0;
        let mut infinite = 0;
        if !MISERE {
            for &v in &indices {
                if let Some((value, _)) = game.generalized_grundy[v] {
                    xor ^= value;
                } else {
                    infinite += 1;
                }
            }
        }
        let mut result = Vec::new();
        for (i, &component) in state.iter().enumerate() {
            let source = indices[i];
            for next in game.graph.neighbors(component) {
                indices[i] = game.index_of(next.to);
                let wins = if MISERE {
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    game.sums.outcomes.values[game.sums.indices[&key]] == GameOutcome::Lose
                } else if let Some((value, _)) = game.generalized_grundy[indices[i]] {
                    match game.generalized_grundy[source] {
                        Some((g, _)) => infinite == 0 && xor ^ g == value,
                        None => infinite == 1 && xor == value,
                    }
                } else {
                    false
                };
                if wins {
                    let mut to = state.to_vec();
                    to[i] = next.to;
                    result.push(Neighbor::new(to, (i, next.label)));
                }
            }
            indices[i] = source;
        }
        result
    }

    /// A move that guarantees termination when winning, or preserves a draw.
    /// Returns `None` at terminal or losing positions.
    pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return None;
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .best_move(single)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
        }
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        if MISERE {
            let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
            let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
            for (i, &component) in state.iter().enumerate() {
                let original = indices[i];
                for next in game.graph.neighbors(component) {
                    indices[i] = game.index_of(next.to);
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    let id = game.sums.indices[&key];
                    if Some(id) == winner
                        || outcome == GameOutcome::Draw
                            && game.sums.outcomes.values[id] == GameOutcome::Draw
                    {
                        let mut to = state.to_vec();
                        to[i] = next.to;
                        return Some(Neighbor::new(to, (i, next.label)));
                    }
                }
                indices[i] = original;
            }
            return None;
        }
        let mut xor = 0;
        let mut infinite = None;
        let mut multiple = false;
        for (i, &v) in indices.iter().enumerate() {
            if let Some((value, _)) = game.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(i).is_some() {
                multiple = true;
                break;
            }
        }
        if outcome == GameOutcome::Draw {
            let i = infinite.unwrap();
            let v = indices[i];
            let edges = &game.index.as_ref().unwrap().edges;
            let target = (!multiple).then(|| {
                let values = edges[v]
                    .iter()
                    .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
                    .collect();
                game_mex(values)
            });
            // Preserve two infinite components, or keep the finite XOR outside
            // the remaining infinite component's finite follower values.
            if target.is_none_or(|g| g == xor) {
                let to = edges[v]
                    .iter()
                    .copied()
                    .find(|&u| {
                        game.generalized_grundy[u].is_none()
                            && target.is_none_or(|g| {
                                !edges[u].iter().any(|&w| {
                                    game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
                                })
                            })
                    })
                    .unwrap();
                let next = game
                    .graph
                    .neighbors(state[i])
                    .find(|next| game.index_of(next.to) == to)
                    .unwrap();
                let mut to = state.to_vec();
                to[i] = next.to;
                return Some(Neighbor::new(to, (i, next.label)));
            }
            // The current finite XOR exceeds this mex, so a finite component
            // can decrease it to the mex without moving the infinite component.
            xor ^= target.unwrap();
            infinite = None;
        }
        // Reduce the largest (Grundy, counter) pair, then minimize the
        // destination counter so repeated winning moves terminate.
        let (i, target) = if let Some(i) = infinite {
            (i, xor)
        } else {
            let (i, (g, _)) = indices
                .iter()
                .enumerate()
                .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
                .filter(|(_, (g, _))| g ^ xor < *g)
                .max_by_key(|&(i, g)| (g, Reverse(i)))?;
            (i, g ^ xor)
        };
        let next = game
            .graph
            .neighbors(state[i])
            .filter_map(|next| {
                let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
                (g == target).then_some((next, counter))
            })
            .min_by_key(|&(_, counter)| counter)?
            .0;
        let mut to = state.to_vec();
        to[i] = next.to;
        Some(Neighbor::new(to, (i, next.label)))
    }
}

impl<G> ImpartialGraph<'_, G>
where
    G: Graph + VertexMap<Option<usize>>,
{
    fn grundy(&mut self, state: &G::Vertex) -> u64 {
        self.prepare();
        let root = self.index_of(*state);
        let index = self.index.as_ref().unwrap();
        self.grundy.resize(index.edges.len(), None);
        if let Some(value) = self.grundy[root] {
            return value;
        }
        let mut active = HashSet::from([root]);
        let mut stack = vec![(root, index.edges[root].iter())];
        while let Some((v, moves)) = stack.last_mut() {
            if let Some(&u) = moves.next() {
                if self.grundy[u].is_none() {
                    assert!(active.insert(u), "cycle in a finite game");
                    stack.push((u, index.edges[u].iter()));
                }
            } else {
                let values = index.edges[*v]
                    .iter()
                    .map(|&u| self.grundy[u].unwrap())
                    .collect();
                self.grundy[*v] = Some(game_mex(values));
                active.remove(v);
                stack.pop();
            }
        }
        self.grundy[root].unwrap()
    }

    fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
        self.prepare();
        let index = self.index.as_ref().unwrap();
        let outcome = &mut self.outcomes[usize::from(misere)];
        if outcome.values.is_empty() {
            outcome.extend(&index.edges, &index.reverse, misere);
        }
        self.outcomes[usize::from(misere)].values[self.index_of(*state)]
    }

    fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
        state.iter().fold(0, |value, s| value ^ self.grundy(s))
    }

    fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
        match state {
            [] => return GameOutcome::from_win(misere),
            [single] => return self.outcome(single, misere),
            _ => {}
        }
        let indices = self.sum_indices(state);
        if !misere {
            self.solve_generalized_grundy();
            return self.sum_normal_outcome(&indices);
        }
        let edges = &self.index.as_ref().unwrap().edges;
        let root = self.sums.prepare(indices, edges);
        self.sums.outcomes.values[root]
    }

    fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome {
        let mut xor = 0;
        let mut infinite = None;
        for &v in state {
            if let Some((value, _)) = self.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(v).is_some() {
                return GameOutcome::Draw;
            }
        }
        if let Some(v) = infinite {
            let can_win = self.index.as_ref().unwrap().edges[v]
                .iter()
                .any(|&u| self.generalized_grundy[u].is_some_and(|(value, _)| value == xor));
            if can_win {
                GameOutcome::Win
            } else {
                GameOutcome::Draw
            }
        } else if xor == 0 {
            GameOutcome::Lose
        } else {
            GameOutcome::Win
        }
    }

    fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize> {
        self.prepare();
        state.iter().map(|&s| self.index_of(s)).collect()
    }

    fn prepare(&mut self) {
        if self.index.is_some() {
            return;
        }
        let vertices: Vec<_> = self.graph.vertices().collect();
        let mut indices = self.graph.construct_vmap(|| None);
        for (i, &v) in vertices.iter().enumerate() {
            self.graph.vmap_set(&mut indices, v, Some(i));
        }
        let mut edges = vec![Vec::new(); vertices.len()];
        let mut reverse = vec![Vec::new(); vertices.len()];
        let mut seen = vec![None; vertices.len()];
        for (i, &v) in vertices.iter().enumerate() {
            for next in self.graph.neighbors(v) {
                let j = self
                    .graph
                    .vmap_get(&indices, next.to)
                    .expect("vertex is not enumerated by the graph");
                if seen[j] != Some(i) {
                    seen[j] = Some(i);
                    edges[i].push(j);
                    reverse[j].push(i);
                }
            }
        }
        self.index = Some(GraphIndex {
            indices,
            edges,
            reverse,
        });
    }

    fn index_of(&self, v: G::Vertex) -> usize {
        self.graph
            .vmap_get(&self.index.as_ref().unwrap().indices, v)
            .expect("vertex is not enumerated by the graph")
    }

    fn solve_generalized_grundy(&mut self) {
        let index = self.index.as_ref().unwrap();
        let n = index.edges.len();
        if self.generalized_grundy.len() == n {
            return;
        }
        let mut values: Vec<Option<(u64, usize)>> = vec![None; n];
        // Visit acyclic followers first, so DAGs need only one pass.
        let reverse = UsizeGraph::new(n, |v: usize| index.reverse[v].iter().map(|&u| (u, ())));
        let order = reverse.topological_sort();
        if order.len() == n {
            for (counter, v) in order.into_iter().enumerate() {
                let mex = self.grundy.get(v).copied().flatten().unwrap_or_else(|| {
                    let options = index.edges[v]
                        .iter()
                        .map(|&u| values[u].unwrap().0)
                        .collect();
                    game_mex(options)
                });
                values[v] = Some((mex, counter));
            }
            self.generalized_grundy = values;
            return;
        }
        let mut queue: VecDeque<_> = order.into();
        let mut queued = vec![false; n];
        for &v in &queue {
            queued[v] = true;
        }
        for (v, pending) in queued.iter_mut().enumerate() {
            if !*pending {
                *pending = true;
                queue.push_back(v);
            }
        }
        let mut counter = 0;
        let mut options = vec![HashSet::new(); n];
        let mut mexes = vec![0; n];
        while let Some(v) = queue.pop_front() {
            queued[v] = false;
            let mex = mexes[v];
            // Every unresolved option must be able to return to this mex.
            let ready = index.edges[v]
                .iter()
                .all(|&u| values[u].is_some() || options[u].contains(&mex));
            if !ready {
                continue;
            }
            values[v] = Some((mex, counter));
            counter += 1;
            for &u in &index.reverse[v] {
                if values[u].is_some() {
                    continue;
                }
                let inserted = options[u].insert(mex);
                if inserted {
                    while options[u].contains(&mexes[u]) {
                        mexes[u] += 1;
                    }
                }
                // A larger value already had a follower at this vertex's mex.
                if mex < mexes[u] && !queued[u] {
                    queued[u] = true;
                    queue.push_back(u);
                }
                if inserted {
                    for &w in &index.reverse[u] {
                        if queue.len() == n - counter {
                            break; // All unresolved vertices are already queued.
                        }
                        if values[w].is_none() && !queued[w] && mexes[w] == mex {
                            queued[w] = true;
                            queue.push_back(w);
                        }
                    }
                }
            }
        }
        self.generalized_grundy = values;
    }
}

impl GraphSums {
    fn prepare(&mut self, state: Vec<usize>, components: &[Vec<usize>]) -> usize {
        let state = Self::canonical(state, components);
        if let Some(&root) = self.indices.get(&state) {
            return root;
        }
        let root = self.outcomes.values.len();
        self.indices.insert(state.clone(), root);
        let mut edges = vec![Vec::new()];
        let mut reverse = vec![Vec::new()];
        let mut pending = VecDeque::from([(root, state)]);
        while let Some((v, state)) = pending.pop_front() {
            for (i, &component) in state.iter().enumerate() {
                if i != 0 && state[i - 1] == component {
                    continue;
                }
                for &next in &components[component] {
                    let mut to = state.clone();
                    to[i] = next;
                    let to = Self::canonical(to, components);
                    let u = *self.indices.entry(to).or_insert_with_key(|to| {
                        let u = root + edges.len();
                        pending.push_back((u, to.clone()));
                        edges.push(Vec::new());
                        reverse.push(Vec::new());
                        u
                    });
                    edges[v - root].push(u);
                }
            }
            edges[v - root].sort_unstable();
            edges[v - root].dedup();
            for &u in &edges[v - root] {
                if u >= root {
                    reverse[u - root].push(v);
                }
            }
        }
        self.outcomes.extend(&edges, &reverse, true);
        root
    }

Trait Implementations

impl Default for GraphSums

fn default() -> Self

Returns the “default value” for a type.