Neo4jでグラフアルゴリズム：双方向ダイクストラ探索

この記事について

Neo4jを使ったグラフアルゴリズムの実装を紹介してみようという計画「グラフアルゴリズム入門 - javaとNeo4jで学ぶ -」の一部です（どこまで続くか・・・）

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

双方向ダイクストラ探索

秋葉さんのスライド：大規模グラフアルゴリズムの最先端のP.16近辺に少し記述がある。双方向ダイクストラ探索は、与えられた2点の最短経路を求めるアルゴリズムであるが、その2点の両側からダイクストラ探索を実行し、ぶつかったら最短距離の候補として記憶する。さらに「よりよい（短い）経路が見つけられない」ことが判定できたら、解が見つかったことになる。双方向ダイクストラ探索は、最悪ケースではダイクストラ探索と同等の計算量となるが、データには依存するものの探索範囲を狭める効果がある。下図は上記のスライドから引用した図であり、双方向ダイクストラ探索のイメージをわかりやすく示している。

「よりよい（短い）経路が見つけられない」の判定には、三角不等式を使う。候補の最短距離が、（スタート側から探索して到達した距離＋エンド側から探索して到達した距離）を下回れば、その候補よりもさらに短い経路を発見することはないから終了してよい。下図にイメージを示す。

Neo4jによる実装

まず、ノードの隣を展開して、プライオリティキューに登録していく部分は、スタート側、エンド側の双方で共通に使われるので関数として切り出しておこう。ここはダイクストラ法で用いたものと全く同じ処理である。

    // get adjacent nodes and add them to queue
    public void getAdjacentNodes(NodeInfo cur_ni, PriorityQueue<NodeInfo> pq, Map<Node, NodeInfo> nodes, Map<Node, Relationship> parent) {
        // Property for cost: type must be double
        String cost_property = "cost";
        Iterable<Relationship> rels = cur_ni.nd.getRelationships();
        for (Relationship rel : rels) {
            // get adjacent nodes and their costs
            Node o_nd = rel.getOtherNode(cur_ni.nd);
            double cost_rel = (double) rel.getProperty(cost_property);
            // check whether the node was found
            NodeInfo next_ni = nodes.get(o_nd);
            // not found -> 1st appearance of the node, add it to map
            if (next_ni == null) {
                next_ni = new NodeInfo(o_nd, cur_ni.cost + cost_rel);
                pq.add(next_ni);
                nodes.put(o_nd, next_ni);
                parent.put(o_nd, rel);
            }
            // found but cost is't fixed and has lower cost -> overwrite cost
            else if (next_ni.done == false) {
                if (next_ni.cost > cur_ni.cost + cost_rel) {
                    next_ni.cost = cur_ni.cost + cost_rel;
                    parent.put(o_nd, rel);
                }
            }
            // found and cost was fixed -> do nothing
        }
    }

スタート側とエンド側について、普通のダイクストラの場合と同様に、それぞれプライオリティキューやマップを用意する必要がある。探索を進める方法であるが、ここでは、2つのキューの先頭のコストを比較してが小さい側を展開する。左右の探索範囲が同程度の大きさで少しずつ広がるイメージである。whileループを脱出する条件が異なっていて、それぞれ、以下のようになる。

• （経路を見つける前に）どちらかのプライオリティキューが空になってしまう場合は、つながる経路が存在しない場合なので、解なし
• 片側から探していって、（双方向の結果をあわせるまでもなく）目標とするノードに到達してしまう場合は、これは最短経路であるから、それをそのまま返せばよい
• 上で説明した三角不等式を満たす場合、これは双方向の結果をつなげたものが求める最短経路である。

