Showing posts with label Other. Show all posts
Showing posts with label Other. Show all posts

Friday, 21 October 2011

Contraction hierarchies (part 4)

When preprocessing of original graphis is done, we need to build CH graph which consists of node order and original graph with shortcut edges introduced in preprocessing stage.

On CH graph we can make queries to find shortest paths with modified bidirectional Dijkstra's algorithm - algorthm performs forward search from starting node s expanding to the nodes that have higher order and backward search from target node t to the nodes that have lower order. If the shortest path exists, those two searches will meet at some node v. A shortest path from s to t consists from paths from s to v and from v to t.


The shortest paths found by this algorithm have particular form:


< s = u0, u1, ..., up = v, ..., uq = t >, p, q ∈ N

ui < ui+1 za i ∈ N, i < p 
uj > uj+1 za j ∈ N, p ≤ j < q
 A path found by a query is the shortest path because of preprocessing stage. In preprocessing stage we transformed graph introducing shortcut edges,which represents the shortest paths that algorithm does not take into consideration.

Now let's assume (for forward search, identical thing stands for backward search) that there exists a path that is shorter than the one we found with this algorithm:


So, let's say that at some point there exists a subpath that is shorter than path. Because algorithm expands towards nodes that have higher order, order of uk node must be lower than order of uk-1 and uk+1 nodes. Because of that fact, in preprocessing stage that path would be represented as shortcut edge with equal lenght and therefore, no such path that is shorter than the one algorithm found can exists.

Monday, 15 August 2011

Contraction hierarchies (part 3)

Formal definition of CH would be:

CH = (V, E'), "<", where V is set of nodes, E is set of edges of original graph with introduced shortcut edges and "<" is relation that defines different levels of contration hierarchy.

Levels/order of nodes in CH can be arbitrary. The main point is that shorcuts are introduced when necessary. To understand when shortcut is necessary, one has to understand the searching algorithm. Searching algorithm (bidirectional Dijkstra's algorithm) only relaxes edges that are connected to the nodes that are higher in CH than current node in one direction, and vice versa. That way, algorithm wouldn't find shortest paths and because of that we need to introduce new edges to the graph that represents existing shortest paths that algorithm don't takes into consideration. Not all shortest paths needs to be restored as new shortcut edges, it's enough to take in consideration adjacent nodes of some node that are higher in CH (sub-path of some shortest path is shortest path himself).




Algorithmically:


  • add order/levels to the graph nodes
  • for each node, respecting order, get it's adjacent nodes of higher order and find if shortest path between each pair of them goes through current node and if it is, add shortcut edge

Lets say that we take in cosideration just 2 adjacent nodes (from, in general, "n" of them):
  
 From this picture, if shortest path from v to w goes through node u that is lower in CH, new egde has to be added the CH graph so that shortest paths that searching algorithm takes in consideration are preserved.




Weight of new egde is equal to path distance from v to w.

Monday, 28 February 2011

Contraction hierarchies (part 2)

So, in general, there are two distinct phases: preprocessing of original graph (usually it takes more than a hour to finish) and queries (less than a second).


Contraction hierarchy is extreme case of hierarchy approach. Every node in the graph is represented as it's own level of hierarchy. This can be achieved in many ways, but one way is obvious and simple. If |N| is number of nodes in the graph, every node is enumerated from 1 to |N|. That way in hierarchy every node is represented as distinct level.


As searching algorithm, bidirectional Dijkstra's algorithm is used. It is classical Dijkstra's algorithm with some modifications. Algorithm searches from starting node in one direction and from ending node in other direction (this is classical bidirectional Dijkstra's algorithm), but it relaxes (see what relaxation is in Dijkstra algorithm pseudo-code) edges that are directed toward higher hierarchy nodes in one direction (essentially it expands towards higher hierarchy nodes) and edges that are directed toward lower hierarchy nodes in other direction. That way, searching algorithm wouldn't find shortest paths because it doesn't take in consideration shortest paths that aren't directed in a way algorithm searches. Because of that, all shortest path that are not directed properly have to be compensated in some way. This step is important because of validity of the algorithm.


So ... algorithm is bidirectional Dijkstra's algorithm. In one direction it relaxes edges that are directed towards nodes that are higher in the hierarchy (as I said, every node has it's own level in hierarchy) and opposite in other direction. Searching this way, not all shortest paths are taken into consideration and because of that algorithm would find inaccurate results. To restore shortest paths that aren't taken into consideration, a new edge is added to the graph. That edges are called shortcut edges and they represents existing shortest paths between two nodes in the graph.


(to be continued)

Wednesday, 26 January 2011

Contraction hierarchies (part 1)

And now something completely different. :)



"Contraction hierarchies" is new approach for solving shortest path problem in graph theory. Shortest path problem (http://en.wikipedia.org/wiki/Shortest_path_problem) can be solved using classical algorithms like Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). But, classical algorithms are not useful on large graphs (more than 10 000 nodes). Today's roads networks are represented as a graph with about 10 million nodes or more and algorithm is implemented on small devices (navigation devices, mobile devices, ...) which have limited computing power. A problem with classical algorithms is their speed of finding shortest path on large graphs and space required for running of the algorithm. That's why they're not practical even on fast computers - they can't finish finding shortest path on large graphs due to large space consumption. There have been many speedup techniques for finding shortest path in large graph and they are more or less successful in that task.

In general, speedup tehniques have two distinct phases: preprocessing of original graph and queries for finding shortest path. In preprocessing phase some information is extracted from graph and it's being used in query phase to speedup finding of the shortest path.

Modern navigational devices generally use some kind of modified (bidirectional) A* algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm) with hierarchical approach. That means that graph is devided according to node/road importance (local road, highway, ...) in preprocessing phase and then searching algorithm uses hierarchy to speedup finding of the shortest path (basic idea is that highway road is "faster" than local road). A problem with this approach is that there is no formal definition what highway is and what local road is (humans are manually doing that). Because of that errors are possible.
Also, searching algorithm is optimized in a way that it makes trade-off between speed and accuracy.


For that reasons new algorithms are reseached that are fast on large graphs and that give exact results.


(to be continued)