problemreductions/models/graph/
generalized_hex.rs

1//! Generalized Hex problem implementation.
2//!
3//! Generalized Hex asks whether the first player has a forced win in the
4//! vertex-claiming Shannon switching game on an undirected graph.
5
6use std::collections::{HashMap, VecDeque};
7
8use serde::{Deserialize, Serialize};
9
10use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
11use crate::topology::{Graph, SimpleGraph};
12use crate::traits::Problem;
13use crate::variant::VariantParam;
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "GeneralizedHex",
18        display_name: "Generalized Hex",
19        aliases: &[],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
22        ],
23        category: crate::registry::ProblemCategory::Graph,
24        module_path: module_path!(),
25        description: "Determine whether Player 1 has a forced blue path between two terminals",
26        fields: GeneralizedHexCreateSpec::FIELDS,
27    }
28}
29
30/// Generalized Hex on an undirected graph.
31///
32/// The problem is represented as a zero-variable decision problem: the graph
33/// instance fully determines the question, so `evaluate([])` runs a memoized
34/// game-tree search from the initial empty board.
35#[derive(Debug, Clone, Serialize, Deserialize)]
36#[serde(bound(deserialize = "G: serde::Deserialize<'de>"))]
37pub struct GeneralizedHex<G> {
38    graph: G,
39    source: usize,
40    target: usize,
41}
42
43#[derive(Debug, Deserialize, crate::CreateSpec)]
44struct GeneralizedHexCreateSpec {
45    /// The underlying graph G=(V,E).
46    graph: SimpleGraph,
47    /// The source terminal s.
48    source: usize,
49    /// The target terminal t.
50    sink: usize,
51}
52
53impl TryFrom<GeneralizedHexCreateSpec> for GeneralizedHex<SimpleGraph> {
54    type Error = crate::registry::ConstructionError;
55
56    fn try_from(spec: GeneralizedHexCreateSpec) -> Result<Self, Self::Error> {
57        let num_vertices = spec.graph.num_vertices();
58        if spec.source >= num_vertices {
59            return Err(format!(
60                "source {} is outside graph with {num_vertices} vertices",
61                spec.source
62            )
63            .into());
64        }
65        if spec.sink >= num_vertices {
66            return Err(format!(
67                "sink {} is outside graph with {num_vertices} vertices",
68                spec.sink
69            )
70            .into());
71        }
72        if spec.source == spec.sink {
73            return Err("source and sink must be distinct".to_string().into());
74        }
75        Ok(Self::new(spec.graph, spec.source, spec.sink))
76    }
77}
78
79#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
80enum ClaimState {
81    Unclaimed,
82    Blue,
83    Red,
84}
85
86impl<G: Graph> GeneralizedHex<G> {
87    /// Create a new Generalized Hex instance.
88    pub fn new(graph: G, source: usize, target: usize) -> Self {
89        let num_vertices = graph.num_vertices();
90        assert!(source < num_vertices, "source must be a valid graph vertex");
91        assert!(target < num_vertices, "target must be a valid graph vertex");
92        assert_ne!(source, target, "source and target must be distinct");
93        Self {
94            graph,
95            source,
96            target,
97        }
98    }
99
100    /// Get a reference to the underlying graph.
101    pub fn graph(&self) -> &G {
102        &self.graph
103    }
104
105    /// Get the source terminal.
106    pub fn source(&self) -> usize {
107        self.source
108    }
109
110    /// Get the target terminal.
111    pub fn target(&self) -> usize {
112        self.target
113    }
114
115    /// Get the number of vertices in the graph.
116    pub fn num_vertices(&self) -> usize {
117        self.graph.num_vertices()
118    }
119
120    /// Get the number of edges in the graph.
121    pub fn num_edges(&self) -> usize {
122        self.graph.num_edges()
123    }
124
125    /// Get the number of playable non-terminal vertices.
126    pub fn num_playable_vertices(&self) -> usize {
127        self.graph.num_vertices().saturating_sub(2)
128    }
129
130    /// Check whether the first player has a forced win from the initial state.
131    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
132        if !config.is_empty() {
133            return false;
134        }
135        let playable_vertices = self.playable_vertices();
136        let vertex_to_state_index = self.vertex_to_state_index(&playable_vertices);
137        let mut state = vec![ClaimState::Unclaimed; playable_vertices.len()];
138        let mut memo = HashMap::new();
139        self.first_player_wins(&mut state, &vertex_to_state_index, &mut memo)
140    }
141
142    fn playable_vertices(&self) -> Vec<usize> {
143        (0..self.graph.num_vertices())
144            .filter(|&vertex| vertex != self.source && vertex != self.target)
145            .collect()
146    }
147
148    fn vertex_to_state_index(&self, playable_vertices: &[usize]) -> Vec<Option<usize>> {
149        let mut index = vec![None; self.graph.num_vertices()];
150        for (state_idx, &vertex) in playable_vertices.iter().enumerate() {
151            index[vertex] = Some(state_idx);
152        }
153        index
154    }
155
156    fn first_player_wins(
157        &self,
158        state: &mut [ClaimState],
159        vertex_to_state_index: &[Option<usize>],
160        memo: &mut HashMap<Vec<ClaimState>, bool>,
161    ) -> bool {
162        if self.has_path(state, vertex_to_state_index, |claim| {
163            matches!(claim, ClaimState::Blue)
164        }) {
165            return true;
166        }
167        if !self.has_path(state, vertex_to_state_index, |claim| {
168            claim != ClaimState::Red
169        }) {
170            return false;
171        }
172        if let Some(&cached) = memo.get(state) {
173            return cached;
174        }
175
176        let blue_turn = state
177            .iter()
178            .filter(|&&claim| !matches!(claim, ClaimState::Unclaimed))
179            .count()
180            % 2
181            == 0;
182
183        let result = if blue_turn {
184            let mut winning_move_found = false;
185            for idx in 0..state.len() {
186                if !matches!(state[idx], ClaimState::Unclaimed) {
187                    continue;
188                }
189                state[idx] = ClaimState::Blue;
190                if self.first_player_wins(state, vertex_to_state_index, memo) {
191                    winning_move_found = true;
192                    state[idx] = ClaimState::Unclaimed;
193                    break;
194                }
195                state[idx] = ClaimState::Unclaimed;
196            }
197            winning_move_found
198        } else {
199            let mut all_red_moves_still_win = true;
200            for idx in 0..state.len() {
201                if !matches!(state[idx], ClaimState::Unclaimed) {
202                    continue;
203                }
204                state[idx] = ClaimState::Red;
205                if !self.first_player_wins(state, vertex_to_state_index, memo) {
206                    all_red_moves_still_win = false;
207                    state[idx] = ClaimState::Unclaimed;
208                    break;
209                }
210                state[idx] = ClaimState::Unclaimed;
211            }
212            all_red_moves_still_win
213        };
214
215        memo.insert(state.to_vec(), result);
216        result
217    }
218
219    fn has_path<F>(
220        &self,
221        state: &[ClaimState],
222        vertex_to_state_index: &[Option<usize>],
223        allow_claim: F,
224    ) -> bool
225    where
226        F: Fn(ClaimState) -> bool,
227    {
228        let mut visited = vec![false; self.graph.num_vertices()];
229        let mut queue = VecDeque::from([self.source]);
230        visited[self.source] = true;
231
232        while let Some(vertex) = queue.pop_front() {
233            if vertex == self.target {
234                return true;
235            }
236
237            for neighbor in self.graph.neighbors(vertex) {
238                if visited[neighbor]
239                    || !self.vertex_is_allowed(neighbor, state, vertex_to_state_index, &allow_claim)
240                {
241                    continue;
242                }
243                visited[neighbor] = true;
244                queue.push_back(neighbor);
245            }
246        }
247
248        false
249    }
250
251    fn vertex_is_allowed<F>(
252        &self,
253        vertex: usize,
254        state: &[ClaimState],
255        vertex_to_state_index: &[Option<usize>],
256        allow_claim: &F,
257    ) -> bool
258    where
259        F: Fn(ClaimState) -> bool,
260    {
261        if vertex == self.source || vertex == self.target {
262            return true;
263        }
264        vertex_to_state_index[vertex]
265            .and_then(|state_idx| state.get(state_idx).copied())
266            .is_some_and(allow_claim)
267    }
268}
269
270impl<G> Problem for GeneralizedHex<G>
271where
272    G: Graph + VariantParam,
273{
274    const NAME: &'static str = "GeneralizedHex";
275    type Solution = ();
276    type Value = crate::types::Or;
277
278    crate::problem_parameters![
279        ("num_vertices", num_vertices),
280        ("num_edges", num_edges),
281        ("num_playable_vertices", num_playable_vertices),
282    ];
283
284    fn variant() -> Vec<(&'static str, &'static str)> {
285        crate::variant_params![G]
286    }
287
288    fn evaluate(
289        &self,
290        _solution: &Self::Solution,
291    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
292        Ok({
293            crate::types::Or({
294                let playable_vertices = self.playable_vertices();
295                let vertex_to_state_index = self.vertex_to_state_index(&playable_vertices);
296                let mut state = vec![ClaimState::Unclaimed; playable_vertices.len()];
297                let mut memo = HashMap::new();
298                self.first_player_wins(&mut state, &vertex_to_state_index, &mut memo)
299            })
300        })
301    }
302}
303
304impl<G> crate::solvers::BruteForceProblem for GeneralizedHex<G>
305where
306    G: Graph + VariantParam,
307{
308    fn dimensions(&self) -> Vec<usize> {
309        vec![]
310    }
311}
312
313crate::impl_random_generate!(
314    GeneralizedHex<SimpleGraph>,
315    crate::random::EndpointRandomSpec,
316    |spec| {
317        let (source, sink) = spec.endpoints()?;
318        Ok(GeneralizedHex::new(spec.graph()?, source, sink))
319    }
320);
321
322crate::declare_variants! {
323    default GeneralizedHex<SimpleGraph> => "3^num_playable_vertices" create GeneralizedHexCreateSpec random,
324}
325
326crate::register_brute_force! {
327    GeneralizedHex<SimpleGraph> decode |_, _| (),
328}
329
330#[cfg(feature = "example-db")]
331pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
332    vec![crate::example_db::specs::ModelExampleSpec {
333        id: "generalized_hex_simplegraph",
334        instance: Box::new(GeneralizedHex::new(
335            SimpleGraph::new(
336                6,
337                vec![(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4), (4, 5)],
338            ),
339            0,
340            5,
341        )),
342        optimal_config: serde_json::json!(null),
343        optimal_value: serde_json::json!(true),
344    }]
345}
346
347#[cfg(test)]
348#[path = "../../unit_tests/models/graph/generalized_hex.rs"]
349mod tests;
problemreductions/models/graph/generalized_hex.rs

problemreductions/models/graph/
generalized_hex.rs
