この記事について
何が書いてあるか
rustのpetgraphについて、基礎的な使い方を書きます。
基礎的とは、以下のことを指しています。
- グラフ構造体の作り方(有向、無効)
- 作ったグラフに対しての探索
- dijkstra、二部グラフ判定、閉路検出
また、グラフについての基礎的な知識については、この記事では書きません。
どんな人を対象とした記事か
単純にはpetgraphの使い方が何も分からない人を対象としています。AtCoderの色でいくと灰色から茶色くらいだと思います。(2023/01/18現在、私が茶色寄りの灰色だからです。)緑色、水色になるためには必要になる知識だと思います(ソース)。
グラフについての基礎的な知識は持っている人を対象としています。
モチベーション
rustのpetgraphに関する記事はいくつかありますが、それらを読んでも理解できなかったためです(記事が悪いのではなく、私の知識不足の部分が大きいと思います)。他の誰かが自分のように遠回りをしなくてもいいように。
petgraphとは
グラフの構造を提供してくれるクレートです。
また、グラフに作用するいくつかのアルゴリズムも提供してくれます。
グラフの作成
petgraphのグラフインスタンスの作成方法は大きく分けて、以下の2つあります。
- nodeとedgeをそれぞれ追加
- edgeのみ追加(nodeは自動作成)
グラフを作成する際に、グラフが有向か無向かを指定します。また、nodeとedgeの重みの型も指定する必要があります。
nodeとedgeをそれぞれ追加する方法
まずnodeとedgeをそれぞれ追加する方法について書いていきます。
重みなし有向グラフの場合
まず、重みなしの有向グラフを作成します。有向グラフにおいて、nodeとedgeをそれぞれ追加するには以下の手順で行います。
- 有向グラフのインスタンスを作成
- nodeを追加
- edgeを追加
use petgraph;
fn main() {
let mut directed_graph = petgraph::Graph::<(),(),petgraph::Directed>::new();
//let mut directed_graph = petgraph::Graph::<(),()>::new(); defaultでDirectedのため、この形でも可
let a = directed_graph.add_node(());
let b = directed_graph.add_node(());
directed_graph.add_edge(a,b,());
}コードの説明です。
Graph::<(),(),petgraph::Directed>について
<>内がおそらく「??」となってしまうのではないでしょうか(私がそうだっただけ…?)。<>内はグラフのインスタンスを作成する際に必要な3つの項目に対応しています。1つ目はnodeの重みの型。2つ目はedgeの重みの型。3つ目は有向グラフか無向グラフかです。この例では空のタプル(ユニット)を使って重みがないことを示しています。重みありの場合については後述します。
add_nodeについて
グラフインスタンスのメソッドaddnode()でnodeを追加します。addnodeは引数にnodeの重みをとります。今回はグラフ作成の際にnodeの重みに、ユニットを指定したので、ユニットにします。この際、これらのnodeは内部でインデックスが割り振られます。0から順に割り振られていくので、aは0、bは1になります。
add_edgeについて
nodeを追加したら、「それらがどのように繋がっているか」という情報をグラフに追加する必要があります。ここではaからbへ繋がっているということを表すため、引数を(a,b,())にしています。3つ目の引数はedgeの重みです。nodeと同様、グラフ作成の際にユニットをしてしたので、ユニットにします。
グラフ描画
ここでは詳しく書きませんが、petgraphには、graphviz(グラフ描画用ソフト)と連携してグラフを作成することができます。この例でグラフを描画してみると、以下のようになります。nodeの中心にはインデックスを書いています。
重みあり有向グラフの場合
重みがある場合、nodeの重みの型とedgeの重みの型を指定する必要があります。
以下、nodeの重みにusize,edgeの重みにi32を指定した場合のコードです。
use petgraph;
fn main() {
let mut directed_graph = petgraph::Graph::<usize,i32,petgraph::Directed>::new();
let a = directed_graph.add_node(4);
let b = directed_graph.add_node(10);
directed_graph.add_edge(a,b, -3);
}add_nodeの引数にはusizeを、add_edgeの3つ目の引数にはi32の引数を設定します。
グラフ描画
先ほどと同じようにグラフを描画しています。nodeの中心に書いてあるのはインデックスです。重みがあってもなくても、add_nodeした際に内部的にはインデックスで扱います。
nodeの中心にインデックスを表示させる代わりに、重みを表示させてみます。ついでにedgeの重みも表示させてみます。先ほど指定した数字が表示されているのがわかります。
また、重みの型は任意です。文字でもいいですし、自分で作った構造体型でもいいです。
例えば以下のように書いてみると
use petgraph;
#[derive(Debug)]
struct MyWeight {
weight: usize,
name: String
}
fn main() {
let mut directed_graph = petgraph::Graph::<MyWeight,(),petgraph::Directed>::new();
let my_weight_a = MyWeight{weight:4, name:"a".to_string()};
let my_weight_b = MyWeight{weight:10, name:"b".to_string()};
let a = directed_graph.add_node(my_weight_a);
let b = directed_graph.add_node(my_weight_b);
directed_graph.add_edge(a,b,());
}重みを表示させてグラフ描画してみるとこのようになります。
重みなし無向グラフの場合
無向グラフについても手順は有向グラフと全く同じです。違いはグラフインスタンス作成の際に、無向グラフを指定することです。
- 無向グラフのインスタンスを作成
- nodeを追加
- edgeを追加
use petgraph;
fn main() {
let mut undirected_graph = petgraph::Graph::<(),(),petgraph::Undirected>::new_undirected();
//let mut undirectedgraph = petgraph::graph::UnGraph::<(),()>::new_undirected(); Undirectedを指定する代わりに、こちらを使ってもいい
let a = undirected_graph.add_node(());
let b = undirected_graph.add_node(());
undirected_graph.add_edge(a,b,());
}new_undirected()について
無向グラフを作成するためのnew()はなく、代わりにnew_undirected()を使うようです。
グラフ描画
有向グラフの時とほぼ同じです。違いはedgeが矢印ではなくなったことのみです。
重みあり無向グラフの場合
先ほどと同じで、有向グラフとの違いはインスタンス作成時のみです。
use petgraph;
fn main() {
let mut undirected_graph = petgraph::Graph::<usize,i32,petgraph::Undirected>::new_undirected();
let a = undirected_graph.add_node(4);
let b = undirected_graph.add_node(10);
undirected_graph.add_edge(a,b, -3);
}
無向グラフの場合も重みは任意の型に設定することができます。
use petgraph;
#[derive(Debug)]
struct MyWeight {
weight: usize,
name: String
}
fn main() {
let mut undirected_graph = petgraph::Graph::<MyWeight,(),petgraph::Undirected>::new_undirected();
let my_weight_a = MyWeight{weight:4, name:"a".to_string()};
let my_weight_b = MyWeight{weight:10, name:"b".to_string()};
let a = undirected_graph.add_node(my_weight_a);
let b = undirected_graph.add_node(my_weight_b);
undirected_graph.add_edge(a,b,());
}
edgeのみ追加(nodeは自動作成)する方法
次にedgeだけを入力としてグラフを作成します。
これまでの方法は、グラフを作成して、nodeを作成した後、edgeを設定するという流れでした。今回の方法はedgeを設定するだけでnodeも自動で作成してくれます。注意点として、nodeの重みはデフォルトになるので、後で追加する必要があります。
重みなし有向グラフの場合
use petgraph;
fn main() {
let edges = [(0,1), (1,2), (2,0)];
//let edges = &[(0,1), (1,2), (2,0)]; イテレート可能なため、これでもいい
//let edges = vec![(0,1), (1,2), (2,0)]; イテレート可能なため、これでもいい
let directed_graph = petgraph::Graph::<(),(),petgraph::Directed>::from_edges(edges);
//let mut directed_graph = petgraph::Graph::<(),()>::from_edges();コードの説明を入れます。
petgraph::Graph::<(),(),petgraph::Directed>について
nodeとedgeをそれぞれ追加する方法と同じです。
from_edgesについて
from_edgesの引数は「イテレート可能」かつ「各要素が要素2or3のタプル」かつ「タプル内の各要素がu8,u16,u32,usizeのいずれか」です。
厳密なことを言おうとすると複雑になりますが、usizeタプルのVecだと考えていいと思います。
グラフ描画
グラフを描画してみると以下のようになります。nodeの中心はインデックスです。
重みあり有向グラフの場合
重みにはnodeの重みとedgeの重みがありますが、まずはedgeの重みのみありの場合についてです。edgeのみ追加の場合はnodeは自動で生成されるので、重みの値はデフォルト値となります。
use petgraph;
fn main() {
//let edges = [(0,1,2), (1,2,4), (2,0,-1)];
let edges = &[(0,1,2), (1,2,4), (2,0,-1)]; //イテレート可能なため、これでもいい
//let edges = vec![(0,1,2), (1,2,4), (2,0,-1)]; //イテレート可能なため、これでもいい
let directed_graph = petgraph::Graph::<(),i32,petgraph::Directed>::from_edges(edges);
//let directed_graph = petgraph::Graph::<(),i32>::from_edges(edges);
}コードの説明を入れます。
edgesについて
重みなしの場合と比較すると、3つ目の要素が増えました。これはedgeの重みです。「このパスを通るにはこれだけのコストがかかる」という時のコストのことです。この要素の型は任意ですが、グラフを作成するときのedgeの重みの型指定と一致させる必要があります(ここではi32)。
グラフ描画
グラフを描画してみます。まずnodeの中心にインデックスを描く場合。
nodeの中心に重みを描く場合。また、edgeの重みも書くようにします。nodeの重みはデフォルトの0になっています。
nodeの重みについて
from_edgesで作成した際の、nodeの重みは0になります。
nodeの重みを設定するには重みを書き換える必要があります。
例えば、重みの型をusizeにする場合、以下のようにします。
use petgraph;
fn main() {
let edges = [(0,1,2), (1,2,4), (2,0,-1)];
//let edges = &[(0,1,2), (1,2,4), (2,0,-1)]; //イテレート可能なため、これでもいい
//let edges = vec![(0,1,2), (1,2,4), (2,0,-1)]; //イテレート可能なため、これでもいい
let mut directed_graph = petgraph::Graph::<usize,i32,petgraph::Directed>::from_edges(edges);
//let directed_graph = petgraph::Graph::<usize,i32>::from_edges(edges);
directed_graph.node_indices().enumerate().for_each(|(n,nodeix)| {directed_graph[nodeix] = n*2;});
}コードの説明を入れます。
directed_graph.node_indices()…について
node_indices()は現在グラフにあるノードのインデックスについてのイテレータを返します。このイテレータの型はNodeIndexです。今、3つのノードがあるため、0,1,2になります。それをenumerate()でwrapすると、(0,0),(1,1),(2,2)になります。for_eachで、このそれぞれのタプルに対して、重みを代入します。directed_graph[node_index]を使うと指定したノードの重みにアクセスできます。例えば、一つ目の要素では、directed_graph[0] = 0;となります。
ここで、[]の中は実際にはNodeIndex型です。
グラフを描画
グラフを描画してみます。nodeの中心に重みを描くように指定してみると、重みが設定できているのがわかります。
次の記事
以下の2つのことも書こうと思いましたが、長くなりすぎるので分けようと思います。
- 作ったグラフに対しての探索
- dijkstra、二部グラフ判定、閉路検出
ここで挙げたコード例はgithubに上げています
例えば、以下のようなコードで、graphvizで読み込めるdot形式のグラフが出力されます。
cargo run --bin directed_no_weight_from_edgesgraphvizをインストールしているなら、以下のコードでpngを出力できます。
dot -Tpng -o hoge.png hoge.dotまた、リポジトリ内のこのスクリプトで、dot/以下にdot形式のファイルを保存し、png/以下にpngファイルを保存するようになっています。
コメント