概要

Rustでグラフ構造を扱う方法あれこれを書いていこうと思います。第一回はRustでグラフを表現する方法とRust初心者がはまりがちなポイントを見ていきます。

グラフとは?

グラフGとはノードVと辺Eの集合でG(V, E)のように書かれます。特に向きがある有向グラフの場合、辺は矢印であらわされ、始点のノードを親、終点のノードは子と呼ばれます。例えば以下の図ではノード1と2は0の子であり、0はそれぞれの親です。

ノードは様々な表現がありますが、ここではシンプルに以下のようにあらわします。

Node:
    - id
    - parents: 親ノードのIDのリスト
    - children: 子ノードのIDのリスト

このようにノードを定義すると辺の情報も自動的に含まれるのでグラフはノードの集合となります。利便性のためにここではグラフはノードのリストではなく、idをキーとした辞書であらわします。

Graph = Map<ID, Node>

さて、これを素直にRustで表現すると以下のようになります。

struct Node {
    id: usize,
    parents: HashSet<usize>,
    children: HashSet<usize>,
}

type Graph = HashMap<usize, Node>;

現実の問題をグラフであらわすときには多くの場合は親ノードのみが分かっていてどんな子ノードが存在しているかわからないことが多々あります。そこでここでは子ノードのリストを埋める方法を考えてみます。シンプルな方法として以下のように二重ループを回すものがすぐに思いつきます。

fn fill_children(graph: &mut Graph) {
    for (id, node) in graph.iter_mut() {
        for p_id in node.parents.iter() {
            let p_node = graph.get_mut(p_id).unwrap();
            p_node.children.insert(*id);
        }
    }
}

しかし、この方法はうまくいかず、二回目のgraph.get_mutでコンパイルエラーが発生します。これはRustでは同じオブジェクトに対する可変参照は同時に一つしか作れないという制限があるからです。これを回避するためにはRefCellを使用したInterior Mutability Pattern¹というのを使用します。

struct Node {
    id: usize,
    parents: RefCell<HashSet<usize>>,
    children: RefCell<HashSet<usize>>,
}

fn fill_children(graph: &Graph) {
    for (id, node) in graph.iter() {
        for p_id in node.parents.borrow().iter() {
            let p_node = graph.get(p_id).unwrap();
            p_node.children.borrow_mut().insert(*id);
        }
    }
}

RefCellを使用することで可変でない参照からでも内部の要素を変更できるようになります。これは実際には可変参照のチェックをコンパイル時ではなく実行時に行うという方式で実現されているのですが、やはりborrow_mutの結果の変数を同時に複数作成するとエラーになります。上記の例ではnodeの通常の参照を先に２つ作り、後者についてborrow_mutを一度だけ使用するので回避できているわけです。今回の例では本当はchildrenだけをRefCellで包めばいいのですが、子だけが分かっている状態から親を埋めるという場合もあるでしょうからparentsもRefCellにしています。

記事の初めに挙げた図のグラフについて、親だけが分かっている状態から子を実際に埋めてみます。完全なコードは以下の通りです。maplit²というcrateを使用しています。

use std::{
    cell::RefCell,
    collections::{HashMap, HashSet},
};

use maplit::hashset;

#[derive(Debug, Clone)]
struct Node {
    id: usize,
    parents: RefCell<HashSet<usize>>,
    children: RefCell<HashSet<usize>>,
}

impl Node {
    fn new(id: usize, parents: HashSet<usize>, children: HashSet<usize>) -> Self {
        Self {
            id,
            parents: RefCell::new(parents),
            children: RefCell::new(children),
        }
    }
}

type Graph = HashMap<usize, Node>;

fn fill_children(graph: &Graph) {
    for (id, node) in graph.iter() {
        for p_id in node.parents.borrow().iter() {
            let p_node = graph.get(p_id).unwrap();
            p_node.children.borrow_mut().insert(*id);
        }
    }
}

fn main() {
    let nodes = [
        Node::new(0, hashset! {}, hashset! {}),
        Node::new(1, hashset! {0}, hashset! {}),
        Node::new(2, hashset! {0}, hashset! {}),
        Node::new(3, hashset! {2}, hashset! {}),
        Node::new(4, hashset! {2}, hashset! {}),
        Node::new(5, hashset! {4}, hashset! {}),
        Node::new(6, hashset! {3, 5}, hashset! {}),
    ];

    let graph = nodes
        .into_iter()
        .map(|node| (node.id, node))
        .collect::<HashMap<_, _>>();

    fill_children(&graph);

    let mut nodes = graph.values().collect::<Vec<_>>();
    nodes.sort_unstable_by_key(|node| node.id);
    dbg!(nodes);
}

これを実行すると以下のようになり、上の図の通りにchildrenが埋まっていることが分かります。

nodes = [
    Node {
        id: 0,
        parents: RefCell {
            value: {},
        },
        children: RefCell {
            value: {
                1,
                2,
            },
        },
    },
    Node {
        id: 1,
        parents: RefCell {
            value: {
                0,
            },
        },
        children: RefCell {
            value: {},
        },
    },
    Node {
        id: 2,
        parents: RefCell {
            value: {
                0,
            },
        },
        children: RefCell {
            value: {
                4,
                3,
            },
        },
    },
    Node {
        id: 3,
        parents: RefCell {
            value: {
                2,
            },
        },
        children: RefCell {
            value: {
                6,
            },
        },
    },
    Node {
        id: 4,
        parents: RefCell {
            value: {
                2,
            },
        },
        children: RefCell {
            value: {
                5,
            },
        },
    },
    Node {
        id: 5,
        parents: RefCell {
            value: {
                4,
            },
        },
        children: RefCell {
            value: {
                6,
            },
        },
    },
    Node {
        id: 6,
        parents: RefCell {
            value: {
                5,
                3,
            },
        },
        children: RefCell {
            value: {},
        },
    },
]

Rustでグラフアルゴリズム Part1

概要

グラフとは?