Arcflag

Arcflag (. Tightly edges flag ) (2005, Mohring et al.), Arc flag or Arcflags is a targeted acceleration technology for the Dijkstra - algorithm for searching the shortest path between two nodes in an edge-weighted graph . The basic idea, as with most acceleration techniques for Dijkstra, is to cleverly reduce the number of edges to be considered to a fraction compared to those which would have to be considered when executing the Dijkstra algorithm. First of all, each edge of the graph is enriched with flag information, which ultimately decides during the path search whether this edge must be taken into account for the search.

Precalculation

Graph partitioning

The graph to be considered is first broken down into partitions with node cardinality as similar as possible . In order to keep the effort of the precalculation in the next step as low as possible, it is advisable to pay attention to the smallest possible number of cut edges between partitions. A simple method is the recursive, alternating horizontal and vertical division of the graph at the point that achieves a good compromise between a similarly large node cardinality and a small number of intersecting edges between the partitions. See the data structure kd-tree . ${\displaystyle k}$ ${\displaystyle P_{1},\ldots ,P_{k}}$

In the following, let the set of nodes, the set of edges within the partition and the set of edges going out of the partition (whose start nodes are in , but the end nodes are not) for . ${\displaystyle V_{i}}$ ${\displaystyle E_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle E_{i}^{+}}$ ${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle i=1,\ldots ,k}$

Arcflag calculation

In the second step, the set of edges of the overall graph is determined for each partition , which are part of a shortest path that ends at a node within the partition . In other words: A search is made for the edges over which an optimal path leads into the target partition, or those edges are sorted out which are of no relevance for a path search into the target partition. The information as to whether an edge is part of a shortest path is called an arc flag . ${\displaystyle P_{i}}$ ${\displaystyle P_{i}}$

The calculation of this set of edges is very computationally intensive and is usually carried out using a backward search from the end node per cut edge . So we seek "from the partition out " the entire graph of shortest paths from that in the partition into lead. The arc flag is set for every edge that is part of at least one shortest path tree of these searches. The flag is also set for all edges that run within the partition ( ). ${\displaystyle E_{i}^{+}}$ ${\displaystyle E_{i}}$

Ultimately, this process results in an amount of information of bits per edge in the overall graph, with which the graph is enriched for the path search described below. ${\displaystyle k}$

Path search with Arcflag information

A search query on a graph enriched by Arcflags is principally done with the help of the classic Dijkstra algorithm. First, however, the partition is determined in which the target node of the search query is located (hereinafter “target partition”). If a rigid geometric grid, a kd tree or a similar principle was used for the partitioning , this can be determined relatively easily. However, when partitioning any shapes (polygons), this step may be a bit more time-consuming.

In the actual path search subsequently carried out using Dijkstra, when all neighboring nodes of the node to be processed are determined, only those are considered for whose edge the respective arc flag of the target partition is set. After completing the Dijkstra algorithm, no further calculation is necessary and it is guaranteed that the path found actually corresponds to the shortest.

advantages

• The implementation of the search algorithm in the application program is very simple, since in comparison to the implementation of a classic Dijkstra algorithm on a graph without additional information, no major modifications have to be made in order to take existing Arcflag information into account.
• Arcflag is a very effective acceleration technique for path searches and achieves acceleration factors (compared to the classic Dijkstra) in the range of a few hundred to a thousand on large road networks such as Germany or Europe and thus enables route searches in the millisecond range using, for example, approx. 64 partitions.
• The information that must be available to the application program in addition to the graph is limited (in the above example 8 additional bytes per edge).

disadvantage

• The computation of the flag information is very computationally intensive, since with increasing graph size not only the computing time of a search over the entire graph increases, but also the number of intersecting edges of the partitions from which such a search is carried out. Using alternative, but more complex calculation methods (e.g. PHAST algorithm), however, this step can be carried out more quickly.
• The calculation of alternative short paths (by removing certain edges, e.g. construction sites that are not passable or avoiding tolls in the road graph) cannot benefit from Arcflag information. Subsequent changes in edge weights (e.g. change in speed at construction sites or consideration of traffic jam information) also mean that the flag information is no longer valid. In both cases an application program must i. d. R. fall back on the classic Dijkstra. In the meantime, however, there are approaches to combine dynamic graphs with arc flags.

See also

• Dijkstra's algorithm for finding the shortest path
• Pseudocode of the Dijkstra algorithm

Footnotes

1. ↑ Paper on Arc Flags (English): http://dl.acm.org/citation.cfm?doid=1187436.1216585 or archive link ( memento of the original from August 20, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. 
2. ↑ Paper on the PHAST algorithm (English): http://research.microsoft.com/pubs/138638/phastTR.pdf
3. ↑ Arc flags in Dynamic Graphs (English): http://i11www.iti.uni-karlsruhe.de/extra/publications/bdd-afdg-09.pdf