前の章で紹介した幅優先探索をRustで実装していきます。
隣接する頂点を返す関数をトレイトとして定義します。こうすることで探索対象がグラフとしての性質を満たすものであればなんでも探索できるようになります。テスト用のデータを入力することができるようになるので、アルゴリズムの実装が正しいかを試すことができるようになります。
アルゴリズム自体は訪問した頂点を返すイテレータとして実装したいと思います。mini-crawlerの実装ではウェブページを訪問する際に待機時間を挟みたいので、一つの頂点を訪問したら呼び出し側のコードに制御を戻したいのです。また、イテレータにすることで訪問する頂点の個数を制御できます。
幅優先探索の実装はsrc/crawler.rsに書くことにします。このファイルをコンパイルの対象にするために、src/lib.rsに
pub mod crawler;
を書き加えておきましょう。
trait AdjacentNodes
頂点vに隣接する頂点を返す関数adjacent_nodesを定義します。頂点の型はトレイトの関連型としておきます。関連型はあとで具体的な実装を作るときに指定する必要があります。
pub trait AdjacentNodes {
type Node;
fn adjacent_nodes(&self, v: &Self::Node) -> Vec<Self::Node>;
}
src/crawler.rsのtestモジュールに隣接する頂点をVecで保持する構造体AdjVecを作っておきます。AdjVecはusizeの値を頂点として、i番目の要素に頂点iに隣接する頂点を格納したVecを保持します。
このAdjVecにAdjacentNodesトレイトを実装します。関数adjacent_nodesではVecのgetメソッドで隣接する頂点を取り出します。この戻り値はOption<&Vec<usize>>になるのでclonedメソッドを呼んでコピーします。最後に中身がNoneだった場合は空のVecを返すためにunwrap_orを呼びます。
#[cfg(test)]
mod test {
use super::*;
struct AdjVec(Vec<Vec<usize>>);
impl AdjacentNodes for AdjVec {
type Node = usize;
fn adjacent_nodes(&self, v: &Self::Node) -> Vec<Self::Node> {
self.0.get(*v)
.cloned()
.unwrap_or(Vec::new())
}
}
}
struct Crawler
さて、幅優先探索を実装する構造体を設計しましょう。名前はCrawlerとしましょう。コンストラクタはAdjacentNodesトレイトを実装したオブジェクトと頂点を受け取るようにします。そしてCrawlerにはIteratorトレイトを実装します。
使い方としては以下のコードのような感じでしょうか。下のコードは今はコンパイルできませんが、このコードが動くようにプログラムを書いていきましょう。
fn test_bfs() {
let graph = AdjVec(vec![
vec![1, 2],
vec![0, 3],
vec![3],
vec![2, 0]
]);
let bfs = Crawler::new(&graph, 0);
let nodes: Vec<usize> = bfs.iter().collect();
assert_eq!(nodes, vec![0, 1, 2, 3]);
}
幅優先探索の実装
それでは幅優先探索を実装していきましょう。まずは保持しなければならないデータを考えます。前の章で紹介したアルゴリズムを再度載せます。ただし、訪問するページ数の上限に関する記述は削除します。なぜならイテレータとして実装するので呼び出し側から制御できるからです。
- 入力
- 頂点に対して隣接する頂点の集合を返す関数
T - 探索を始める頂点
a
- 頂点に対して隣接する頂点の集合を返す関数
- 出力
- 訪問したページのリスト
- 手順
- キュー
Visitの末尾にaを挿入する。 - キュー
Visitが空ならばハッシュVisitedを出力して終了する。 - キュー
Visitの先頭から頂点vを取り出す。 - 頂点
vがハッシュVisitedに含まれていれば、手順2にジャンプする。 -
T(v)の頂点のうち、ハッシュVisitedに含まれないものをキューVisitの末尾に挿入する。 -
vをハッシュVisitedに挿入する。 - 手順2にジャンプする。
- キュー
頂点を取り出すグラフはAdjacentNodesトレイトを実装したオブジェクトへの参照を持つことにします。なので型パラメータに参照のライフタイムが必要になります。
幅優先探索の実装に必要なデータ構造はVisitに使うキューとVisitedに使うハッシュでした。それぞれVecDequeとHashSetが使えます。したがって、Crawlerの宣言は次のようになります。VecDequeとHashSetのパラメタにはAdjacentNodes::Nodeを入れる必要があるので、Gにトレイト制約を付けています。
pub struct Crawler<'a, G: AdjacentNodes> {
graph: &'a G,
visit: VecDeque<<G as AdjacentNodes>::Node>,
visited: HashSet<<G as AdjacentNodes>::Node>,
}
次にコンストラクタを作りましょう。受け取った頂点をvisitに挿入するのを忘れないようにしておきましょう。
<G as AdjacentNodes>::Nodeに複数のトレイト制約を付けました。visitから取り出した頂点をvisitedに挿入してイテレータから返すために、Cloneトレイトが必要になります。なぜなら、HashSetは保持するデータを所有する必要があり、戻り値も所有権が呼び出し側に移るため、取り出した頂点のコピーが必要になるからです。また、HashSetのメソッドを呼び出すために、Hashトレイト、Eqトレイト、Borrowトレイトが必要になります。
impl<'a, G> Crawler<'a, G>
where
G: AdjacentNodes,
<G as AdjacentNodes>::Node: Clone + Hash + Eq + Borrow<<G as AdjacentNodes>::Node>,
{
pub fn new(graph: &'a G, start: <G as AdjacentNodes>::Node) -> Self {
let mut visit = VecDeque::new();
let visited = HashSet::new();
visit.push_back(start);
Self {
graph: graph,
visit: visit,
visited: visited,
}
}
}
それではIteratorトレイトの実装に取り掛かりましょう。
まずは、必要な宣言を書いてしまいます。そして、nextメソッドの中には、キューvisitの要素を取り出し続けるループを書きます。ループが終わった後にはNoneを返すようにします。
VecDequeから要素を取り出すにはpop_frontメソッドを呼び出します。このメソッドはOption<T>型のオブジェクトを返すので、while letを使うことでキューが空になるまでループすることができます。
ここでループが必要になるのはvisitから取り出した頂点がすでにvisitedに含まれていた場合に、隣接する頂点をvisitに挿入する操作をスキップする必要があるからです。ループを抜けたらvisitは空になっているのでもう訪れるべき頂点はありません。なのでNoneを返します。
impl<'a, G> Iterator for Crawler<'a, G>
where
G: AdjacentNodes,
<G as AdjacentNodes>::Node: Clone + Hash + Eq + Borrow<<G as AdjacentNodes>::Node>,
{
type Item = <G as AdjacentNodes>::Node;
fn next(&mut self) -> Option<Self::Item> {
while let Some(v) = self.visit.pop_front() {
}
None
}
}
visitから取り出した頂点が訪問済みであれば処理をスキップするコードを書きます。HashSet構造体のcontainsメソッドを呼び出すことで、ハッシュに要素が含まれるかどうかを調べることができます。ここでは、self.visited.contains(&v)を呼び出すことで、visitから取り出した頂点vがvisitedに含まれるかどうかを調べます。そして、含まれていた場合はcontinueで後の処理をスキップします。
impl<'a, G> Iterator for Crawler<'a, G>
where
G: AdjacentNodes,
<G as AdjacentNodes>::Node: Clone + Hash + Eq + Borrow<<G as AdjacentNodes>::Node>,
{
type Item = <G as AdjacentNodes>::Node;
fn next(&mut self) -> Option<Self::Item> {
while let Some(v) = self.visit.pop_front() {
if self.visited.contains(&v) {
continue;
}
}
None
}
}
次に、頂点vに隣接する頂点を取得してキューvisitに挿入します。まず、self.graphのadjacent_nodesメソッドを呼び出して隣接する頂点を取得します。このメソッドの戻り値は頂点のVecでした。
そして、隣接する頂点のVecの各要素をinto_iterメソッドで取り出していきます。隣接する頂点をキューvisitに挿入したいので所有権を奪うinto_iterを使いました。隣接する頂点uがvisitedに含まれていなければvisitに挿入します。
impl<'a, G> Iterator for Crawler<'a, G>
where
G: AdjacentNodes,
<G as AdjacentNodes>::Node: Clone + Hash + Eq + Borrow<<G as AdjacentNodes>::Node>,
{
type Item = <G as AdjacentNodes>::Node;
fn next(&mut self) -> Option<Self::Item> {
while let Some(v) = self.visit.pop_front() {
if self.visited.contains(&v) {
continue;
}
let adj = self.graph.adjacent_nodes(&v);
for u in adj.into_iter() {
if !self.visited.contains(&u) {
self.visit.push_back(u);
}
}
}
None
}
}
あとは頂点vのコピーをvisitedに挿入してからreturnでSome(v)を返せば、イテレータの実装は完了です。
impl<'a, G> Iterator for Crawler<'a, G>
where
G: AdjacentNodes,
<G as AdjacentNodes>::Node: Clone + Hash + Eq + Borrow<<G as AdjacentNodes>::Node>,
{
type Item = <G as AdjacentNodes>::Node;
fn next(&mut self) -> Option<Self::Item> {
while let Some(v) = self.visit.pop_front() {
if self.visited.contains(&v) {
continue;
}
let adj = self.graph.adjacent_nodes(&v);
for u in adj.into_iter() {
if !self.visited.contains(&u) {
self.visit.push_back(u);
}
}
self.visited.insert(v.clone());
return Some(v);
}
None
}
}
テスト
最後に、testモジュールにテストコードを書いてcargo testを実行してみましょう。テストに通ることが確認できるはずです。これでCrawlerは完成です。
#[test]
fn bfs() {
let graph = AdjVec(vec![
vec![1, 2],
vec![0, 3],
vec![3],
vec![2, 0]
]);
let crawler = Crawler::new(&graph, 0);
let nodes: Vec<usize> = crawler.collect();
assert_eq!(nodes, vec![0, 1, 2, 3]);
}
この章で作成したファイル
演習
-
次の隣接関係を持つグラフに、頂点
0をスタートとして幅優先探索を適用すると、0, 1, 2, 4, 3の順で訪問することを手計算とCrawlerで確かめてみてください。頂点 隣接する頂点 0 1 1 0, 2, 4 2 0, 3 3 0 4 0