haar_lib/graph/
mod.rs

1//! グラフ一般に関するもの
2
3pub mod articulation_points;
4pub mod biconnected;
5pub mod bridges;
6pub mod lowlink;
7pub mod scc;
8pub mod two_edge;
9
10pub mod functional_graph;
11pub mod pseudo_tree;
12
13pub mod bellman_ford;
14pub mod bfs;
15pub mod dijkstra;
16pub mod warshall_floyd;
17pub mod yen;
18
19pub mod cycle;
20pub mod detect_cycle;
21pub mod eulerian;
22
23pub mod bipartite;
24
25pub mod enumerate_triangles;
26pub mod max_independent_set;
27
28pub mod chu_liu_edmonds;
29pub mod kruskal;
30pub mod prim;
31
32pub mod tsort;
33
34pub mod chinese_postman;
35pub mod tsp;
36
37pub mod chromatic_number;
38
39pub mod matrix_tree;
40
41use std::marker::PhantomData;
42
43/// [`Graph`]にもたせる辺の満たすトレイト。
44pub trait EdgeTrait {
45    /// 辺の重みの型
46    type Weight;
47    /// 辺の始点
48    fn from(&self) -> usize;
49    /// 辺の終点
50    fn to(&self) -> usize;
51    /// 辺の重み
52    fn weight(&self) -> Self::Weight;
53    /// 逆辺
54    fn rev(self) -> Self;
55}
56
57/// グラフの辺
58#[derive(Debug, Clone, Hash, PartialEq, Eq)]
59pub struct Edge<T, I> {
60    /// 辺の始点
61    pub from: usize,
62    /// 辺の終点
63    pub to: usize,
64    /// 辺の重み
65    pub weight: T,
66    /// 辺の番号など
67    pub index: I,
68}
69
70impl<T, I> Edge<T, I> {
71    /// `from`から`to`への重さ`weight`、辺番号`index`をもつ有向辺を作る。
72    pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
73        Self {
74            from,
75            to,
76            weight,
77            index,
78        }
79    }
80}
81
82impl<T: Clone, I> EdgeTrait for Edge<T, I> {
83    type Weight = T;
84    #[inline]
85    fn from(&self) -> usize {
86        self.from
87    }
88    #[inline]
89    fn to(&self) -> usize {
90        self.to
91    }
92    #[inline]
93    fn weight(&self) -> Self::Weight {
94        self.weight.clone()
95    }
96    fn rev(mut self) -> Self {
97        std::mem::swap(&mut self.from, &mut self.to);
98        self
99    }
100}
101
102/// グラフの辺の有向・無向の情報をもたせるためのトレイト。
103pub trait Direction {}
104/// 有向辺をもつ。
105#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
106pub struct Directed;
107/// 無向辺をもつ。
108#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
109pub struct Undirected;
110impl Direction for Directed {}
111impl Direction for Undirected {}
112
113/// グラフのノード
114#[derive(Clone, Debug)]
115pub struct GraphNode<E> {
116    /// 接続する辺
117    pub edges: Vec<E>,
118}
119
120impl<E: EdgeTrait> GraphNode<E> {
121    /// 隣接辺を列挙するイテレータを返す。
122    pub fn neighbors(&self) -> impl DoubleEndedIterator<Item = &E> {
123        self.edges.iter()
124    }
125
126    /// 隣接辺の個数を返す。
127    pub fn neighbors_size(&self) -> usize {
128        self.edges.len()
129    }
130}
131
132impl<E: EdgeTrait> IntoIterator for GraphNode<E> {
133    type Item = E;
134    type IntoIter = std::vec::IntoIter<Self::Item>;
135
136    fn into_iter(self) -> Self::IntoIter {
137        self.edges.into_iter()
138    }
139}
140
141impl<'a, E: EdgeTrait> IntoIterator for &'a GraphNode<E> {
142    type Item = &'a E;
143    type IntoIter = std::slice::Iter<'a, E>;
144
145    fn into_iter(self) -> Self::IntoIter {
146        self.edges.iter()
147    }
148}
149
150/// グラフ
151#[derive(Debug, Clone)]
152pub struct Graph<D, E> {
153    nodes: Vec<GraphNode<E>>,
154    __phantom: PhantomData<D>,
155}
156
157impl<D: Direction, E: EdgeTrait + Clone> Graph<D, E> {
158    /// 頂点数が`size`の空の`Graph`を構築する。
159    pub fn new(size: usize) -> Self {
160        Self {
161            nodes: vec![GraphNode { edges: vec![] }; size],
162            __phantom: PhantomData,
163        }
164    }
165}
166
167impl<E: EdgeTrait + Clone> Graph<Directed, E> {
168    /// 有向グラフに辺を追加する。
169    pub fn add(&mut self, e: E) {
170        self.nodes[e.from()].edges.push(e);
171    }
172}
173
174impl<E: EdgeTrait + Clone> Extend<E> for Graph<Directed, E> {
175    fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
176        iter.into_iter().for_each(|e| self.add(e));
177    }
178}
179
180impl<E: EdgeTrait + Clone> Graph<Undirected, E> {
181    /// 無向グラフに辺を追加する。
182    pub fn add(&mut self, e: E) {
183        self.nodes[e.from()].edges.push(e.clone());
184        self.nodes[e.to()].edges.push(e.rev());
185    }
186}
187
188impl<E: EdgeTrait + Clone> Extend<E> for Graph<Undirected, E> {
189    fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
190        iter.into_iter().for_each(|e| self.add(e));
191    }
192}
193
194impl<D, E> Graph<D, E> {
195    /// 各頂点の[`GraphNode`]への参照のイテレータを返す。
196    pub fn nodes_iter(&self) -> impl Iterator<Item = &GraphNode<E>> {
197        self.nodes.iter()
198    }
199
200    /// `i`番目の頂点の[`GraphNode`]への参照を返す。
201    pub fn node_of(&self, i: usize) -> &GraphNode<E> {
202        &self.nodes[i]
203    }
204
205    /// グラフの頂点数を返す。
206    pub fn len(&self) -> usize {
207        self.nodes.len()
208    }
209
210    /// グラフの頂点数が`0`ならば`true`を返す。
211    pub fn is_empty(&self) -> bool {
212        self.nodes.is_empty()
213    }
214}
haar_lib/graph/mod.rs

haar_lib/graph/
mod.rs