片側のノードのコストが確定したタイミングで、もう反対側のキューに登録されている（つまり、暫定的にでもコストが求められている。このプログラムではnodes_f, nodes_tに登録さているかどうかを調べる）かどうかを調べ、もし登録されていて、全体のコストがこれまでより小さくなるならば、最小値を更新する。もし、仮に上記の反対側のコストが暫定的であっても、そのコストが確定するタイミングで反対側を調べに行くから、最終的には最適な値を求めることができる。

    // sample8_2: bidirectional djkstra
    @Procedure(value = "example.sample8_2")
    @Description("sample8_2: bidirectional djkstra")
    public Stream<Output> sample8_2(@Name("from_id") final Long from_id, @Name("to_id") final Long to_id) {
        final Node from_nd = db.getNodeById(from_id);
        final Node to_nd = db.getNodeById(to_id);
        // Priority Queue by cost property value
        final PriorityQueue<NodeInfo> pq_f = new PriorityQueue<>((n1, n2) -> Double.compare(n1.cost, n2.cost));
        final PriorityQueue<NodeInfo> pq_t = new PriorityQueue<>((n1, n2) -> Double.compare(n1.cost, n2.cost));
        // map for keeping node and cost
        final Map<Node, NodeInfo> nodes_f = new HashMap<>();
        final Map<Node, NodeInfo> nodes_t = new HashMap<>();
        // map for keeping Node and parent relationship
        final Map<Node, Relationship> parent_f = new HashMap<>();
        final Map<Node, Relationship> parent_t = new HashMap<>();

        // current node(info)
        NodeInfo cur_ni_f = new NodeInfo(from_nd, 0.0);
        pq_f.add(cur_ni_f);
        nodes_f.put(from_nd, cur_ni_f);
        NodeInfo cur_ni_t = new NodeInfo(to_nd, 0.0);
        pq_t.add(cur_ni_t);
        nodes_t.put(to_nd, cur_ni_t);

        // node that f-side path and t-side path meets
        NodeInfo min_ni_f = null;
        NodeInfo min_ni_t = null;

        // variables for checking to exit
        double total_cost = 100000; // total cost

        // Result
        final Output o = new Output();

        // Path finding
        while(true) {
            // if one queue is empty, no route exit
            if(cur_ni_f == null || cur_ni_t == null) {
                return new ArrayList<Output>().stream();
            }
            // exit when found to node in the from-side
            if(cur_ni_f.nd.equals(to_nd)) {
                o.path = getPath(from_nd, min_ni_f.nd, parent_f);
                o.cost = cur_ni_f.cost;
                break;
            }
            // exit when found from node in the to-side
            if(cur_ni_t.nd.equals(from_nd)) {
                o.path = reverse(getPath(to_nd, min_ni_t.nd, parent_t));
                o.cost = cur_ni_t.cost;
                break;          
            }
            // exit when cannot find shorter path (triangle inequality)
            // (total cost) < (current f-side cost) + (current t-side cost)
            if(cur_ni_f.cost + cur_ni_t.cost > total_cost){
                final Path f_path = getPath(from_nd, min_ni_f.nd, parent_f);
                final Path t_path = getPath(to_nd, min_ni_t.nd, parent_t);
                o.path = cat(f_path, reverse(t_path));
                o.cost = total_cost;
                break;
            }
            // expand from-side
            if(pq_f.peek().cost <= pq_t.peek().cost){
                // top node of queue's cost is fixed
                cur_ni_f = pq_f.poll();
                cur_ni_f.done = true;
                // find the node in the other side
                final NodeInfo ni_t = nodes_t.get(cur_ni_f.nd);
                // the node is in the other side map and total_cost can be lower
                if(ni_t != null && total_cost > cur_ni_f.cost + ni_t.cost) {
                    min_ni_f = cur_ni_f;
                    min_ni_t = ni_t;
                    total_cost = cur_ni_f.cost + ni_t.cost;                 
                }
                // get adjacent nodes and add them to queue
                // Property for cost: type must be double
                getAdjacentNodes(cur_ni_f, pq_f, nodes_f, parent_f);
            }
            // expand to-side
            else{
                cur_ni_t = pq_t.poll();
                cur_ni_t.done = true;
                final NodeInfo ni_f = nodes_f.get(cur_ni_t.nd); 
                if(ni_f != null && total_cost > ni_f.cost + cur_ni_t.cost) {
                    min_ni_f = ni_f;
                    min_ni_t = cur_ni_t;
                    total_cost = ni_f.cost + cur_ni_t.cost; 
                }       
                getAdjacentNodes(cur_ni_t, pq_t, nodes_t, parent_t);
            }           
        }
        // list for result
        final List<Output> o_l = new ArrayList<>();
        o_l.add(o);
        return o_l.stream();
    }

双方向のパスをまとめて一つのパスを作るために使った、パスを逆転する処理とくっつける処理については、以下のようになっている。

    // reverse Path
    public Path reverse(Path p) {
        PathImpl.Builder builder = new PathImpl.Builder(p.endNode());       
        for(Relationship r: p.reverseRelationships()) {
            builder = builder.push(r);
        }
        return builder.build();
    }
    // concatenate two Paths 
    public Path cat(Path p1, Path p2) {
        PathImpl.Builder builder = new PathImpl.Builder(p1.startNode());
        Iterable<Relationship> rels1 = p1.relationships();
        Iterable<Relationship> rels2 = p2.relationships();
        for(Relationship r: rels1) {
            builder = builder.push(r);
        }
        for(Relationship r: rels2) {
            builder = builder.push(r);
        }
        return builder.build();
    }