Neo4jで重み付き最短経路問題を解く～ユーザ定義のプラグインを使用～

##記事を書いた理由
以前、[こちら](https://qiita.com/kk31108424/items/8c7bf307cc5773c24505)の記事で、Neo4jで最短経路計算をする手段の使い分けについてまとめました。

今回新たに、ビルトインで提供されているアルゴリズムをオーバーライドして、重み付き最短経路問題を解く方法を発見したので、まとめました。

##まずはお礼
今回は、Neo Technology社の[Max De Marzi氏の記事](https://github.com/maxdemarzi)を参考にさせていただき、検証を行いました。厚く御礼申し上げます。

##今回行うこと
今回は、アメリカの駅データを用いて、二つの分岐駅間の経路を計算します。
なお、検証環境はWindowsを想定しています。MacOSやLinuxを使用されている方は、コマンドなどを適宜読み替えていただけると幸いです。

##データのインポート
[こちら](https://raw.githubusercontent.com/maxdemarzi/choo_choo/master/src/main/resources/data/rail_junctions.csv)から分岐駅のデータ、[こちら](https://raw.githubusercontent.com/maxdemarzi/choo_choo/master/src/main/resources/data/rail_roads.csv)から分岐駅を結ぶ線路のデータを入手します。

※データが大きいので、インポートに時間がかかりますが、我慢しましょう！

###分岐駅データのインポート

```graphql
USING PERIODIC COMMIT LOAD CSV WITH HEADERS FROM "https://raw.githubusercontent.com/maxdemarzi/choo_choo/master/src/main/resources/data/rail_junctions.csv" AS line WITH line
CREATE (j:Junction {object_id:line.OBJECTID, fra_node_id:line.FRANODEID, 
                       latitude:toFloat(line.X), longitude:toFloat(line.Y)})
RETURN COUNT(*);
```

大きなデータを一度にインポートしようとすると、メモリを圧迫してしまいます。データが大きすぎてメモリが不足すると、``OutOfMemoryError``が投げられ、インポートに失敗してしまいます。

そんなときに役立つのが``USING PERIODIC COMMIT``です。``USING PERIODIC COMMIT``は、非常に大きなデータをインポートする際に使います。

これにより、大きなデータをインポートする際、一定数の列をインポートするごとにコミットされ、ファイル読み込み時のオーバーヘッドを減らすことができます。


![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/63b113b0-fff6-e86f-35ec-d2a3d2ae3753.png)

また、今回はノードID以外のプロパティは考慮する必要はありません。よって、ノード間のリレーションを作ることも考慮して、以下のようにノードIDを一意にします。

```graphql
CREATE CONSTRAINT ON (j:Junction) ASSERT j.fra_node_id IS UNIQUE;
```

###分岐駅を結ぶ線路データのインポート
```graphql
USING PERIODIC COMMIT LOAD CSV WITH HEADERS FROM "https://raw.githubusercontent.com/maxdemarzi/choo_choo/master/src/main/resources/data/rail_roads.csv" AS line WITH line
MATCH (j1:Junction {fra_node_id:line.FRFRANODE}), (j2:Junction {fra_node_id:line.TOFRANODE})
MERGE (j1)-[l:LINKS { object_id:line.OBJECTID, fra_aarc_id:line.FRAARCID, owner:line.RROWNER1,
 trackage:line.TRKRGHTS1 , tracks: toInteger(line.TRACKS), network:line.NET, miles:toFloat(line.MILES) }]->(j2)
RETURN COUNT(*);
```
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/2ff39201-1d0d-ca3d-aff7-dacdc8048c7b.png)

##最短経路問題を解く（ホップ数のみを考慮）
[こちら](https://qiita.com/kk31108424/items/8c7bf307cc5773c24505)の記事でも検証したように、シカゴからミルウォーキーまでの最短経路問題を解いてみます。

```graphql
// From Chicago to Milwaukee Shortest Number of Relationships
MATCH (chicago:Junction {fra_node_id: "414657"}), (milwaukee:Junction {fra_node_id: "412167"}),
        p = shortestPath((chicago)-[:LINKS*]-(milwaukee))
RETURN p
```
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/dc75479c-fba9-7ea8-b70f-2c7a13972b56.png)

このデータの持ち方によると、線路のデータ（エッジ）のプロパティが``X``を持つと、その経路は通ることができないようになっています。

通行可能な経路のみを通る時の最短経路は、以下のように求めます。

```graphql
// From Chicago to Milwaukee Shortest Number of Relationships on valid parts of the network
MATCH (chicago:Junction {fra_node_id: "414657"}), (milwaukee:Junction {fra_node_id: "412167"}),
        p = shortestPath((chicago)-[:LINKS*]-(milwaukee))
WHERE NONE( x IN relationships(p) WHERE x.network = "X" )  
RETURN p
```
<img width="1438" alt="スクリーンショット 2019-07-09 21.30.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/c2f9bac8-4fb9-39e1-789e-e56c0d1f17a1.png">

NONE()関数を用いて、``network``プロパティを持つエッジを排除して計算しています。

幸いにも、今回は先ほどと同じ結果が返ってきました。先ほど求めた最短経路で通行できないエッジはなかったようですね。

###距離を求める

求めた最短経路で、シカゴからミルウォーキーまでの距離を求めます。

```graphql
// From Chicago to Milwaukee Shortest Number of Relationships on valid parts of the network with mileage
MATCH (chicago:Junction {fra_node_id: "414657"}), (milwaukee:Junction {fra_node_id: "412167"}),
        p = shortestPath((chicago)-[:LINKS*]-(milwaukee))
WHERE NONE( x IN relationships(p) WHERE x.network = "X" )  
RETURN　reduce(totalMiles = 0, n IN relationships(p) | totalMiles + n.miles) AS miles 
```

<img width="1440" alt="スクリーンショット 2019-07-09 21.38.50.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/4d9ac28d-ee40-e7b1-b01d-a1cc4a7005ef.png">


reduce()関数を用いて、リストとして返される各経路の距離を繰り返し加算する処理を行っています。

しかし、[こちらの記事](https://qiita.com/kk31108424/items/8c7bf307cc5773c24505)でも検証した通り、``shortestPath``関数を用いて取得した最短経路は、**エッジの重みを考慮しない、最小のホップ数を持つ経路**です。

つまり、上記のクエリで算出された約86マイル以下の経路が存在する可能性が十分にあるのです。

##重み付き最短経路問題を解く
それでは、最短マイルの経路を調べるにはどうしたらよいでしょうか？すべての経路を調べてから距離順にソートするという方法も考えられますが、今回のようにデータがとても大きい場合、投げたクエリが返ってこない「組み合わせ爆発」が起こってしまいます。

###アルゴリズムを追加する方法
今回は、Neo4jにビルトインで提供されているアルゴリズムを活用して、新たに独自のアルゴリズムを追加して、それを呼び出すという方法で重み付き最短経路問題を解いてみます。

最初にも書きましたが、今回はNeo Technology社の[Max De Marzi氏の記事](https://github.com/maxdemarzi)を参考にさせていただきます。

ある程度経路の絞り込みをして、あまりにも最短経路とはかけ離れている（距離が大きすぎる）経路は最初から探索しないというアプローチで、この問題を解いてみます。
Max De Marzi氏がどのように実装しているのかを理解することが目的です。

###①リポジトリを拝借する
```shell
git clone  https://github.com/maxdemarzi/choo_choo.git
Cloning into 'choo_choo'...
remote: Enumerating objects: 50, done.
remote: Counting objects: 100% (50/50), done.
remote: Compressing objects: 100% (30/30), done.
remote: Total 50 (delta 9), reused 44 (delta 7), pack-reused 0
Unpacking objects: 100% (50/50), done.
```
###②コピーしたレポジトリでJavaプログラムをビルドする
今回は、Mavenというツールを使用します。

コピーした``maxdemarzi/choo_choo``ディレクトリで、以下のコマンドを実行します。

```shell
maven clean package
[INFO] Scanning for projects...
[INFO]
[INFO] ----------------------< com.maxdemarzi:railroads >----------------------
[INFO] Building railroads 1.0-SNAPSHOT
[INFO] --------------------------------[ jar ]---------------------------------
Downloading from central: https://repo.maven.apache.org/maven2/org/apache/maven/plugins/maven-clean-plugin/2.5/maven-clean-plugin-2.5.pom
Downloaded from central: https://repo.maven.apache.org/maven2/org/apache/maven/plugins/maven-clean-plugin/2.5/maven-clean-plugin-2.5.pom (3.9 kB at 1.7 kB/s)
Downloading from central: https://repo.maven.apache.org/maven2/org/apache/maven/plugins/maven-plugins/22/maven-plugins-22.pom
Downloaded from central: https://repo.maven.apache.org/maven2/org/apache/maven/plugins/maven-plugins/22/maven-plugins-22.pom (13 kB at 14 kB/s)

・・・（中略）・・・

[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  06:25 min
[INFO] Finished at: 2019-07-11T14:05:15+09:00
[INFO] ------------------------------------------------------------------------
```
このコマンドにより、javaプログラムがビルドされ、``jar``ファイルが作成されます。

###③作成された``jar``ファイルをpluginディレクトリにコピーする
```powershell
copy target/railroads-1.0-SNAPSHOT.jar (neo4jインスタンスが保存されているディレクトリ)/plugins/.
```

###④Neo4jを再起動する
Neo4jを再起動します。

これにより、ユーザー定義のプラグインを使うことができるようになります。

##どのような処理をしているか
今回、Max De Marzi 氏はビルトインのアルゴリズムにどのような処理を加えているのでしょうか。
以下に、実装されたコードの一部を示します。

```java:Procedure.java
@Procedure(name = "com.maxdemarzi.routes", mode = Mode.READ)
@Description("CALL com.maxdemarzi.routes(Node from, Node to, Number limit)")
public Stream<WeightedPathResult> routes(@Name("from") Node from, @Name("to") Node to, @Name("limit") Number limit) {
    // ↓ここで経路の絞り込みを行っている！
    double maxCost = getCost(from, to) * 1.2;
    ValidPathExpander validPaths = new ValidPathExpander(maxCost, latitudes.get(to), longitudes.get(to));
 
    PathFinder<WeightedPath> dijkstra = GraphAlgoFactory.dijkstra(validPaths,
            CommonEvaluators.doubleCostEvaluator(MILES), limit.intValue() );
 
    ArrayList<WeightedPathResult> results = new ArrayList<>();
    for(WeightedPath path : dijkstra.findAllPaths(from, to)) {
        results.add(new WeightedPathResult(path, path.weight()));
    }
 
    return results.stream();
}
```



``ValidPathExpander.java``の30行目で、以下のようなオーバーライドを行っています。

```java:ValidPathExpander.java
@Override
public Iterable<Relationship> expand(Path path, BranchState branchState) {
    List<Relationship> rels = new ArrayList<>();
    // ↓全経路が通行可能かを調べている
    for (Relationship r : path.endNode().getRelationships(RelationshipTypes.LINKS)) {
        if (!(r.getProperty(NETWORK)).equals(OUT_OF_SERVICE)) {
```

また、47~52行目で、それまでの最短経路の長さ以上の経路は計算しないようにしています。

```java:ValidPathExpander.java
if (getCost(latitudes.get(from), longitudes.get(from), latitude, longitude) <= maxCost) {
    rels.add(r);
    valid.add(from.getId());
} else {
    invalid.add(from.getId());
}
```

これにより、以下のようなアルゴリズムの呼び出しができるようになります。

``com.maxdemarzi.routes(始点ノード, 終点ノード, 表示したい経路の数)``

##実際に呼び出してみる
実際に呼び出してみましょう。

###シカゴからミルウォーキーまでの最短経路を10経路分求める

```graphql
MATCH (chicago:Junction {fra_node_id: "414657"}), (milwaukee:Junction {fra_node_id: "412167"})
CALL com.maxdemarzi.routes(chicago, milwaukee, 10)
YIELD path, weight
RETURN path, weight
```

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/3a699fa9-6a77-adf9-6e8b-76e7911e31ab.png)

###シカゴからミルウォーキーまでの最短経路のホップ数とその長さを10経路分求める
```graphql
MATCH (chicago:Junction {fra_node_id: "414657"}), (milwaukee:Junction {fra_node_id: "412167"})
CALL com.maxdemarzi.routes(chicago, milwaukee, 10)
YIELD path, weight
RETURN length(path), weight
```

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/1ab27d2a-0c32-7c60-b150-6e85bed904f6.png)

###シカゴからサンフランシスコまでの最短経路のホップ数とその長さを10経路分求める

```graphql
MATCH (chicago:Junction {fra_node_id: "414657"}), (san_francisco:Junction {fra_node_id: "306128"})
CALL com.maxdemarzi.routes(chicago, san_francisco, 10)
YIELD path, weight
RETURN length(path), weight
```

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/bff4a8a1-9a50-51d9-3fe7-987eaaf82380.png)

###シカゴからサンフランシスコまでの最短経路のホップ数とその長さを求める

```graphql
MATCH (chicago:Junction {fra_node_id: "414657"}), (san_francisco:Junction {fra_node_id: "306128"})
CALL com.maxdemarzi.routes(chicago, san_francisco, 1)
YIELD path, weight
RETURN length(path), weight
```

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/cfe67c7c-03bb-04c6-2184-852578f5a459.png)



##参考
https://neo4j.com/docs/cypher-manual/current/query-tuning/using/#query-using-periodic-commit-hint
https://neo4j.com/docs/cypher-manual/current/clauses/load-csv/#load-csv-setting-the-rate-of-periodic-commits
https://neo4j.com/docs/cypher-manual/current/functions/predicate/#functions-none