グラフアルゴリズム入門 - javaとNeo4jで学ぶ -

はじめに

グラフデータベースNeo4jは通常は、Cypherというグラフデータベース検索言語を利用してアクセスする。Cypherは、グラフに対するパターンマッチを容易にすることに特徴があるが、Neo4jにビルトインで組み込まれている探索アルゴリズムを呼び出すことも可能である。よって、Neo4jを利用するときに自前でグラフアルゴリズムを実装する必要は基本的にはない。しかし、本稿では自前によるグラフアルゴリズムを実装する例を紹介する。グラフアルゴリズムを学ぶために、Neo4jをグラフに関するプログラミングのフレームワークとして利用することが有効だと思うからである。

グラフアルゴリズムはアルゴリズムの基礎として非常に重要と考えられているのに、意外と具体的なコード例を伴った著作は多くなく、アルゴリズムの教科書に擬似コードで書かれているだけの事も多い（参考文献¹）。その例外としては、Javaによるものでは参考文献² 、C言語によるものでは参考文献 ³がある。前者はJavaで書かれている点が使いやすいが、アルゴリズム全般を対象にしているためグラフに関する記述はあまり充実していない。後者は、豊富なグラフアルゴリズムの実装例が含まれており興味深い。この本の第1章は、グラフ表現のデータ構造を紹介することに割かれており、以降のグラフアルゴリズムの基礎となっている。これも重要ではあるのだが、グラフアルゴリズムを純粋に学びたいのであれば、標準的なグラフデータへのインターフェースが既に用意されている環境で学んだほうがアルゴリズムに集中できるし、プログラムも標準的ですっきりし理解しやすくなる。また、Neo4jでアルゴリズムを作成すれば、動作確認や可視化にNeo4jの便利なツール群を利用することができるし、Webアプリケーションにするのも容易である。何となく地味で無味乾燥な感じになりやすいアルゴリズムの勉強を、イメージが湧きやすくより楽しくすることができるのではないだろうか。また、Neo4jはデータベースであるから当然永続化は勝手にやってくれるし、グラフの規模が極端に大きくなければ、オンメモリの状態でデータにアクセスするので性能も高い。

トピック

扱いたいトピックを以下にあげる。一部は既に記事にしている。

• Neo4jの概要（この辺はとりあえず他コンテンツを参照で）
• Neo4jのアーキテクチャとアプリケーション機能分担
• Neo4jのJava API
• Neo4jのプロシージャによる拡張
• 基本的なデータ構造：キュー、スタック、プライオリティキュー
• 幅優先探索
• 深さ優先探索
• 最短経路：ダイクストラ法
• 最短経路：A*法
• 最短経路：双方向ダイクストラ法
• 旅行計画問い合わせ(Trip planning query)
• 補足：Neo4jプロシージャの単体テストとCypherからの返却値の解説
• 補足：Spring Data Neo4jとSpring Bootを利用してWebアプリ化

サンプルコードはこちらにおいた。

Neo4jの概要

Neo4jことはじめを参照。
これで概要とCypherの簡単な使い方はわかる。ただし、インストールについては、今はNeo4j Desktopを使うほうがよいだろう。

Neo4jのアーキテクチャとアプリケーション機能分担

Cypher・プロシージャなどをどう組み合わせるのがおすすめなのかをまとめる予定

Neo4jのJava API

この辺のドキュメントを参照。今では、Java開発者マニュアルの第1章が、Extenging Neo4jである。拡張から入るのがわかりやすい（昔はおそらくEmbeddedのほうが先だっただろう）。

• The Neo4j Java Developer Reference
• Neo4j 3.5 API
• Neo4j Java Driver API

Neo4jのプロシージャによる拡張

こちらに記事にした

基本的なデータ構造：キュー、スタック、プライオリティキュー

サンプルはC++だが、一般的な説明は スタックとキューを極める！ 〜 考え方と使い所を特集 〜 がわかりやすい。Javaでの利用は、[Java] スタック・キューのメモに簡単にまとまっている。

---

1. Jon Kleinberg, アルゴリズムデザイン, 共立出版 , 2008 ↩

2. 永田 武, Javaによるアルゴリズムとデータ構造の基礎, コロナ社 , 2019 ↩

3. 浅野孝夫, グラフ・ネットワークアルゴリズムの基礎：数理とCプログラム, 近代科学社, 2017 ↩