Struct GraphOutcomes 

pub struct GraphOutcomes {
    values: Vec<GameOutcome>,
    winning: Vec<Option<usize>>,
}

Fields

values: Vec<GameOutcome>

winning: Vec<Option<usize>>

Implementations

impl GraphOutcomes

fn extend(&mut self, edges: &[Vec<usize>], reverse: &[Vec<usize>], misere: bool)

Examples found in repository

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

    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 GraphOutcomes

fn default() -> Self

Returns the “default value” for a type.