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
37use std::marker::PhantomData;
38
39/// [`Graph`]にもたせる辺の満たすトレイト。
40pub trait EdgeTrait {
41    /// 辺の重みの型
42    type Weight;
43    /// 辺の始点
44    fn from(&self) -> usize;
45    /// 辺の終点
46    fn to(&self) -> usize;
47    /// 辺の重み
48    fn weight(&self) -> Self::Weight;
49    /// 逆辺
50    fn rev(self) -> Self;
51}
52
53/// グラフの辺
54#[derive(Debug, Clone)]
55pub struct Edge<T, I> {
56    /// 辺の始点
57    pub from: usize,
58    /// 辺の終点
59    pub to: usize,
60    /// 辺の重み
61    pub weight: T,
62    /// 辺の番号など
63    pub index: I,
64}
65
66impl<T, I> Edge<T, I> {
67    /// `from`から`to`への重さ`weight`、辺番号`index`をもつ有向辺を作る。
68    pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
69        Self {
70            from,
71            to,
72            weight,
73            index,
74        }
75    }
76}
77
78impl<T: Clone, I> EdgeTrait for Edge<T, I> {
79    type Weight = T;
80    #[inline]
81    fn from(&self) -> usize {
82        self.from
83    }
84    #[inline]
85    fn to(&self) -> usize {
86        self.to
87    }
88    #[inline]
89    fn weight(&self) -> Self::Weight {
90        self.weight.clone()
91    }
92    fn rev(mut self) -> Self {
93        std::mem::swap(&mut self.from, &mut self.to);
94        self
95    }
96}
97
98/// グラフの辺の有向・無向の情報をもたせるためのトレイト。
99pub trait Direction {}
100/// 有向辺をもつ。
101#[derive(Debug, Clone)]
102pub struct Directed;
103/// 無向辺をもつ。
104#[derive(Debug, Clone)]
105pub struct Undirected;
106impl Direction for Directed {}
107impl Direction for Undirected {}
108
109/// グラフのノード
110#[derive(Clone, Debug)]
111pub struct GraphNode<E> {
112    /// 接続する辺
113    pub edges: Vec<E>,
114}
115
116impl<E: EdgeTrait> IntoIterator for GraphNode<E> {
117    type Item = E;
118    type IntoIter = std::vec::IntoIter<Self::Item>;
119
120    fn into_iter(self) -> Self::IntoIter {
121        self.edges.into_iter()
122    }
123}
124
125/// グラフ
126#[derive(Debug, Clone)]
127pub struct Graph<D, E> {
128    nodes: Vec<GraphNode<E>>,
129    __phantom: PhantomData<D>,
130}
131
132impl<D: Direction, E: EdgeTrait + Clone> Graph<D, E> {
133    /// 頂点数が`size`の空の`Graph`を構築する。
134    pub fn new(size: usize) -> Self {
135        Graph {
136            nodes: vec![GraphNode { edges: vec![] }; size],
137            __phantom: PhantomData,
138        }
139    }
140}
141
142impl<E: EdgeTrait + Clone> Graph<Directed, E> {
143    /// 有向グラフに辺を追加する。
144    pub fn add(&mut self, e: E) {
145        self.nodes[e.from()].edges.push(e);
146    }
147}
148
149impl<E: EdgeTrait + Clone> Extend<E> for Graph<Directed, E> {
150    fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
151        iter.into_iter().for_each(|e| self.add(e));
152    }
153}
154
155impl<E: EdgeTrait + Clone> Graph<Undirected, E> {
156    /// 無向グラフに辺を追加する。
157    pub fn add(&mut self, e: E) {
158        self.nodes[e.from()].edges.push(e.clone());
159        self.nodes[e.to()].edges.push(e.rev());
160    }
161}
162
163impl<E: EdgeTrait + Clone> Extend<E> for Graph<Undirected, E> {
164    fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
165        iter.into_iter().for_each(|e| self.add(e));
166    }
167}
168
169impl<D, E> Graph<D, E> {
170    /// 各頂点の[`GraphNode`]への参照のイテレータを返す。
171    pub fn nodes_iter(&self) -> impl Iterator<Item = &GraphNode<E>> {
172        self.nodes.iter()
173    }
174
175    /// `i`番目の頂点の[`GraphNode`]への参照を返す。
176    pub fn node_of(&self, i: usize) -> &GraphNode<E> {
177        &self.nodes[i]
178    }
179
180    /// グラフの頂点数を返す。
181    pub fn len(&self) -> usize {
182        self.nodes.len()
183    }
184
185    /// グラフの頂点数が`0`ならば`true`を返す。
186    pub fn is_empty(&self) -> bool {
187        self.nodes.is_empty()
188    }
189}
haar_lib/graph/mod.rs

haar_lib/graph/
mod.rs
