LoginSignup
1

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-07-11

記事を書いた理由

以前、こちらの記事で、Neo4jで最短経路計算をする手段の使い分けについてまとめました。

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

まずはお礼

今回は、Neo Technology社のMax De Marzi氏の記事を参考にさせていただき、検証を行いました。厚く御礼申し上げます。

今回行うこと

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

データのインポート

こちらから分岐駅のデータ、こちらから分岐駅を結ぶ線路のデータを入手します。

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

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

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

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

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

分岐駅を結ぶ線路データのインポート

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

最短経路問題を解く(ホップ数のみを考慮)

こちらの記事でも検証したように、シカゴからミルウォーキーまでの最短経路問題を解いてみます。

// 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

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

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

// 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

スクリーンショット 2019-07-09 21.30.45.png

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

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

距離を求める

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

// 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 

スクリーンショット 2019-07-09 21.38.50.png

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

しかし、こちらの記事でも検証した通り、shortestPath関数を用いて取得した最短経路は、エッジの重みを考慮しない、最小のホップ数を持つ経路です。

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

重み付き最短経路問題を解く

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

アルゴリズムを追加する方法

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

最初にも書きましたが、今回はNeo Technology社のMax De Marzi氏の記事を参考にさせていただきます。

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

①リポジトリを拝借する

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ディレクトリで、以下のコマンドを実行します。

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ディレクトリにコピーする

copy target/railroads-1.0-SNAPSHOT.jar (neo4jインスタンスが保存されているディレクトリ)/plugins/.

④Neo4jを再起動する

Neo4jを再起動します。

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

どのような処理をしているか

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

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行目で、以下のようなオーバーライドを行っています。

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行目で、それまでの最短経路の長さ以上の経路は計算しないようにしています。

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経路分求める

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

シカゴからミルウォーキーまでの最短経路のホップ数とその長さを10経路分求める

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

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

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

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

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://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

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
  3. You can use dark theme
What you can do with signing up
1