昔のお題をCypherで解いてみる - エンジニアのソフトウェア的愛情

グラフデータベースならグラフ理論の問題ぐらい解けるだろう、という乱暴な短絡思考から昔のグラフのお題を解いてみました。

C++のtemplateが問題を解く - エンジニアのソフトウェア的愛情

昔のお題がネタなら、今回の解法もネタだったりします。

とにかくCypher で書く

Cypher歴2日なので不手際があるかもしれません。

// see http://d.hatena.ne.jp/E_Mattsan/20120511/1336748744

// 番号付きの点を作る
UNWIND
  range(1, 20) AS number
CREATE
  (n:Point {number: number});

// 点から右方向と下方向の辺を作る
UNWIND
  // ただし右端と下端を除く
  [i IN range(1, 20) WHERE NOT (i % 4 = 0 OR i IN range(17, 20))] AS number
MATCH
  (n:Point {number: number}),
  (right:Point {number: number + 1}),
  (bottom:Point {number: number + 4})
CREATE
  (n)-[:Edge]->(right),
  (n)-[:Edge]->(bottom);

// 右端の点から下方向の辺を作る
UNWIND
  [i IN range(1, 4) | i * 4] AS number
MATCH
  (n:Point {number: number}),
  (bottom:Point {number: number + 4})
CREATE
  (n)-[:Edge]->(bottom);

// 下端の点から右方向の辺を作る
UNWIND
  range(17, 19) AS number
MATCH
  (n:Point {number: number}),
  (right:Point {number: number + 1})
CREATE
  (n)-[:Edge]->(right);

// 点1から点20への経路の個数を数える
MATCH
  (:Point {number: 1})-[*]->(:Point {number: 20})
RETURN
  count(*) AS count;

// 点6-点10, 点11-点12, 点14-点15 の辺を削除する
MATCH
  (_6:Point {number: 6}),
  (_10:Point {number: 10}),
  (_11:Point {number: 11}),
  (_12:Point {number: 12}),
  (_14:Point {number: 14}),
  (_15:Point {number: 15}),
  (_6)-[_6_10]->(_10),
  (_11)-[_11_12]->(_12),
  (_14)-[_14_15]->(_15)
DELETE
  _6_10,
  _11_12,
  _14_15;

// 点1から点20への経路の個数を数える
MATCH
  (:Point {number: 1})-[*]->(:Point {number: 20})
RETURN
  count(*) AS count;

実行してみる

上記のクエリを count_paths.cypher という名前で保存します。

neo4j-shell コマンドを使ってクエリを実行します。
Neo4j に干渉するデータが入っていない状態で実行してください。

$ neo4j-shell -file count_paths.cypher 
+-------------------+
| No data returned. |
+-------------------+
Nodes created: 20
Properties set: 20
Labels added: 20
5 ms
+-------------------+
| No data returned. |
+-------------------+
Relationships created: 24
15 ms
+-------------------+
| No data returned. |
+-------------------+
Relationships created: 4
6 ms
+-------------------+
| No data returned. |
+-------------------+
Relationships created: 3
6 ms
+-------+
| count |
+-------+
| 35    |
+-------+
1 row
14 ms
+-------------------+
| No data returned. |
+-------------------+
Relationships deleted: 3
6 ms
+-------+
| count |
+-------+
| 15    |
+-------+
1 row
9 ms

それぞれ経路数が35, 15と出力されました。