What are virtual edges and how are they used in the current Map Matching implementation?

Open Source Routing Engine Map Matching
1

Hi, I have looked through the source and documentation and notice Graph Hopper uses this notion of “virtual edges”. This is not a concept I am familar with, so what are they? And what purpose do they serve?

Secondly, I notice they are used in the current map matching implementation, can you explain how they are used during map matching? Particularly code such as, queryGraph.lookup(allQRs).

2

It is indeed not explain in the docs, which we should fix. I’ll explain here and update the docs later.

GraphHopper does routing and for this it needs a road network representation. For this it uses nodes and edges and e.g. Dijkstra or whatever algorithm to efficiently traverse this graph. These nodes are named tower nodes, see here for the explanation.

Now when you query for a route you do not need junction-precise but GPS-precise routes, otherwise you’ll get lots of trouble.

To make this possible we introduce one new virtual node x and virtual edges A-x, x-B for every query located on the edge A-B:

\                /
 A----x---------B
/                \

But we need to decouple queries from each other and therefor we create a very lightweight graph called QueryGraph for every query which handles also stuff like two queries on the same edge.

The virtual nodes and edges have a higher int ID than graph.getNodes() or allEdges.getMaxId()

So the call queryGraph.lookup(allQRs) will set the virtual or junction node of the QueryResults and make them “valid”.

Let me know your questions if this does not fully answer your question :slight_smile: !

update: added now here

3

Thank you, I think I now understand how and why virtual edges/nodes are used in GH.

1 Like