Node Based Graph Representation vs. Edge Based Graph Representation

wangyoucao577 commented 3 years ago

Read ETA Phone Home: How Uber Engineers an Efficient Route again, it mentioned:

Some people want to model road segments as nodes, and edges as the transition between one road segment to another. This is called edge-based representation, in contrast to the node-based representation mentioned before. Each representation has its own tradeoffs, so it’s important to know what you need before committing to one or the other.

But what exactly tradeoffs between the two models?

Node based vs Edge based graph representation discussed some, e.g., the edge based graph representation(a.k.a., edge-expanded graph representation or arc-based graph representation) is better to process turn costs, but its data size will increase by a factor 3.

As mentioned in https://github.com/Project-OSRM/osrm-backend/issues/4851#issuecomment-363028875, OSRM uses edge based graph representation to deal with turn too.
Also, OSRM uses 4 to estimate the increasing, which also explains some reason that why OSRM compiled data is so big. See https://github.com/Telenav/osrm-backend/blob/3906e34f2079617702a966b317c6431412852dfc/src/extractor/edge_based_graph_factory.cpp#L292-L294

Edge based graph representation is perfect for simple turns, include turn costs/restrictions. We don't need to consider turn anymore once the edge based graph generated.
However, complex restrictions or time restrictions are difficult to deal with in this case since we have to process all the information to edge based graph representation and record everything to perform in query. That's why OSRM hasn't support them yet, and maybe they'll never be supported in the future.
Process to edge based graph representation also may affect customzie performance in MLD. The input of osrm-customize are OSM NodeIDs, which means we have to convert OSM NodeIDs -> OSRM Edge Based Graph every time.

Dynamic information, for instance live traffic, become more and more important in these years, as well as the future. Node based graph representation might be better by this trending since it's more near the original graph, and will be easier to perform dynamic information.

A ideally approach might be CRP/MLD implemented on node based graph. Any open source choice?

wangyoucao577 commented 3 years ago

Some references:

CodeBear801 commented 3 years ago

@wangyoucao577 I think this is a very interesting problem to discuss. Here is some of our summary from previous notes(around 2010/2012)

Why

The major reason of abstracting node-based graph and edge-based graph is related how to handle turn cost, both of them is targeting hide complexity of geo graph and provide classic graph for upper layer.

Node based graph

My personal experience of graph abstraction is mainly based on this strategy. The key point is node based Dijkstra, during Settle() it use the idea of target node.

Edge based graph

Telenav's BJ lab has rich experience on Edge based graph. OSRM also use this strategy. Basically, it treat edge as node, and convert original node to many edges to represent different turns

It increases the size of graph, and as you said, hide complexity of simple turns, which make graph algorithm has better way to evaluate the performance.
There are good discussion in CRP's paper for why handling turn is important, FYI. My understanding is, for geo graph, turn complexity is a must consider factor to evaluate final algorithm, edge based graph put this in pre-processing which makes later step(HH, CH, CRP) has more accurate evaluation on algorithm based on different size of graph.

Problems

Besides abstraction, I think there are difference between this two abstractions. Such as this case: There are two links <1, 2> and <2, 1>, during graph contraction, whether shall we build a shortcut of 1 -> 2 -> 1. It is obvious for this simple case, but we met lots of similar issues during graph experiment during implementing HH/CH.

wangyoucao577 commented 3 years ago

@CodeBear801 Thanks for the information.

Whether should build a shortcut for u-turn is interesting. At the first glance, I think it's necessary otherwise graph is not completed. But yes, it's wasting. One more problem might be that u-turn can only be allowed at start/end of a road segment due to shortcut, but we may expect to allow u-turn in many small level roads. What's your decision of this case?

As you mentionded, the turn section(section 4) of CRP discussed it a lot, which I found that I haven't really understood before.
Capture some and add some comments here:

So far, we have considered a simplified(but standard representation of road networks, with each intersection corrsponding to a single vertex. This is not very realistic, since it does not account for turn costs(or restrictions, a special case).

[Jay]: It indeed mentions the node based graph representation. It's the classic graph in graph algorithm of computer science that doesn't consider turn by default.

Of course, any algorithm can handle turns simply by working on an expanded graph. A traditional representation is arc-based: each vertex represents one exit point of an intersection, and each arc is a road segment followed by a turn.
This is wasteful.

[Jay]: So the author thoughts that edge based graph representation is a traditional and wasteful method...

We proposed a compact representation in which each intersection becomes a single vertex with some associated information. If a vertex u has p incoming and q outgoing arcs, we associate a p*q turn table T to it, where T[i,j] represents the turn from the ith incoming arc into the jith outgoing arc.

[Jay] CRP proposes turn table, names it compact representation.

Dijkstra's algorithm, however, becomes more complicated. In particular, it may now visit each vertex(intersection) multiple times, once for each entry point. It essentially simulates an execution on the arc-based expanded representation.
To support the compact representation, MLD needs two minor changes. First, it uses turn-aware Dijkstra on the lowest level(but not on higher ones). Second, matrices in each cell now represent paths between incoming and outgoing boundary arcs(and not boundary vertices, as before). The difference is subtle. With turns, the distance from a boundary vertex v to an exit point depends on whether we enter the cell from arc(u,v) or arc(w,v), so each arc needs its own entry in the matrix. Since most boundary vertices have only one incoming(and outgoing) boundary arc, the matrices are only slightly larger.

[Jay] Dijkstra algorithm simulates an execution on the edge-based graph representation when relax with turn handling. That's exactly what we do in bidirectional Dijkstra/A*.

Telenav / osrm-backend