haar_lib/graph/eulerian/
directed.rs

1//! 有向グラフの(準)Eulerグラフの判定
2use crate::graph::*;
3
4/// 有向グラフでの一筆書き
5#[derive(Clone)]
6pub struct DirectedEulerianTrail<E: EdgeTrait> {
7    size: usize,
8    edge_count: usize,
9    graph: Vec<Vec<E>>,
10    indeg: Vec<i32>,
11    outdeg: Vec<i32>,
12}
13
14impl<E: EdgeTrait + Clone> DirectedEulerianTrail<E> {
15    /// 頂点数`size`のグラフを用意する。
16    pub fn new(size: usize) -> Self {
17        Self {
18            size,
19            edge_count: 0,
20            graph: vec![vec![]; size],
21            indeg: vec![0; size],
22            outdeg: vec![0; size],
23        }
24    }
25
26    /// 有向辺`e`を追加する。
27    pub fn add_edge(&mut self, e: E) {
28        self.indeg[e.to()] += 1;
29        self.outdeg[e.from()] += 1;
30        self.graph[e.from()].push(e);
31        self.edge_count += 1;
32    }
33
34    fn dfs(&mut self, cur: usize, vs: &mut Vec<usize>, es: &mut Vec<E>) {
35        while let Some(e) = self.graph[cur].pop() {
36            let next = e.to();
37            self.dfs(next, vs, es);
38            es.push(e);
39        }
40
41        vs.push(cur);
42    }
43
44    /// グラフが一筆書き可能なら、その頂点列と辺列を`Some`に包んで返す。
45    pub fn solve(mut self) -> Option<(Vec<usize>, Vec<E>)> {
46        let mut in_count = 0;
47        let mut out_count = 0;
48        let mut start = None;
49
50        for i in 0..self.size {
51            match self.outdeg[i] - self.indeg[i] {
52                0 => {}
53                1 => {
54                    out_count += 1;
55                    start = Some(i);
56                }
57                -1 => in_count += 1,
58                _ => return None,
59            }
60            if start.is_none() && !self.graph[i].is_empty() {
61                start = Some(i);
62            }
63        }
64
65        let start = start.unwrap_or(0);
66
67        if !(in_count == 0 && out_count == 0 || in_count == 1 && out_count == 1) {
68            return None;
69        }
70
71        let mut vs = vec![];
72        let mut es = vec![];
73        self.dfs(start, &mut vs, &mut es);
74
75        (vs.len() == self.edge_count + 1 && es.len() == self.edge_count).then(|| {
76            vs.reverse();
77            es.reverse();
78
79            (vs, es)
80        })
81    }
82}
haar_lib/graph/eulerian/directed.rs

haar_lib/graph/eulerian/
directed.rs
