AtCoderのRust実行環境で使えるグラフライブラリ petgraph 0.5.0 についての覚書
1. グラフの作り方
最も簡潔な方法は from_edges というエッジ一覧から作る方法:
// 三すくみの無向グラフ
let g = UnGraph::<(),()>::from_edges(&[(0,1), (1,2), (2,0)]);
// エッジに整数値の重みがある場合
let g = UnGraph::<(),i32>::from_edges(&[(0,1,100), (1,2,50), (2,0,200)]);
// 例: 全重みの合計
assert_eq!(350, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
普通の方法は extend_with_edges で、ノードを作ってからエッジを作る。ノードには文字列を エッジには整数値を重みとしてもつ有向グラフを作る例:
let mut g = DiGraph::<&str,i32>::new();
let a = g.add_node("a");
let b = g.add_node("b");
let c = g.add_node("c");
g.extend_with_edges(&[(a,b,100), (b,c,50), (c,a,200)]);
assert_eq!(350, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
2. グラフの巡り方
petgraph::visit にあるように、DFS, 帰りがけDFS, BFS, トポロジカル順など、様々な順で巡るイテレータが用意されている。しかし多くの場合単なるイテレータでは機能不足で、枝刈りや大域脱出が必要になる。DFSの場合は depth_first_search がそれを反映した汎用的な枠組みだが、他の巡り方に対しては、同様のAPIは存在しない。自分で書くときはGraphが実装しているメソッド（例えば隣接ノードを求めるneighbors()など）を使って記述するか、次章で紹介する汎用アルゴリズムを使う。
Dfsビジタを使って全てのノードの重み(i32整数値)をインクリメントする例:
let mut dfs = Dfs::new(&graph, a);
while let Some(nx) = dfs.next(&graph) {
graph[nx] += 1;
}
depth_first_search を使って DFSの最中で 打ち切る(Break)/枝刈りをする(Prune)という典型的な制御フローを組み込んでパスを求める例が公式のExampleに記載がある。抜粋:
depth_first_search(&gr, Some(start), |event| {
if let DfsEvent::TreeEdge(u, v) = event {
predecessor[v.index()] = u;
if v == goal {
return Control::Break(v);
}
}
Control::Continue
});
3. 有名なアルゴリズム
有名なアルゴリズム が実装されているので、頻出の問題には関数を呼び出すだけでよい。パス全探索・最短経路・ダイクストラ法・スパニングツリー・強連結分解等々。UnionFind もあるが、Graphのアルゴリズムの場所とは別の箇所で提供されている。
4. スニペット
use petgraph::{Undirected, Directed};
use petgraph::graph::Graph;
fn main() {
// エッジ一覧から有向グラフをつくる例(少し煩雑だが汎用的)
let data = [(0,1),(1,2),(2,3),(3,1)];
let mut g = Graph::<(),()>::new(); // デフォルトでは有向グラフ
let nodes: Vec<_> = (0..6).map(|_| g.add_node(())).collect(); // ノードの数は6個としよう
g.extend_with_edges(data.iter().map(|&x| (nodes[x.0], nodes[x.1])));
assert_eq!((6, 4), (g.node_count(), g.edge_count()));
// エッジ一覧から有向グラフをつくる例(簡潔だが注意が必要)
let g = Graph::<(), (), Directed, usize>::from_edges(&data);
assert_eq!((4, 4), (g.node_count(), g.edge_count())); // エッジ一覧にないノードは存在しない
// エッジ一覧から無向グラフをつくる例(少し煩雑だが汎用的)
let data = [(0,1),(1,2),(2,3),(3,1)];
let mut g = Graph::<(),(),Undirected>::new_undirected();
let nodes: Vec<_> = (0..6).map(|_| g.add_node(())).collect(); // ノードの数は6個としよう
g.extend_with_edges(data.iter().map(|&(i,j)| (nodes[i], nodes[j])));
assert_eq!((6, 4), (g.node_count(), g.edge_count()));
// エッジ一覧から無向グラフをつくる(簡潔だが注意が必要)例
let g = Graph::<(), (), Undirected, usize>::from_edges(&data);
assert_eq!((4, 4), (g.node_count(), g.edge_count())); // エッジ一覧にないノードは存在しない
// 重みのある有向グラフ
let data = [(0,1,10),(1,2,40),(2,3,100),(3,1,300)];
let mut g = Graph::<usize,i32>::new();
let nodes: Vec<_> = (0..6).map(|i| g.add_node(i)).collect(); // ノードの重みは添え字にしてみる
g.extend_with_edges(data.iter().map(|&(i,j,k)| (nodes[i], nodes[j], k)));
assert_eq!(450, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
assert_eq!((6, 4), (g.node_count(), g.edge_count()));
// 簡便な方法
let g = Graph::<usize, i32, Directed, usize>::from_edges(&data);
assert_eq!((4, 4), (g.node_count(), g.edge_count())); // エッジ一覧にないノードは存在しない
assert_eq!(450, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
assert!(g.node_indices().all(|ni| g[ni] == 0)); // ノードの重みには型のデフォルト値がはいる
// 重みのある無向グラフ
let data = [(0,1,10),(1,2,40),(2,3,100),(3,1,300)];
let mut g = Graph::<usize, i32, Undirected>::new_undirected();
let nodes: Vec<_> = (0..6).map(|i| g.add_node(i)).collect(); // ノードの重みは添え字にしてみる
g.extend_with_edges(data.iter().map(|&(i,j,k)| (nodes[i], nodes[j], k)));
assert_eq!(450, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
assert_eq!((6, 4), (g.node_count(), g.edge_count()));
// 簡便な方法
let g = Graph::<usize, i32, Undirected, usize>::from_edges(&data);
assert_eq!(450, g.edge_indices().map(|ei| g[ei]).sum::<i32>());
assert_eq!((4, 4), (g.node_count(), g.edge_count())); // エッジ一覧にないノードは存在しない
}
最後に
コメント歓迎です