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 in fact 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 options of a graphs: 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.

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.

 

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

Be the first to like.
Oktober 18th, 2016

Neue ArcGIS Javascript WebApp “WKS Online”

Unter http://www.lwf.bayern.de/wks hat die LWF am Freitag 14.10.16 wkseine neue WebApp zur Anzeige der Witterungsdaten von Waldklimastationen aus ganz Bayern veröffentlicht. Die App wurde mit der ArcGIS Javascript API entwickelt und ist nun neben dem Borkenkäfermonitoring die zweite WebApp der Bayerischen Forstverwaltung auf der Basis ihrer ArcGIS Server Plattform.

Hier gehts zur offiziellen Pressemitteilung.

Be the first to like.
Oktober 8th, 2016

GitHub vs Bitbucket

Recently I signed up for a GitHub account.
First I was a little annoyed reading and hearing sentences like “..and we’re also at GitHub – we’re embracing open source..”. Aha.
Any company that sells proprietary software was now on GitHub: Apple, ESRI, Microsoft, Google. Of course not with their core proprietary products.
But then I noticed that the community grew and I realized that some companies were not just riding the open source wave for getting “code credibility” but really released more and more code open source.
And besides that: it feels more comfortable knowing some company hosts your code in the cloud with a DVCS. So I decided to sign up.

The difference
I already have a Bitbucket repository but this is not public just because it’s not open source. And that’s the main difference between GitHub and Bitbucket in my opinon: GitHub is everything open source and public for anyone (unless you pay for private repositories) while at Bitbucket you can choose between private and public repos.
Of course GitHub works with git and Bitbucket with mercurial, but the tools are more or less the same regarding functionality.
I started with mercurial and it took 5 minutes to learn how to use git.
So that’s how I’ll handle it: GitHub for exchange with others and anything open source, Bitbucket for working with a team on private repos.
Thus it should not be “GitHub vs Bitbucket” but “GitHub and Bitbucket”.

From now on any code I discuss in this blog will be published at GitHub (@sommergis) and I’ll move the code over to it.

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

Be the first to like.
September 24th, 2016

Solving the Shortest Path Problem (1) – Intro

Shortest Path Problem

3 years later I’m back with a new article in my blog – time flies..

The Shortest Path Problem is a common problem to nearly anyone nowadays. Anyone who used a navigation system or Google Maps for finding the best route for the weekend trip has already sucessfully solved the shortest path problem.
A solution to the shortest path (in terms of distance, time or any arbitrary cost) is to find the best route from one point of a network (maybe a street network) to another.

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

https://en.wikipedia.org/wiki/Shortest_path_problem

There are several tools for solving this problem – even free of charge and on any platform. In the following article series I want to explore the usage and the performance of various graph libraries that offer a shortest path solver.

List of the packages I want to explore:

  • Google OR-Tools
  • LEMON Graph Library
  • Boost Graph Library (BGL)

