Understanding edge directions

Open Source Routing Engine
1

Hi Peter and everyone,

First off many thanks for creating and working on this code, it is very useful.

I am using the 0.7 version of GH, as a reference.

I am trying to understand how to associate the original direction of an edge with the direction traveled by the routing algorithm.

Here is a simple example, with three edges, A, B and C:

 A           B       C

2<-------1<-------4<-----3

The numbers are the nodes created. The reason for the strange sequence is the order the edges were added:

First add edge A, which creates 1 as the base node and 2 as adjacent
Then add edge C, which creates base node 3 and adjacent 4
Then add edge B. Since the tower nodes already exist, the base node is 4 and adjacent is 1

So now, if I route from 3 to 2 I get the following route:

Edge C, base 3, adj 4
Edge B, base 4, adj 1
Edge C, base 1, adj 2

So now I’m trying to figure out how the edge traversal compares with the original edge direction. I noticed in a couple of posts you suggested using the node comparison, that is, compare if base node < adj node.

But in this case, I would get true, false, true, which does not reflect the original edge direction. Am I wrong in using this? I notice there is a reverse property for each edge, but it’s not exposed to the interface. From looking at the code it looks like it’s used to determine the geometry extraction, which is in line with the true direction of the edge. Is there something that exposes that value? I tried using the isForward function but those don’t return the true direction of the edge.

Let me know if I misunderstood this.

Many thanks.

Daniel

2

Edge C, base 1, adj 2

Here you mean Edge A?

If you use the EdgeIteratorStates returned from the Path object, then they already have the correct direction. (e.g. first would be with base=3 etc)

3

Hi Peter,

You are correct, I meant Edge A, sorry. But even though I get the edges with the correct direction, I have no idea how that direction relates to the original direction of the edge. If I traverse the route in the opposite direction, how do I know if that is the “reverse” (as originally defined by the edge) or “forward” (as originally defined by the edge)? Just knowing that the edges are in order doesn’t help me determine if the travel is in the original direction or not.

For example, say the direction I defined those edges in my example are meant to mean “generally east”, where the opposite direction means “generally west”. So I need to know if I traveled the route “generally east” or “generally west”. This is just an example, my actual use case is a little bit more complex.

I found a workaround, which is inefficient but does the job. I record the original start and end nodes for each edge when they are added to the graph. Then I compare the base and adjacent nodes of the traveled edge against those originals and can obtain direction. But I know that internally the edge does something like this when extracting the geometry using that reverse property internal to the edge. I was thinking that simply exposing that property as read only would help folks who need to know the relationship of the original edge definition to the traveled edge.

4

Then the EdgeIterator State has the correct state associated and then the last edge has a base node of 4 and “forward” then would be from 4 to 3

“generally west”.

For that you can call edge.fetchWayGeometry and pick the first and last node. And again, the returned PointList already has the correct order.

This is just an example, my actual use case is a little bit more complex.

I still do not fully understand what exactly your problem is. In general you do not have to know any internal state of an EdgeIteratorState just use the provided methods and it should have already the correct direction.

5

Hi Peter,

I think we are talking about two different things when we mean the correct direction. The edge list and way geometry from the routing algorithm is indeed in the correct direction of travel along the route.

But that is not the direction(s) I want. For each edge that was defined in the graph, originally it had an orientation (whether it’s a one way or bidirectional). That original direction is no longer available to the user once the graph is created. You cannot retrieve it just by fetching the geometry after routing, because that geometry is automatically reoriented in the direction of the routing travel. That is not what I want. I want the original (as originally imported into the graph) orientation of the edge.

And I think that information is there in the reverse flag. All I am asking simply is to expose that flag, read only, in the EdgeIterator interface. Do you not agree that the reverse flag can be useful to the end user? At the very least it cannot harm to expose it as read only.

6

I still don’t understand your use case. Maybe you need encoder.isForward(edge.getFlags())?

Do you not agree that the reverse flag can be useful to the end user?

I can’t agree, as I do not understand it :slight_smile: … (and private data should be exposed)

7

Thank you Peter for your time. I will continue with my custom solution then.

8

I’m pretty sure you do not need it (but you have to explain it so that I understand your problem …)

9

Yeah, I wish I was better at explaining it.

