Artikel getaggt mit ‘Graph’

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 28th, 2016

Solving the Shortest Path Problem (4) – Comparison of LEMON and BGL

In the previous articles I explained the usage of the APIs of LEMON and Boost Graph Library (BGL). Now I want to sum up the differences of them. Of course this is very opinion-based.

1. Simplicity

LEMON has despite its template mechanism a clean and realtively simple interface. A few algorithms have predefined default template parameters which cover standard use cases. For example the Dijkstra Shortest Path solver uses a binary heap as priority queue.  The map concept of storing additional data on graphs is not very friendly regarding usability but is a guarantee for performance, because the core component only has to look after its internal IDs and not after some additional graph data.

By contrast you cannot say that the Boost BGL looks simple at first glance. I found it harder to understand, but it has flexibility to adapt changes. Especially the property map concept may be familiar to regular Boost users, but if you are new to this it’s not really clear.

2. Flexibility

The API of LEMON is flexible enough to change the many parameters of graphs, algorithms or internal structures like the heap type. Unfortunately there is little documentation on these advanced operations.

What I liked working with the BGL was the bundled property mechanism where you can „inject“ your custom class and convert that to some node or arc property. I missed in BGL the ability to change the heap type for the shortest path dijkstra. A big plus in my opinion is the so called visitor concept in the BGL. You are able to specify a visitor that allows custom functions in a standard algorithm, e.g. stopping the execution of the dijkstra algorithm at a certain total distance. But again implementing this is not an easy task.

So this time it’s a draw.

3. Algorithms

Both of the two libraries offer a huge list of graph algorithms if you are not only interested in shortest path algorithms.

Again the score is even in my opinion.

So to sum these things up, I enjoy using LEMON more. But what about the performance? I will write an extra article about this.

 

1 andere Person mag diesen Artikel.

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.