Artikel getaggt mit ‘Shortest Path’

Oktober 28th, 2016

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.

weiterlesen »

Be the first to like.

Oktober 27th, 2016

Solving the Shortest Path Problem (3) – Boost Graph Library

Boost Graph Library
The Boost Graph library (BGL) is a part of the famous Boost library.

C++ Boost
The BGL graph interface and graph components are generic, in the same sense as the Standard Template Library (STL).

As LEMON the BGL also relies on C++ templates and thus is a header-only library.

The list of provided graph algorithms is impressive. Its latest version 1.6.2 was updated in September 2016.

So we want to have a look into the API using the same agenda as in the previous article about the LEMON Graph Library:

  1. Prerequisites
  2. Populate a graph
  3. Setup a shortest path solver
  4. Solve it, get the cost and the path

weiterlesen »

Be the first to like.

September 28th, 2016

Solving the Shortest Path Problem (2) – LEMON Graph Library

LEMON Graph Library


LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks.

http://lemon.cs.elte.hu/trac/lemon

I like LEMON because of its nice and simple API. There is also a mailing list which offers quick support. Its latest version 1.3.1 was updated in August 2014.

So let’s see what’s on the agenda:

  1. Prerequisites
  2. Populate a graph
  3. Setup a shortest path solver
  4. Solve it, get the cost and the path

weiterlesen »

Be the first to like.