haar_lib/grid/
to_graph.rs

1//! グリッドをグラフに変換する
2use crate::{graph::*, grid::*};
3
4/// グリッドをグラフに変換する
5///
6/// `index`はグリッド上の位置をグラフの頂点番号に対応させる関数。
7///
8/// `edge`はグリッド上のマス目からマス目への辺を与える関数。
9/// 通行不可の場合は`None`を返し、通行可能ならば、そのコストを`Some`に包んで返すこと。
10pub fn grid_to_graph<T: Clone>(
11    h: usize,
12    w: usize,
13    dirs: &[Dir],
14    index: impl Fn(Position) -> usize,
15    edge: impl Fn(Position, Position) -> Option<T>,
16) -> Graph<Directed, Edge<T, ()>> {
17    let mut g = Graph::<Directed, _>::new(h * w);
18
19    for i in 0..h {
20        for j in 0..w {
21            let p = Position::new(i, j, h, w);
22
23            for d in dirs {
24                let q = p.mov(*d);
25
26                if let Some(q) = q {
27                    if let Some(c) = edge(p, q) {
28                        let e = Edge::new(index(p), index(q), c, ());
29                        g.add(e);
30                    }
31                }
32            }
33        }
34    }
35
36    g
37}