giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Angelo Immediata <>
Subject Information
Date Wed, 26 Mar 2014 10:11:26 GMT
Hi there

In my project I have to implement a routing system with good performance;
at the beginning this system should be able in giving routes information
only for one italian region (Lombardia) but it could be used for the whole
Italy (or world....)
Let's stop to the Lombardia for now. By reading OSM files I can create my
own graph in the best format i can use it; then I need to use Dijkstra (or
any other algorithm) in order to propose to the user K possible paths from
point A to point B (K becouse i need to show to the customer also the
alternatives). I can't use Contraction Herarchy algorithm becouse I need to
take care of external events that can modify the weights on my built graph
and this implies that I should create the "contracted" graph once again and
this can be a very onerous operation

By my experimentations, I saw that by reading the Lombardia OSM file I
should create a graph with around 1 million of vertexes and 6 million of
edges and I was thinking to use Giraph to solve my issue (I saw this link where you talked about shortestpaths
I have a couple of question for you giraph/hadoop gurus

   - does it make sense to use giraph for my scenario?
   - must i respect some graph format to pass to the giraph algorithm in
   order to have K shortest paths from point A to point B? If so....which
   format should I respect?
   - what would be perfomance by using giraph? I know that Dijstra
   algorithm problem is that it is using giraph will I be able in
   improving its performances on very large graph?

I know these can seem very basic questions, but I'm pretty new to giraph
and I'm trying to understand it

Thank you

View raw message