Rust でグラフ(petgraph)

AtCoderのRust実行環境で使えるグラフライブラリ [petgraph 0.5.0](https://docs.rs/petgraph/0.5.0/petgraph/index.html) についての覚書

## 1. グラフの作り方
最も簡潔な方法は [from_edges](https://docs.rs/petgraph/0.5.0/petgraph/graph/struct.Graph.html#method.from_edges) というエッジ一覧から作る方法:

```rust
// 三すくみの無向グラフ
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](https://docs.rs/petgraph/0.5.0/petgraph/graph/struct.Graph.html#method.extend_with_edges) で、ノードを作ってからエッジを作る。ノードには文字列を エッジには整数値を重みとしてもつ有向グラフを作る例:

```rust
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](https://docs.rs/petgraph/0.5.0/petgraph/visit/index.html) にあるように、DFS, 帰りがけDFS, BFS, トポロジカル順など、様々な順で巡るイテレータが用意されている。しかし多くの場合単なるイテレータでは機能不足で、枝刈りや大域脱出が必要になる。DFSの場合は [depth_first_search](https://docs.rs/petgraph/0.5.0/petgraph/visit/fn.depth_first_search.html) がそれを反映した汎用的な枠組みだが、他の巡り方に対しては、同様のAPIは存在しない。自分で書くときはGraphが実装しているメソッド（例えば隣接ノードを求める`neighbors()`など）を使って記述するか、次章で紹介する汎用アルゴリズムを使う。

Dfsビジタを使って全てのノードの重み(i32整数値)をインクリメントする例:

```rust
let mut dfs = Dfs::new(&graph, a);
while let Some(nx) = dfs.next(&graph) {
   graph[nx] += 1;
}
```

`depth_first_search` を使って DFSの最中で 打ち切る(Break)/枝刈りをする(Prune)という典型的な制御フローを組み込んでパスを求める例が[公式のExample](https://docs.rs/petgraph/0.5.0/petgraph/visit/fn.depth_first_search.html#example)に記載がある。抜粋:

```rust
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. 有名なアルゴリズム
[有名なアルゴリズム](https://docs.rs/petgraph/0.5.0/petgraph/algo/index.html#functions) が実装されているので、頻出の問題には関数を呼び出すだけでよい。パス全探索・最短経路・ダイクストラ法・スパニングツリー・強連結分解等々。[UnionFind](https://docs.rs/petgraph/0.5.0/petgraph/unionfind/struct.UnionFind.html) もあるが、Graphのアルゴリズムの場所とは別の箇所で提供されている。

## 4. スニペット

```rust
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())); // エッジ一覧にないノードは存在しない
}
```



## 最後に
コメント歓迎です