Neo4jでグラフアルゴリズム

前から調べようと思っていたNeo4jの勉強会に行ってきた。
jp-neo4j-usersgroup.connpass.com

グラフアルゴリズム

• とりあえず深さ優先探索、幅優先探索、ダイクストラ法などをビジュアライズしてみたい

AOJ - 深さ優先探索

データセットの用意

• 深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
  • サンプルデータがあるので、それを投入してみる

入力例 2
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

• こんな感じか？
  • たぶん書き方が冗長になっている気がする

CREATE (g:Graph { u:1, k:2 });
CREATE (g:Graph { u:2, k:2 });
CREATE (g:Graph { u:3, k:1 });
CREATE (g:Graph { u:4, k:1 });
CREATE (g:Graph { u:5, k:1 });
CREATE (g:Graph { u:6, k:0 });

MATCH (s:Graph) WHERE s.u = 1
MATCH (d:Graph) WHERE d.u = 2
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 1
MATCH (d:Graph) WHERE d.u = 3
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 2
MATCH (d:Graph) WHERE d.u = 3
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 2
MATCH (d:Graph) WHERE d.u = 4
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 3
MATCH (d:Graph) WHERE d.u = 5
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 4
MATCH (d:Graph) WHERE d.u = 6
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 5
MATCH (d:Graph) WHERE d.u = 6
CREATE (s)-[:DIRECTED]->(d);

ビジュアライズ

Neo4j Desktopを使ってビジュアライズしてみる

なにこれ高性能過ぎる・・・

アルゴリズム実装

あとはこれをクエリで距離を測ったりいろいろやりたい。

実装するのはこれ

function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)

• ノード3から辿れるものを出力
  • これで一応有向グラフをたどることはできてんのかな？
  • もともとプログラム側の疑似コードで for each v に接続している頂点 i do ~ done という処理をやらせているのは、グラフの探索のためであった、Neo4j(GQL)では MATCH (src)-[:DIRECTED*]->(dst) にてその指示が完了しているので、そこを考える必要がなくなっている？あとは、後戻り防止のために訪問済みかどうかチェックが付けられればいいのだけど。*1

MATCH (src)-[:DIRECTED*]->(dst)
WHERE src.u = 3
RETURN dst;

*1:そしてそのような処理はFOREACHでできそう