1

我正在研究使用通过节点方法生成备用路径的实现。

在检查局部最优性时，我执行以下操作

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 的路径是 <= 未打包边的长度，我通过节点接受这个并按如下方式构造备用路径。

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 回答