Is possible two edges from one node to another with the same direction?

Hi,

I’m trying to understand in what cases a graph can contains a node with two edges from one node to another with the same direction. I’m processing an UK map and I found some nodes with that pattern. Any idea?

Thanks

You mean two edges between the same two nodes? That happens whenever two junctions (nodes) are connected by two ways (like a street and a separate foot path for example). It is also possible that two nodes were connected by two ways accidentally.

Yes two edges between the same two nodes. I load an UK map for car profile in Graphhopper and when try to iterate for node example: node 13071 I get the following edges:
baseNode → adjNode → Distance → shortcut → edgeId

13071 → 13066 distance: 238.532 — true -->16971295

13071 → 13071 distance: 444.968 — true -->16971294

13071 → 13067 distance: 319.276 — true -->16971293

13071 → 13071 distance: 266.091 — true -->16971292

13071 → 18971 distance: 303.36 — true -->16971291

13071 → 13066 distance: 442.187 — true -->16971290

13071 → 18971 distance: 352.101 — true -->16971289

13071 → 13071 distance: 314.832 — true -->16971288

13071 → 13071 distance: 250.983 — true -->16971287

        int base = 13071;
        RoutingCHEdgeIterator iter = edgeExplorer.setBaseNode(base);
        while (iter.next()) {

            int adjNode = iter.getAdjNode();
            double weight = calcWeight(iter, false, base);
            double distance = calcDistance(iter);
            long time = calcTime(iter, false, base);

            System.out.println("#### "+ base + " -> " + adjNode + " distance: " + distance + " --- " + iter.isShortcut() + " -->" + iter.getEdge());
        }

Ah, these are CH shortcuts, not ‘edges’. And yes, if you have enabled turn costs for your car profile this is expected. You are talking about loop shortcuts (a shortcuts going from one node back to the same node), like 13071->13071, right? First it sounded like you were talking about two different nodes that are connected by more than one edge?

Yes I was talking about shortcuts but from one node to another not the loop ones:

13071 → 18971 distance: 303.36 — true -->16971291

13071 → 18971 distance: 352.101 — true -->16971289

Ok then you should add iter.getOrigEdgeKeyFirst() and iter.getOrigEdgeKeyLast() to your logs, and they must be different for the two cases. If they are also identical that would be unexpected. There can be different CH shortcuts between the same two nodes, but with different original first/last edges.

Ok, yes are different:

2966295 → 537 distance: 1738.051- 19109/5504570

2966295 → 537 distance: 1658.88 - 19109/5183034

Then once we are in that node, which is the shortest one? Because GH is selecting the longest one

When turn costs are enabled we aren’t really going from node to node, but rather from edge to edge, so which one is the shortest depends on the direction we are going (even when we end up at the same node). You can imagine standing at a junction and going to another junction either taking one or another road. The reason GH is selecting the longer edge in your case could be either that the weighting is not solely based on the distance (which weighting do you use?), or the presence of turn costs (there is a penalty when we do a turn onto the shorter edge).

Yes, I have turn costs:

Profile carProfile = new Profile("car");
        carProfile.setTurnCosts(true);
        CHProfile chCarProfile = new CHProfile("car");

Thanks @easbar for the clear explanation

1 Like
Powered by Discourse