1
//! Authors: Maurice Laveaux and Sjef van Loo
2

            
3
use std::collections::VecDeque;
4

            
5
use bitvec::bitvec;
6
use bitvec::order::Lsb0;
7

            
8
use crate::PG;
9
use crate::ParityGame;
10
use crate::VertexIndex;
11

            
12
/// Computes the reachable portion of a parity game from the initial vertex.
13
///
14
/// Returns a new parity game containing only reachable vertices and a mapping
15
/// from old vertex indices to new vertex indices (None for unreachable vertices).
16
754
pub fn compute_reachable(game: &impl PG) -> (ParityGame, Vec<Option<usize>>) {
17
754
    let num_vertices = game.num_of_vertices();
18

            
19
    // Mapping from old vertex indices to new vertices (None means unreachable)
20
754
    let mut mapping = vec![None; num_vertices];
21
754
    let mut visited = bitvec![usize, Lsb0; 0; num_vertices];
22

            
23
    // New game data structures
24
754
    let mut new_owners = Vec::new();
25
754
    let mut new_priorities = Vec::new();
26
754
    let mut new_vertices = vec![0]; // Start with offset 0
27
754
    let mut new_edges_to = Vec::new();
28

            
29
    // Helper closure to add a vertex to the new game
30
8758
    let mut add_vertex = |v: VertexIndex| -> usize {
31
8758
        if let Some(idx) = mapping[*v] {
32
5044
            return idx;
33
3714
        }
34

            
35
        // Add a new vertex
36
3714
        let new_v = new_owners.len();
37
3714
        new_owners.push(game.owner(v));
38
3714
        new_priorities.push(game.priority(v));
39

            
40
        // Update mapping
41
3714
        mapping[*v] = Some(new_v);
42
3714
        new_v
43
8758
    };
44

            
45
    // BFS from initial vertex
46
754
    let mut queue = VecDeque::new();
47
754
    let initial = game.initial_vertex();
48
754
    queue.push_back(initial);
49
754
    visited.set(*initial, true);
50

            
51
4468
    while let Some(v) = queue.pop_front() {
52
        // Ensure the current vertex exists in the new game
53
3714
        let _new_v = add_vertex(v);
54
3714
        debug_assert_eq!(_new_v, new_vertices.len() - 1);
55

            
56
        // Process all outgoing edges
57
5044
        for w in game.outgoing_edges(v) {
58
5044
            let new_w = add_vertex(w);
59
5044
            new_edges_to.push(VertexIndex::new(new_w));
60

            
61
5044
            if !visited[*w] {
62
2960
                visited.set(*w, true);
63
2960
                queue.push_back(w);
64
2960
            }
65
        }
66

            
67
        // Update vertex offset for next vertex
68
3714
        new_vertices.push(new_edges_to.len());
69
    }
70

            
71
    // Find new initial vertex
72
754
    let new_initial_idx = mapping[*initial].expect("Initial vertex is unreachable, which should be impossible");
73
754
    let new_initial = VertexIndex::new(new_initial_idx);
74

            
75
754
    let new_game = ParityGame::new(new_initial, new_owners, new_priorities, new_vertices, new_edges_to);
76

            
77
754
    (new_game, mapping)
78
754
}