haar_lib/graph/eulerian/
undirected.rs

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

haar_lib/graph/eulerian/
undirected.rs