Note: I deleted Google OR-Tools from the list, because anything with Google OR-Tools was a mess:

  • Installation first failed
    (recent Ubuntu installation package does not work – “make third_party” gives a “no rule defined for ‘third_party'”)
  • the API is too complicated (I found callbacks hard to understand in Javascript – I really don’t want to program with callbacks in C++
  • Be the first to like.
September 24th, 2013

pyMCFsimplex – Efficient Solving of Minimum Cost Flow Problems in Python

pyMCFsimplex – a Python Wrapper for MCFSimplex

pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) network simplex algorithm. Also important: MCFSimplex is open source software – it has been released under the LGPL license.

To get a feeling for the performance of MCFSimplex: it solves a MCFP of 50.000 nodes and 500.000 arcs in 5 seconds on a average linux box (2,2Ghz 6GB RAM, Ubuntu 64Bit). Another one: NetworkX (a pure python graph library) also has an implementation of the network simplex algorithm – but this one is magnitudes slower than e.g. MCFSimplex. I tried so solve the same MCFP (n = 50.000, m = 500.000) with NetworkX and terminated the process after 1 hour. I intend to publish more on performance tests in an upcoming article.
See also this paper for a MCFP benchmarks.

You may ask: So what about pyMCFsimplex? Well, you’ll get the performance of a well coded C++ MCFP solver with the simplicity of a Python API. Isn’t this nice?

1 andere Person mag diesen Artikel.
April 10th, 2013

Solving the Minimum Cost Flow Problem (6) – Google or-tools

Push-relabel algorithm: Google or-tools

At last we will solve the instance of a Minimum cost flow problem described in (1) with Google or-tools. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

So let’s see how the python API of google or-tools work:

# import graph from google or-tools
from graph import pywrapgraph

# Create graph
# Attention: add +1 for number of nodes and arcs, if your node-IDs begin with 1
# because google or-tools mcf solver internal counters are strictly zero-based!
num_nodes = 4 + 1
num_arcs = 5 + 1
# args: NumNodes * NumArcs
G = pywrapgraph.StarGraph(num_nodes, num_arcs)

# create min cost flow solver 
min_cost_flow = pywrapgraph.MinCostFlow(G)

# add node to graph with positive supply for each supply node 
min_cost_flow.SetNodeSupply(1, 4)
# add node to graph with negative demand for each demand node 
min_cost_flow.SetNodeSupply(4, -4)
# you can ignore transshipment nodes with zero supply when you are working with
# the mcfp-solver of google or-tools

# add arcs to the graph
arc = G.AddArc(1, 2)
min_cost_flow.SetArcCapacity(arc, 4)
min_cost_flow.SetArcUnitCost(arc, 2)
arc = G.AddArc(1, 3)
min_cost_flow.SetArcCapacity(arc, 2)
min_cost_flow.SetArcUnitCost(arc, 2)
arc = G.AddArc(2, 3)
min_cost_flow.SetArcCapacity(arc, 2)
min_cost_flow.SetArcUnitCost(arc, 1)
arc = G.AddArc(2, 4)
min_cost_flow.SetArcCapacity(arc, 3)
min_cost_flow.SetArcUnitCost(arc, 3)
arc = G.AddArc(3, 4)
min_cost_flow.SetArcCapacity(arc, 5)
min_cost_flow.SetArcUnitCost(arc, 1)

# solve the min cost flow problem
# flowDict contains the optimized flow
# flowCost contains the total minimized optimum
min_cost_flow.Solve()
flowCost = min_cost_flow.GetOptimalCost()

print "Optimum: %s" %flowCost

As one can see the python API of google or-tools is also pretty handy although everything is coded in C++. The python API was created using SWIG. The biggest caveat one can run into is the fact that the MCFP solver in google or-tools is strictly zero based. So adding nodes starting from 1 ..n result in strange errors if you don’t size the initial graph properly: just add +1 to the number of nodes and the number of arcs if your node ids start with 1.

Alternatively you can pass the proper number of nodes and arcs at the graph initialization and substract -1 from all of your node ids so they are zero based. But be careful – any arc is made of the node ids so you’ll have to substract -1 at the arcs level also.

Be the first to like.
April 10th, 2013

Solving the Minimum Cost Flow problem (5) – NetworkX

Network Simplex Solver: NetworkX

We will solve the instance of a Minimum cost flow problem described in (1) with NetworkX. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

Solving a Minimum Cost Flow Problem with NetworkX is pretty straight forward.

# import networkx
import networkx as nx

# create directed graph
G = nx.DiGraph()

# add node to graph with negative (!) supply for each supply node 
G.add_node(1, demand = -4)

# you can ignore transshipment nodes with zero supply when you are working with the mcfp-solver 
# of networkx
# add node to graph with positive (!) demand for each demand node
G.add_node(4, demand = 4)

# add arcs to the graph: fromNode,toNode,capacity,cost (=weight)
G.add_edge(1, 2, capacity = 4, weight = 2)
G.add_edge(1, 3, capacity = 2, weight = 2)
G.add_edge(2, 3, capacity = 2, weight = 1)
G.add_edge(2, 4, capacity = 3, weight = 3)
G.add_edge(3, 4, capacity = 5, weight = 1)

# solve the min cost flow problem
# flowDict contains the optimized flow
# flowCost contains the total minimized optimum
flowCost, flowDict = nx.network_simplex(G)

print "Optimum: %s" %flowCost  #should be 14

As you can see the code is very readable and easy to understand. The only thing you could get trouble with in the formulation of a min cost flow problem with networkx is the fact that the supply nodes get a negative supply value (because the python attribute is called “demand”) while the demand nodes require positive demand values.
This differs from the usual mathematical notation of supply and demand values in the network flow problems where supply values are positive and demand values of negative sign.
Also note that you only need to add supply and demand nodes to the graph. You don’t have to care of the transshipment nodes.

4 Leute mögen diesen Artikel.