Maybe make one more try. Imagine that every edge added to the graph has an inherent direction and has a list of attributes that depends on that direction… say a list of house numbers for a one way street. And the house numbers don’t have a specific location, it’s just a list, say for the sake of the example

But that street can be traversed both ways by foot for example. So if I’m walking through that street in one direction, I would like to see that list in the “proper” order. So if I travel along the one way I want the list in the original order. If I travel against the one way then I would like to see the list in the reverse order. Since the list is just an attribute of the way itself and so the house numbers are not tied to actual locations, the only way to know which way the list to be sorted is to know the relationship between the travel direction and the one way direction. That relationship changes depending on which way I travel through the road.

Graphhopper “knows” that relationship through that reverse property. As I understand it, it is a property that tells the edge in which order to extract flags and pillar/tower nodes, so it is an important relationship that the edge stores internally and uses it. I just thought that it would also be something the end user could benefit from in relating the original imported data to the data presented by the routing algorithm.

Anyways, not a big problem Peter. Like I said, I wrote a solution which is not ideal but does what I need.

Thank you for your time.

10

Ah, ok, for external attributes you indeed need some more ‘direction’ information. A usual solution would be if you store a direction dependent attribute “0 vs 1” (like it is done with forward/backward or the two weight speed in Bike2WeightFlagEncoder) and it is correctly fetched. But this is a bit hard to implement (see here)

A simpler solution that we implemented for DataFlagEncoder (but not the other encoders) is to use the bit0 of the flags to detect this direction:

encoder = new CustomDataFlagEncoder();
encoder.isExternalForward(edge.getFlags())

// where you should be able to implement isExternalForward via
class CustomDataFlagEncoder extends DataFlagEncoder {
  public boolean isExternalForward(long flags) {
      return isBit0Empty(flags);
  }
}

Haven’t tested it … so I could be wrong :slight_smile:

At least there has to be a way which avoids internal attributes of the graph storage being exposed

11

Oh I see, encoding that in the flags is probably a cleaner solution, thanks for that idea! I like that DataFlagEncoder solution really, but I don’t think that is available in the 0.7 version? At least I don’t see it.

But I can probably add that as a custom encoder (adding the code from your newest version). That may be the way to go. Thanks for that Peter, glad I was finally able to explain my problem.

12

Can’t you update to 0.8?

glad I was finally able to explain my problem.

Sometimes I’m a bit slow :wink:

13

Lol Peter it’s not you, sometimes I have trouble explaining myself. I’ll look into updating to 0.8 at some point, but there are some wrapper classes I created that may have to change. Last time I upgraded from 0.4.1 to 0.7 I needed to do that.

But I followed your idea and your bie2weight example and implemented a very simple solution that works perfect! Since I don’t use speed in my edges (I have a custom weight algorithm that pulls speed dynamically, for a variety of reasons), I used the bike2weight encoder and set the speed and reverse speed to some known values, then check the traveled edges to see which one of those values match the speed extracted from the edge. Works great!

I initially tried to use the car encoder btw, but for some reason it would treat speed and reverse speed as the same thing. I didn’t dig into the code to find out why though.

Again, thanks for the help and the pointers, much appreciated.

14

Currently only DataFlagEncoder (“the future”) and Bike2WeightFlagEncoder can have two speed values (one for each direction)

Again, thanks for the help and the pointers, much appreciated.

Great that it worked out for you :slight_smile: !

15

Hi there,
We are needing a similar solution to detect directionalityof an edge relative to how the geometries were defined in the original OSM map. We also need to store the edge position relative to the original way definition, represented as an index.
For example, if a way consists of 3 edges A->B, B->C, C->D, then the edges would have index 0, 1, 2 on that way.
For deal with directionality, we tried the suggestion of using DataFlagEncoder along with CarFlagEncoder:

_hopper.setEncodingManager(new EncodingManager(carFlagEncoder, dataFlagEncoder))

But we are getting this error:
Encoders are requesting 37 bits, more than 32 bits of way flags. Decrease the number of vehicles or increase the flags to take long via graph.bytes_for_flags: 8
java.lang.IllegalArgumentException: Encoders are requesting 37 bits, more than 32 bits of way flags. Decrease the number of vehicles or increase the flags to take long via graph.bytes_for_flags: 8
at com.graphhopper.routing.util.EncodingManager.registerEncoder(EncodingManager.java:198)

What does this mean and what can be done?
Thanks,
Trang