lattice_graph/lattice_abstract/
square.rs

1//! Square graph using Abstract Lattice Graph. If you want a undirected square graph, it is recommended to use specialized [`SquareGraph`](`crate::SquareGraph`).
2//! Use this for directed graph or square with diagonal direction graph.
3
4use super::*;
5use petgraph::{Directed, Undirected};
6
7/// Undirected Square Graph based on [`LatticeGraph`], recommended to use [`SquareGraph`](`crate::SquareGraph`) instead.
8pub type SquareGraphAbstract<N, E> = LatticeGraph<N, E, SquareShape>;
9/// Directed Square Graph based on [`LatticeGraph`].
10pub type DirectedSquareGraph<N, E> = LatticeGraph<N, E, SquareShape<Directed>>;
11/// Undirected Square Graph with edge to diagonal direction.
12pub type DiagonalSquareGraph<N, E> = LatticeGraph<N, E, SquareDiagonalShape>;
13/// Directed Square Graph with edge to diagonal direction.
14pub type DirectedDiagonalSquareGraph<N, E> = LatticeGraph<N, E, SquareDiagonalShape<Directed>>;
15
16/// Axis for square graph.
17#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
18pub enum SquareAxis {
19    X = 0,
20    Y = 1,
21}
22
23impl Axis for SquareAxis {
24    const COUNT: usize = 2;
25    const DIRECTED: bool = false;
26    type Direction = DirectedSquareAxis;
27    const UNDIRECTED_COUNT: usize = if Self::DIRECTED {
28        Self::COUNT
29    } else {
30        Self::COUNT * 2
31    };
32
33    fn to_index(&self) -> usize {
34        match self {
35            SquareAxis::X => 0,
36            SquareAxis::Y => 1,
37        }
38    }
39
40    #[allow(unused_unsafe)]
41    unsafe fn from_index_unchecked(index: usize) -> Self {
42        match index {
43            0 => SquareAxis::X,
44            1 => SquareAxis::Y,
45            _ => unsafe { core::hint::unreachable_unchecked() },
46        }
47    }
48
49    fn from_index(index: usize) -> Option<Self>
50    where
51        Self: Sized,
52    {
53        match index {
54            0 => Some(SquareAxis::X),
55            1 => Some(SquareAxis::Y),
56            _ => None,
57        }
58    }
59
60    fn foward(self) -> Self::Direction {
61        unsafe { DirectedSquareAxis::from_index_unchecked(self.to_index()) }
62    }
63
64    fn backward(self) -> Self::Direction {
65        unsafe { DirectedSquareAxis::from_index_unchecked(self.to_index() + 2) }
66    }
67
68    fn from_direction(dir: Self::Direction) -> Self {
69        let i = dir.dir_to_index();
70        unsafe { Self::from_index_unchecked(if i >= 2 { i - 2 } else { i }) }
71    }
72}
73
74/// Offset for square lattice graph.
75#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
76#[repr(transparent)]
77pub struct SquareOffset(pub Offset);
78
79impl PartialEq<(usize, usize)> for SquareOffset {
80    fn eq(&self, other: &(usize, usize)) -> bool {
81        self.0.horizontal == other.0 && self.0.vertical == other.1
82    }
83}
84
85impl From<(usize, usize)> for SquareOffset {
86    fn from(x: (usize, usize)) -> Self {
87        SquareOffset(Offset {
88            horizontal: x.0,
89            vertical: x.1,
90        })
91    }
92}
93
94impl Coordinate for SquareOffset {}
95
96#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
97/// Shape for Square Graph.
98pub struct SquareShape<E = Undirected> {
99    h: usize,
100    v: usize,
101    e: PhantomData<E>,
102}
103
104impl<E> SquareShape<E> {
105    /// Create a new graph.
106    pub fn new(h: usize, v: usize) -> Self {
107        Self {
108            h,
109            v,
110            e: PhantomData,
111        }
112    }
113}
114
115fn range_check<S: Shape>(s: S, coord: SquareOffset) -> Result<Offset, ()> {
116    if coord.0.horizontal < s.horizontal() && coord.0.vertical < s.vertical() {
117        Ok(coord.0)
118    } else {
119        Err(())
120    }
121}
122
123fn move_coord<S: Shape>(
124    s: S,
125    coord: SquareOffset,
126    dir: DirectedSquareAxis,
127) -> Result<SquareOffset, ()> {
128    let o = match dir {
129        DirectedSquareAxis::X => coord.0.add_x(1).check_x(s.horizontal()),
130        DirectedSquareAxis::Y => coord.0.add_y(1).check_y(s.vertical()),
131        DirectedSquareAxis::RX => coord.0.sub_x(1),
132        DirectedSquareAxis::RY => coord.0.sub_y(1),
133    };
134    o.map(SquareOffset).ok_or(())
135}
136
137impl Shape for SquareShape {
138    type Axis = SquareAxis;
139    type Coordinate = SquareOffset;
140    type OffsetConvertError = ();
141    type CoordinateMoveError = ();
142
143    #[inline]
144    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, ()> {
145        range_check(self, coord)
146    }
147
148    #[inline]
149    unsafe fn to_offset_unchecked(&self, coord: Self::Coordinate) -> Offset {
150        coord.0
151    }
152
153    #[inline]
154    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate {
155        SquareOffset(offset)
156    }
157
158    #[inline]
159    fn horizontal(&self) -> usize {
160        self.h
161    }
162
163    #[inline]
164    fn vertical(&self) -> usize {
165        self.v
166    }
167
168    fn horizontal_edge_size(&self, axis: Self::Axis) -> usize {
169        let h = self.horizontal();
170        match axis {
171            SquareAxis::X => h - 1,
172            SquareAxis::Y => h,
173        }
174    }
175
176    fn vertical_edge_size(&self, axis: Self::Axis) -> usize {
177        let v = self.vertical();
178        match axis {
179            SquareAxis::X => v,
180            SquareAxis::Y => v - 1,
181        }
182    }
183
184    fn move_coord(&self, coord: SquareOffset, dir: DirectedSquareAxis) -> Result<SquareOffset, ()> {
185        move_coord(self, coord, dir)
186    }
187}
188
189/// Axis for directed square graph.
190#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
191pub enum DirectedSquareAxis {
192    X = 0,
193    Y = 1,
194    RX = 2,
195    RY = 3,
196}
197
198impl Axis for DirectedSquareAxis {
199    const COUNT: usize = 4;
200    const DIRECTED: bool = true;
201    type Direction = Self;
202
203    fn to_index(&self) -> usize {
204        match self {
205            DirectedSquareAxis::X => 0,
206            DirectedSquareAxis::Y => 1,
207            DirectedSquareAxis::RX => 2,
208            DirectedSquareAxis::RY => 3,
209        }
210    }
211
212    fn from_index(index: usize) -> Option<Self> {
213        Some(match index {
214            0 => DirectedSquareAxis::X,
215            1 => DirectedSquareAxis::Y,
216            2 => DirectedSquareAxis::RX,
217            3 => DirectedSquareAxis::RY,
218            _ => return None,
219        })
220    }
221
222    fn foward(self) -> Self::Direction {
223        self
224    }
225
226    fn backward(self) -> Self::Direction {
227        let x = self.to_index();
228        let x2 = if x > 2 { x - 2 } else { x + 2 };
229        unsafe { Self::from_index_unchecked(x2) }
230    }
231
232    fn from_direction(dir: Self::Direction) -> Self {
233        dir
234    }
235}
236
237impl Shape for SquareShape<petgraph::Directed> {
238    type Axis = DirectedSquareAxis;
239    type Coordinate = SquareOffset;
240    type OffsetConvertError = ();
241    type CoordinateMoveError = ();
242
243    fn horizontal(&self) -> usize {
244        self.h
245    }
246
247    fn vertical(&self) -> usize {
248        self.v
249    }
250
251    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, Self::OffsetConvertError> {
252        range_check(self, coord)
253    }
254
255    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate {
256        SquareOffset(offset)
257    }
258
259    fn move_coord(
260        &self,
261        coord: Self::Coordinate,
262        dir: DirectedSquareAxis,
263    ) -> Result<Self::Coordinate, Self::CoordinateMoveError> {
264        move_coord(self, coord, dir)
265    }
266}
267
268/// Axis for lattice graph with Square and Diagonal Edge.
269#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
270pub enum SquareDiagonalAxis {
271    N,
272    NE,
273    E,
274    SE,
275}
276
277impl Axis for SquareDiagonalAxis {
278    const COUNT: usize = 4;
279    const DIRECTED: bool = false;
280    const UNDIRECTED_COUNT: usize = if Self::DIRECTED {
281        Self::COUNT
282    } else {
283        Self::COUNT * 2
284    };
285    type Direction = DirectedSquareDiagonalAxis;
286
287    fn to_index(&self) -> usize {
288        match self {
289            SquareDiagonalAxis::N => 0,
290            SquareDiagonalAxis::NE => 1,
291            SquareDiagonalAxis::E => 2,
292            SquareDiagonalAxis::SE => 3,
293        }
294    }
295
296    fn from_index(index: usize) -> Option<Self>
297    where
298        Self: Sized,
299    {
300        Some(match index {
301            0 => SquareDiagonalAxis::N,
302            1 => SquareDiagonalAxis::NE,
303            2 => SquareDiagonalAxis::E,
304            3 => SquareDiagonalAxis::SE,
305            _ => return None,
306        })
307    }
308
309    fn foward(self) -> Self::Direction {
310        unsafe { DirectedSquareDiagonalAxis::from_index_unchecked(self.to_index()) }
311    }
312
313    fn backward(self) -> Self::Direction {
314        unsafe { DirectedSquareDiagonalAxis::from_index_unchecked(self.to_index() + 4) }
315    }
316
317    fn from_direction(dir: Self::Direction) -> Self {
318        unsafe {
319            let i = dir.to_index();
320            Self::from_index_unchecked(if i < 4 { i } else { i - 4 })
321        }
322    }
323}
324
325/// Axis for lattice graph with Square and Diagonal Edge.
326#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
327pub enum DirectedSquareDiagonalAxis {
328    N,
329    NE,
330    E,
331    SE,
332    S,
333    SW,
334    W,
335    NW,
336}
337
338impl Axis for DirectedSquareDiagonalAxis {
339    const COUNT: usize = 8;
340    const DIRECTED: bool = true;
341    const UNDIRECTED_COUNT: usize = if Self::DIRECTED {
342        Self::COUNT
343    } else {
344        Self::COUNT * 2
345    };
346    type Direction = Self;
347
348    fn to_index(&self) -> usize {
349        match self {
350            DirectedSquareDiagonalAxis::N => 0,
351            DirectedSquareDiagonalAxis::NE => 1,
352            DirectedSquareDiagonalAxis::E => 2,
353            DirectedSquareDiagonalAxis::SE => 3,
354            DirectedSquareDiagonalAxis::S => 4,
355            DirectedSquareDiagonalAxis::SW => 5,
356            DirectedSquareDiagonalAxis::W => 6,
357            DirectedSquareDiagonalAxis::NW => 7,
358        }
359    }
360
361    unsafe fn from_index_unchecked(index: usize) -> Self {
362        match index {
363            0 => DirectedSquareDiagonalAxis::N,
364            1 => DirectedSquareDiagonalAxis::NE,
365            2 => DirectedSquareDiagonalAxis::E,
366            3 => DirectedSquareDiagonalAxis::SE,
367            4 => DirectedSquareDiagonalAxis::S,
368            5 => DirectedSquareDiagonalAxis::SW,
369            6 => DirectedSquareDiagonalAxis::W,
370            7 => DirectedSquareDiagonalAxis::NW,
371            _ => core::hint::unreachable_unchecked(),
372        }
373    }
374
375    fn from_index(index: usize) -> Option<Self> {
376        Some(match index {
377            0 => DirectedSquareDiagonalAxis::N,
378            1 => DirectedSquareDiagonalAxis::NE,
379            2 => DirectedSquareDiagonalAxis::E,
380            3 => DirectedSquareDiagonalAxis::SE,
381            4 => DirectedSquareDiagonalAxis::S,
382            5 => DirectedSquareDiagonalAxis::SW,
383            6 => DirectedSquareDiagonalAxis::W,
384            7 => DirectedSquareDiagonalAxis::NW,
385            _ => return None,
386        })
387    }
388
389    fn foward(self) -> Self::Direction {
390        self
391    }
392
393    fn backward(self) -> Self::Direction {
394        let i = self.to_index();
395        unsafe { Self::from_index_unchecked(if i < 4 { i + 4 } else { i - 4 }) }
396    }
397
398    fn from_direction(dir: Self::Direction) -> Self {
399        dir
400    }
401}
402
403/// Shape for lattice graph with Square and Diagonal Edge.
404#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
405pub struct SquareDiagonalShape<E = Undirected> {
406    h: usize,
407    v: usize,
408    e: PhantomData<E>,
409}
410
411impl<E> SquareDiagonalShape<E> {
412    /// Create a new graph.
413    pub fn new(h: usize, v: usize) -> Self {
414        Self {
415            h,
416            v,
417            e: PhantomData,
418        }
419    }
420}
421
422impl Shape for SquareDiagonalShape {
423    type Axis = SquareDiagonalAxis;
424    type Coordinate = SquareOffset;
425    type OffsetConvertError = ();
426    type CoordinateMoveError = ();
427
428    fn horizontal(&self) -> usize {
429        self.h
430    }
431
432    fn vertical(&self) -> usize {
433        self.v
434    }
435
436    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, Self::OffsetConvertError> {
437        if coord.0.horizontal < self.horizontal() && coord.0.vertical < self.vertical() {
438            Ok(coord.0)
439        } else {
440            Err(())
441        }
442    }
443
444    unsafe fn to_offset_unchecked(&self, coord: Self::Coordinate) -> Offset {
445        coord.0
446    }
447
448    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate {
449        SquareOffset(offset)
450    }
451
452    fn move_coord(
453        &self,
454        coord: Self::Coordinate,
455        dir: DirectedSquareDiagonalAxis,
456    ) -> Result<Self::Coordinate, Self::CoordinateMoveError> {
457        let offset = coord.0;
458        match dir {
459            DirectedSquareDiagonalAxis::N => offset.add_y(1).check_y(self.vertical()),
460            DirectedSquareDiagonalAxis::NE => offset
461                .add_x(1)
462                .check_x(self.horizontal())
463                .and_then(|o| o.add_y(1).check_y(self.vertical())),
464            DirectedSquareDiagonalAxis::E => offset.add_x(1).check_x(self.horizontal()),
465            DirectedSquareDiagonalAxis::SE => offset
466                .add_x(1)
467                .check_x(self.horizontal())
468                .and_then(|o| o.sub_y(1)),
469
470            DirectedSquareDiagonalAxis::S => offset.sub_y(1),
471            DirectedSquareDiagonalAxis::SW => offset.sub_x(1).and_then(|o| o.sub_y(1)),
472            DirectedSquareDiagonalAxis::W => offset.sub_x(1),
473            DirectedSquareDiagonalAxis::NW => offset
474                .sub_x(1)
475                .and_then(|o| o.add_y(1).check_y(self.vertical())),
476        }
477        .map(SquareOffset)
478        .ok_or(())
479    }
480}
481
482impl Shape for SquareDiagonalShape<Directed> {
483    type Axis = DirectedSquareDiagonalAxis;
484    type Coordinate = SquareOffset;
485    type OffsetConvertError = ();
486    type CoordinateMoveError = ();
487
488    fn horizontal(&self) -> usize {
489        self.h
490    }
491
492    fn vertical(&self) -> usize {
493        self.v
494    }
495
496    fn to_offset(&self, coord: Self::Coordinate) -> Result<Offset, Self::OffsetConvertError> {
497        if coord.0.horizontal < self.horizontal() && coord.0.vertical < self.vertical() {
498            Ok(coord.0)
499        } else {
500            Err(())
501        }
502    }
503
504    unsafe fn to_offset_unchecked(&self, coord: Self::Coordinate) -> Offset {
505        coord.0
506    }
507
508    fn offset_to_coordinate(&self, offset: Offset) -> Self::Coordinate {
509        SquareOffset(offset)
510    }
511
512    fn move_coord(
513        &self,
514        coord: Self::Coordinate,
515        dir: DirectedSquareDiagonalAxis,
516    ) -> Result<Self::Coordinate, Self::CoordinateMoveError> {
517        let offset = coord.0;
518        match dir {
519            DirectedSquareDiagonalAxis::N => offset.add_y(1).check_y(self.vertical()),
520            DirectedSquareDiagonalAxis::NE => offset
521                .add_x(1)
522                .check_x(self.horizontal())
523                .and_then(|o| o.add_y(1).check_y(self.vertical())),
524            DirectedSquareDiagonalAxis::E => offset.add_x(1).check_x(self.horizontal()),
525            DirectedSquareDiagonalAxis::SE => offset
526                .add_x(1)
527                .check_x(self.horizontal())
528                .and_then(|o| o.sub_y(1)),
529
530            DirectedSquareDiagonalAxis::S => offset.sub_y(1),
531            DirectedSquareDiagonalAxis::SW => offset.sub_x(1).and_then(|o| o.sub_y(1)),
532            DirectedSquareDiagonalAxis::W => offset.sub_x(1),
533            DirectedSquareDiagonalAxis::NW => offset
534                .sub_x(1)
535                .and_then(|o| o.add_y(1).check_y(self.vertical())),
536        }
537        .map(SquareOffset)
538        .ok_or(())
539    }
540}
541
542#[cfg(test)]
543mod tests {
544    use super::*;
545    use petgraph::visit::*;
546
547    type SquareGraph<N, E> = super::SquareGraphAbstract<N, E>;
548
549    #[test]
550    fn gen_test() {
551        let sq = SquareGraph::new_with(
552            SquareShape::new(4, 3),
553            |SquareOffset(Offset {
554                 horizontal: x,
555                 vertical: y,
556             })| x + 2 * y,
557            |SquareOffset(Offset {
558                 horizontal: x,
559                 vertical: y,
560             }),
561             _d| (x + 2 * y) as i32,
562        );
563        assert_eq!(sq.s.horizontal(), 4);
564        assert_eq!(sq.s.vertical(), 3);
565        assert_eq!(sq.node_weight((0, 0).into()), Some(&0));
566        assert_eq!(sq.node_weight((0, 1).into()), Some(&2));
567        assert_eq!(sq.node_weight((1, 0).into()), Some(&1));
568        assert_eq!(sq.node_weight((2, 0).into()), Some(&2));
569        assert_eq!(sq.node_weight((3, 0).into()), Some(&3));
570        assert_eq!(sq.node_weight((4, 0).into()), None);
571        assert_eq!(sq.node_weight((0, 2).into()), Some(&4));
572        assert_eq!(sq.node_weight((0, 3).into()), None);
573        assert_eq!(
574            sq.edge_weight(((0, 0).into(), SquareAxis::X).into()),
575            Some(&0)
576        );
577        assert_eq!(
578            sq.edge_weight(((0, 2).into(), SquareAxis::X).into()),
579            Some(&4)
580        );
581        assert_eq!(sq.edge_weight(((0, 2).into(), SquareAxis::Y)), None);
582        assert_eq!(sq.edge_weight(((3, 0).into(), SquareAxis::X)), None);
583        assert_eq!(sq.edge_weight(((3, 0).into(), SquareAxis::Y)), Some(&3));
584    }
585
586    #[test]
587    fn node_identifiers() {
588        let sq = SquareGraph::new_with(
589            SquareShape::new(4, 3),
590            |SquareOffset(Offset {
591                 horizontal: x,
592                 vertical: y,
593             })| x + 2 * y,
594            |SquareOffset(Offset {
595                 horizontal: x,
596                 vertical: y,
597             }),
598             _d| Some((x + 2 * y) as i32),
599        );
600        let mut count = 0;
601        for (i, x) in sq.node_identifiers().enumerate() {
602            let x2 = sq.to_index(x);
603            assert_eq!(x2, i);
604            let x3 = sq.from_index(x2);
605            assert_eq!(x, x3);
606            count += 1;
607        }
608        assert_eq!(count, 12);
609    }
610
611    #[test]
612    fn neighbors() {
613        let sq = SquareGraph::new_with(
614            SquareShape::new(3, 5),
615            |SquareOffset(Offset {
616                 horizontal: x,
617                 vertical: y,
618             })| x + 2 * y,
619            |SquareOffset(Offset {
620                 horizontal: x,
621                 vertical: y,
622             }),
623             _d| Some((x + 2 * y) as i32),
624        );
625
626        let v00 = sq.neighbors((0, 0).into());
627        debug_assert!(v00.eq([(1, 0), (0, 1)]));
628
629        let v04 = sq.neighbors((0, 4).into());
630        debug_assert!(v04.eq([(1, 4), (0, 3)]));
631
632        let v20 = sq.neighbors((2, 0).into());
633        debug_assert!(v20.eq([(2, 1), (1, 0)]));
634
635        let v24 = sq.neighbors((2, 4).into());
636        debug_assert!(v24.eq([(1, 4), (2, 3)]));
637
638        let v12 = sq.neighbors((1, 2).into());
639        debug_assert!(v12.eq([(2, 2), (1, 3), (0, 2), (1, 1)]));
640    }
641
642    #[test]
643    fn edges() {
644        let sq = SquareGraph::new_with(
645            SquareShape::new(3, 5),
646            |SquareOffset(Offset {
647                 horizontal: x,
648                 vertical: y,
649             })| x + 2 * y,
650            |SquareOffset(Offset {
651                 horizontal: x,
652                 vertical: y,
653             }),
654             _d| (x + 2 * y) as i32,
655        );
656
657        debug_assert!(sq
658            .edges((0, 0).into())
659            .map(|e| e.target())
660            .eq([(1, 0), (0, 1)]));
661
662        debug_assert!(sq.edges((0, 0).into()).map(|e| e.edge_weight).eq(&[0, 0]));
663        debug_assert!(sq
664            .edges((1, 1).into())
665            .map(|e| e.edge_weight)
666            .eq(&[3, 3, 2, 1]));
667
668        debug_assert!(sq.edges((1, 2).into()).map(|e| e.target()).eq([
669            (2, 2),
670            (1, 3),
671            (0, 2),
672            (1, 1)
673        ]));
674    }
675
676    #[test]
677    fn astar() {
678        let sq = SquareGraph::new_with(
679            SquareShape::new(4, 3),
680            |SquareOffset(Offset {
681                 horizontal: x,
682                 vertical: y,
683             })| x + 2 * y,
684            |SquareOffset(Offset {
685                 horizontal: x,
686                 vertical: y,
687             }),
688             d| { (x + 2 * y) as i32 * if d == SquareAxis::X { 1 } else { 3 } },
689        );
690
691        let x = petgraph::algo::astar(
692            &sq,
693            (0, 0).into(),
694            |x| x == (2, 1),
695            |e| *e.weight(),
696            |x| (x.0.horizontal as i32 - 2).abs() + (x.0.vertical as i32 - 1).abs(),
697        );
698        assert!(x.is_some());
699        let (d, p) = x.unwrap();
700        assert_eq!(d, 5);
701        assert_eq!(p, [(0, 0), (0, 1), (1, 1), (2, 1)]);
702
703        let x = petgraph::algo::astar(
704            &sq,
705            (2, 1).into(),
706            |x| x == (0, 0),
707            |e| *e.weight(),
708            |x| (x.0.horizontal as i32).abs() + (x.0.vertical as i32).abs(),
709        );
710        assert!(x.is_some());
711        let (d, p) = x.unwrap();
712        assert_eq!(d, 5);
713        assert_eq!(p, [(2, 1), (1, 1), (0, 1), (0, 0)])
714    }
715}
lattice_graph/lattice_abstract/square.rs

lattice_graph/lattice_abstract/
square.rs
