1

via node メソッドを使用して代替パスを生成する実装に取り​​組んでいます。

局所最適性をチェックしながら、次のことを行います

forwardEdge = bestWeightMapFrom.get(viaNode);
reverseEdge = bestWeightMapTo.get(viaNode);

double unpackedUntilDistance = 0;
while(forwardEdge.edge != -1) {
   double parentDist = forwardEdge.parent != null ? forwardEdge.parent.distance : 0;
   double dist = forwardEdge.distance - parentDist;
   if(unpackedUntilDistance + dist >= T_THRESHOLD) {
     EdgeSkipIterState edgeState = (EdgeSkipIterState) graph.getEdgeProps(forwardEdge.edge, forwardEdge.adjNode);
     unpackStack.add(new EdgePair(edgeState, false));
     sV = forwardEdge.adjNode;
     forwardEdge = forwardEdge.parent;
     break;
   }
   else {
     unpackedUntilDistance += dist;
     forwardEdge = forwardEdge.parent;
     sV = forwardEdge.adjNode;
   }
 }
 int oldSV = forwardEdge.adjNode;
 EdgeEntry oldForwardEdge = forwardEdge;

スタック内のエッジをアンパックして、sV をさらに絞り込みます。reverseEdge をトラバースすることで、同様の方法で vT と oldVt を取得します。

sV と vT からのパスが <= アンパックされたエッジの長さであると判断した場合、ノードを介してこれを受け入れ、次のように alternatePath を構築します。

PathBidirRef p = (PathBidirRef) algo.calcPath(oldSV, oldVT);

Path4CHAlt p1 = new Path4CHAlt(graph, flagEncoder);
p1.setSwitchToFrom(false);
p1.setEdgeEntry(oldForwardEdge);
p1.segmentEdgeEntry = p.edgeEntry;
double weight = oldForwardEdge.weight + oldReverseEdge.weight + p.edgeEntry.weight + p.edgeTo.weight;
p1.setWeight(weight);
p1.edgeTo = oldReverseEdge;
p1.segmentEdgeTo = p.edgeTo;
Path p2 = p1.extract();

Path4CHAlt は

public class Path4CHAlt extends Path4CH {
    private boolean switchWrapper = false;
    public EdgeEntry segmentEdgeTo;
    public EdgeEntry segmentEdgeEntry;

    public Path4CHAlt( Graph g, FlagEncoder encoder )
    {
        super(g, encoder);
    }

    public Path4CHAlt setSwitchToFrom( boolean b )
    {
        switchWrapper = b;
        return this;
    }

    @Override
    public Path extract()
    {
        System.out.println("Path4CHAlt extract");
        if (edgeEntry == null || edgeTo == null || segmentEdgeEntry == null || segmentEdgeTo == null)
            return this;

        if (switchWrapper)
        {
            EdgeEntry ee = edgeEntry;
            edgeEntry = edgeTo;
            edgeTo = ee;

            ee = segmentEdgeEntry;
            segmentEdgeEntry = segmentEdgeTo;
            segmentEdgeTo = ee;
        }

        EdgeEntry currEdge = segmentEdgeEntry;
        while (EdgeIterator.Edge.isValid(currEdge.edge))
        {
            processEdge(currEdge.edge, currEdge.adjNode);
            currEdge = currEdge.parent;
        }
        currEdge.parent = edgeEntry;

        currEdge = edgeEntry;
        while (EdgeIterator.Edge.isValid(currEdge.edge))
        {
            processEdge(currEdge.edge, currEdge.adjNode);
            currEdge = currEdge.parent;
        }
        setFromNode(currEdge.adjNode);
        reverseOrder();

        currEdge = segmentEdgeTo;
        int tmpEdge = currEdge.edge;
        while (EdgeIterator.Edge.isValid(tmpEdge))
        {
            currEdge = currEdge.parent;
            processEdge(tmpEdge, currEdge.adjNode);
            tmpEdge = currEdge.edge;
        }

        currEdge.parent = edgeTo;

        currEdge = edgeTo;
        tmpEdge = currEdge.edge;
        while (EdgeIterator.Edge.isValid(tmpEdge))
        {
            currEdge = currEdge.parent;
            processEdge(tmpEdge, currEdge.adjNode);
            tmpEdge = currEdge.edge;
        }
        setEndNode(currEdge.adjNode);
        return setFound(true);
    }
}

これは常に機能しているわけではありません。Path4CH で例外が発生します

java.lang.NullPointerException
at com.graphhopper.routing.ch.Path4CH.expandEdge(Path4CH.java:62)
at com.graphhopper.routing.ch.Path4CH.processEdge(Path4CH.java:56)
at com.graphhopper.routing.PathBidirRef.extract(PathBidirRef.java:95)
at com.graphhopper.routing.DijkstraBidirectionRef.extractPath(DijkstraBidirectionRef.java:99)
at com.graphhopper.routing.AbstractBidirAlgo.runAlgo(AbstractBidirAlgo.java:74)
at com.graphhopper.routing.AbstractBidirAlgo.calcPath(AbstractBidirAlgo.java:60)

パス内

java.lang.IllegalStateException: Edge 1506012 was empty when requested with node 1289685, array index:0, edges:318
at com.graphhopper.routing.Path.forEveryEdge(Path.java:253)
at com.graphhopper.routing.Path.calcInstructions(Path.java:349)

何が間違っているのかわかりません。私は本当にこれでいくつかの助けを使うことができます.

ありがとう。

4

1 に答える 1

0

この問題を解決しました。

DijkstraBidirectionRef.calcPath 内で、任意のノードからソース ノードと頂点ノードまでの最短パスを計算しようとしていました。

calcPath への元の呼び出しが QueryGraph で動作し、内部で LevelGraphStorage を使用して DijkstraBidirectionRef の新しいオブジェクトを作成していたため、エラーが発生していました。

QueryGraph がソース ノードとターゲット ノードの仮想ノードとエッジを作成する可能性があるため、これは問題でした。LevelGraphStorage で動作する calcPath(node, virtualNode) を呼び出すと、例外がスローされていました。

修正は、DijkstraBidirectionRef を作成した後に algo.setGraph(queryGraph) を呼び出すことでした。

于 2014-04-14T15:52:21.463 に答える