概要: Rustでグラフのように相互参照を含むデータ構造を表現するには、Typed Arenaという方法が適している。これについて説明する

整数による表現

グラフの表現方法で、最も簡単なのは、ノードを整数で表し、グラフのデータを別に持つ方法である。

fn main() {
    let mut edges = vec![vec![]];
    edges[0].push(0);
    edges.push(vec![]);
    edges[1].push(0);
}

これは大抵どんな言語でも同じように使えるし、場合によってはこちらで済ませてしまったほうが簡単かもしれない。特に競技プログラミングではノードに付与されている情報が少なかったり、ノードに明示的に整数が付番されていたりするため、ほとんどの場合整数で表現するほうが扱いやすい。

しかしこの方法では、整数とグラフデータとの対応関係を見失いやすいと考えられる。整数を別の構造体で包んだり、indexingというライブラリを使うなどして、マーカーをつける手はあるが、それにしてもやや面倒なことが多い。

参照による表現の問題点

そこで、ノードを構造体で表し、その参照を持ち回すことを考える。

ノードは複数の別のノードから参照されるから、 &mut は使えない。しかしグラフを途中で変更する必要が出るかもしれない。そのような場合、つまり & をimmutable referenceではなくshared mutable referenceとして使いたいときは、 RefCell を使うのであった。

例えば、グラフのノードは以下のように表現できる。

use std::cell::RefCell;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

この定義自体は問題ない、しかしグラフを次のように構築しようとすると問題が発生する。

fn main() {
    let node0 = NodeData { references: RefCell::new(vec![]) };
    node0.references.borrow_mut().push(&node0);
    let node1 = NodeData { references: RefCell::new(vec![]) };
    node0.references.borrow_mut().push(&node1);
}

rustc 1.16.0 (30cf806ef 2017-03-10)
error: `node1` does not live long enough
  --> <anon>:13:1
   |
12 |     node0.references.borrow_mut().push(&node1);
   |                                         ----- borrow occurs here
13 | }
   | ^ `node1` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error: aborting due to previous error

要するに、ノードは相互に参照しあうため、きっかり同一の生存期間を持たなければならない。

ノードの個数が決まっていれば、次のように Vec で確保するといった方法をとることができる。

use std::cell::RefCell;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

fn main() {
    let mut nodes = vec![];
    nodes.push(NodeData { references: RefCell::new(vec![]) });
    nodes.push(NodeData { references: RefCell::new(vec![]) });
    let node0 = &nodes[0];
    let node1 = &nodes[1];
    node0.references.borrow_mut().push(node0);
    node0.references.borrow_mut().push(node1);
}

しかし、この方法では、動的にノードを追加することはできない。

Typed Arena を使ったメモリ確保

Typed Arenaと呼ばれるライブラリを使うと、同一生存期間を持ったメモリを複数回に分けて確保することができる。

Typed Arenaは、 arena crateの arena::TypedArena と typed_arena crateの typed_arena::Arena がある。これらはほぼ同じ内容だが、 arena はコンパイラ内部で使うためにあり、通常はnightlyでしか使えない。通常の用途では typed_arena を使う。

[dependencies]
typed-arena = "1.2.0"

extern crate typed_arena;

use std::cell::RefCell;
use typed_arena::Arena;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

fn main() {
    let nodes = Arena::new(); // mut は不要
    let node0 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node0);
    let node1 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node1);
}

まとめ

相互参照を含むデータ構造では2つの問題があり、それぞれに解決策がある。

複数の参照を保持しつつ、データを書き換えたい場合がある。→ RefCell を使う。
相互に参照するため、同一生存期間をもつデータを複数用意したい。→ 最初に一括で確保するなら Vec 等でよい。動的に確保したければ typed_arena::Arena (または arena::TypedArena) を使う。

TypedArena はRustコンパイラでも使われている。例えばインポート解決はグラフを扱うため TypedArena を用いる。

簡潔なQ

Rustでグラフを表現するにはTyped Arenaが便利

整数による表現

参照による表現の問題点

Typed Arena を使ったメモリ確保

まとめ