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

problemreductions/models/graph/
generalized_hex.rs
