dcc_tiler/
graph.rs

1use crate::board::RectangularBoard;
2use serde_derive::Serialize;
3use std::collections::{HashMap, HashSet};
4
5#[derive(Debug, Serialize, Default)]
6pub struct BoardGraph {
7    // The nodes in our graph are boards - we store there here inside a vec
8    //// so that we dont have Rc<RefCell<..>> all over the place
9    nodes_arena: Vec<RectangularBoard>,
10
11    #[serde(skip_serializing)]
12    nodes_arena_index: usize,
13
14    // An edge in our graph indicates that it is possible to get from one board state
15    // to another by placing down a tile.
16    edges: HashMap<usize, HashSet<usize>>,
17
18    // This hashmap keeps track of edges "going backwards"
19    rev_edges: HashMap<usize, HashSet<usize>>,
20
21    // If a complete tiling of an initial board (index 0 in nodes_arena)
22    complete_indices: HashSet<usize>,
23}
24
25impl BoardGraph {
26    pub fn new() -> Self {
27        BoardGraph {
28            nodes_arena: Vec::new(),
29            nodes_arena_index: 0,
30            edges: HashMap::new(),
31            rev_edges: HashMap::new(),
32            complete_indices: HashSet::new(),
33        }
34    }
35
36    #[allow(clippy::never_loop)]
37    pub fn get_complete_index(&self) -> Option<usize> {
38        for index in &self.complete_indices {
39            return Some(*index);
40        }
41        None
42    }
43
44    pub fn mark_node_as_complete(&mut self, i: usize) {
45        self.complete_indices.insert(i);
46    }
47
48    pub fn find_node(&self, v: &RectangularBoard) -> Option<usize> {
49        for (i, node) in self.nodes_arena.iter().enumerate() {
50            if node == v {
51                return Some(i);
52            }
53        }
54        None
55    }
56
57    pub fn get_edges(&self, i: usize) -> Option<&HashSet<usize>> {
58        self.edges.get(&i)
59    }
60
61    pub fn get_rev_edges(&self, i: usize) -> Option<&HashSet<usize>> {
62        self.rev_edges.get(&i)
63    }
64
65    pub fn get_node(&self, i: usize) -> Option<&RectangularBoard> {
66        self.nodes_arena.get(i)
67    }
68
69    pub fn add_node(&mut self, v: RectangularBoard) -> usize {
70        self.nodes_arena.push(v);
71
72        self.nodes_arena_index += 1;
73        self.nodes_arena_index - 1
74    }
75
76    pub fn add_edge(&mut self, s: usize, t: usize) {
77        assert!(s < self.nodes_arena_index && t < self.nodes_arena_index);
78
79        self.edges.entry(s).or_insert_with(HashSet::new).insert(t);
80        self.rev_edges
81            .entry(t)
82            .or_insert_with(HashSet::new)
83            .insert(s);
84    }
85}
dcc_tiler/graph.rs

dcc_tiler/
graph.rs
