LoginSignup
1

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-09-06

はじめに

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

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

トピック

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

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

Neo4jの概要

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

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

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

Neo4jのJava API

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

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

こちらに記事にした

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1