Solving the Shortest Path Problem (5) – Benchmarks

This article of 2012 at http://stegua.github.io/ shows, that the type of the priority queue of a shortest path solver is crucial for the solving time.
You have to agree with that, but there is another point to mention: the choice of the graph representation.
I wanted to spend some more time on the comparison of the graph libraries LEMON and BGL and so I modified some of the code and ran the following tests on it.

The code was compiled using GCC 4.8.4 with the the following switches: -O2 -m64 -std=c++11. My test machine is a laptop with an Intel 4-Core i3@2,4 Ghz. You can download the graph instances from the DIMACS site.

BGL’s Dijkstra d-ary Heap (d=4)
Boost’s Graph Library offers two variants of a Dijkstra shortest path solver implementation. A regular one dijkstra_shortest_path and a variant that does not use an internal color map of nodes (dijkstra_shortest_path_no_color_map). Both of them use by default a d-ary Heap with d=4 which is actually a quad heap queue. Unfortunately there is no easy way to change the heap in the dijkstra implementation.

There is no significant difference comparing the solving time of each of them, if you do not change the graph structure.
Using the BGL with street networks you have two flavours of a graph: the widely known adjacency_list and a representation that you should look at if you’re dealing with sparse graphs as street networks are: the compressed_sparse_row_graph.

Here are the results.


Graph Nodes Arcs m/n ratio adjacency list [sec] adj RAM footprint [MB] compr. sparse graph [sec] csr RAM footprint [MB]
Western USA 6'262'104 15'248'146 2.4 2.089 606 1.536 458
Central USA 14'081'816 34'292'496 2.4 5.809 1'368 4.477 1'040
USA 23'947'347 58'333'344 2.4 8.664 2'318 6.698 1'770

For these graphs the compressed sparse row graph always outperforms the shortest path search on a graph represented with an adjacency_list. The memory usage is also better on compressed sparse row graphs than using adjacency_lists.

LEMON’s Dijkstra d-ary-Heap (d=4)

LEMON’s default Heap for the dijkstra shortest path solver is by default a binary heap. In order to compare against the BGL’s d-ary implementation with d=4 I changed the heap also to a quad heap in LEMON. Now LEMON has three graph structures to offer: ListGraph, SmartGraph and StaticGraph. All types also have the directed variant (e.g. ListDigraph). From ListGraph over SmartGraph to StaticGraph the flexibility of the graph structure will be getting lesser in exchange for efficiency in graph searches. So there is a trade off between flexibility and speed.

Overall LEMON performs better when you look at the solving times as BGL and the StaticGraph of LEMON provides the fastest results.

Graph Nodes Arcs m/n ratio ListDigraph [sec] SmartDigraph [sec] StaticDigraph [sec]
Western USA 6'262'104 15'248'146 2.4 1.144 0.985 0.859
Central USA 14'081'816 34'292'496 2.4 2.116 1.887 1.749
USA 23'947'347 58'333'344 2.4 6.358 5.605 5.019

LEMON’s Dijkstra 2-Heap

If you change the Quad Heap priority queue to a Binary Heap in LEMON you gain even more performance. Note that LEMON’s Dijkstra implementation defaults to the Binary Heap, so there would be no need to change the heap in most cases.

Graph Nodes Arcs m/n ratio ListDigraph [sec] SmartDigraph [sec] StaticDigraph [sec]
Western USA 6'262'104 15'248'146 2.4 1.109 0.970 0.822
Central USA 14'081'816 34'292'496 2.4 2.005 1.797 1.658
USA 23'947'347 58'333'344 2.4 6.181 5.553 4.750

chart3

LEMON’s Dijkstra 2-Heap – Memory usage

Now let’s look at the memory usage of LEMON’s 2-Heap Dijkstra using different graph structures.

Graph Nodes Arcs m/n ratio ListDigraph [MB] SmartDigraph [MB] StaticDigraph [MB]
Western USA 6'262'104 15'248'146 2.4 352 270 450
Central USA 14'081'816 34'292'496 2.4 795 606 1'016
USA 23'947'347 58'333'344 2.4 1'352 1'024 1'721

chart4

For me very surprisingly: SmartGraph is the winner! I thought that the static variant is also memory friendlier than the SmartGraph implementation.

Best bet of BGL’s Dijkstra and LEMON’s Dijkstra

Now if we put all of the results together, I would say LEMON is the clear winner regarding solving time and memory footprint if you go for the default binary heap and the SmartDigraph of LEMON. There is a noteable difference from BGL’s 2,08 secs with an adjacency_list and LEMON’s SmartDigraph with 0,97 secs or even 0,82 secs using the StaticDigraph on the smallest graph. If you use BGL’s dijkstra on street networks you should use the compressed sparse row graph structure.

Graph Nodes Arcs m/n ratio LEMON 2-Heap SmartDigraph [sec] LEMON's RAM fp [MB] Boost compr. sparse graph [sec] Boost's RAM fp [MB]
Western USA 6'262'104 15'248'146 2.4 0.970 270 1.536 458
Central USA 14'081'816 34'292'496 2.4 1.797 606 4.477 1'040
USA 23'947'347 58'333'344 2.4 5.553 1'024 6.698 1'770

I forked the repository of stegua and made a few changes to his version of the dijkstra implementations. The code is available on GitHub.

Be the first to like.

2 Kommentare zu “Solving the Shortest Path Problem (5) – Benchmarks”

  1. Good job on the benchmarking.

    People always ask whether the LEMON is more efficient than BGL.

Kommentar hinzufügen