[GraphHopper] Graphhopper and Pg_Routing Bridge

Ciobota ciobota at gmail.com
Sat Jul 5 17:06:40 UTC 2014 

Sorry Mark, I don't have any experience with Postgres, I can't help with
that.



On Fri, Jul 4, 2014 at 8:16 PM, Markware Software Services <
markwaresoftware at gmail.com> wrote:

> Hi Daniel
>
> Great Answer, thanks so much for your time. I guess I have to learn Java
> and figure out HashTables now :(, your suggestion is worth putting some
> effort into.
>
> Do you, or anyone else have any thoughts about actually creating the graph
> using a Postgres database instead of an OSM xml File?
>
> The main reason for looking at this is that I could possibly substitute
> the OSMID with a new "Segment ID" or combination of both values (Allocating
> a unique Segment Id would be easy after the ways are split at intersecting
> nodes in Pg_Routing) to improve granularity
>
> The second reasons is that it will be easier to keep the mapping db,
> pg_routing db and the grapahhoper graph in sync with the minutely diff
> updates. For smaller areas (like disasters) we coudl make new graphs on a
> regular basis, hourly, daily, or whatever is needed
>
> In a disaster, the maps in a disaster area changes dramatically with the
> people form HOT and locals updating form Sat Images and we would need to be
> able to pick these up without having to run osmosis on a pbf file.
>
> I guess we could extract the database using osmosis, then run the
> graphhopper build graph routines on the extracted xml but it does seem like
> one extra unnecessary step
>
> Cheers
>
> Mark
>
>
>
>
>
> Regards
>
> Mark Cupitt
>
> "If we change the world, let it bear the mark of our intelligence"
>
> See me on Open Street Map <https://www.openstreetmap.org/user/Mark_Cupitt>
>
> See me on LinkedIn <http://ph.linkedin.com/in/markcupitt>
>
>
>
> *See me on StackExchange <http://gis.stackexchange.com/users/17846/mark-c>
> *
>
> ===============================================================================================
> The contents of this email are intended only for the individual(s) to whom
> it is addressed and may contain
> confidential or privileged information. If you are not the intended
> recipient, you must not disclose, copy, distribute,
> or use the contents of this email. If you have received this email in
> error, please notify the sender immediately and
> delete the email and any attachments.
> ===============================================================================================
>
>
>
> On Sat, Jul 5, 2014 at 1:48 AM, Ciobota <ciobota at gmail.com> wrote:
>
>> Hi Mark,
>>
>>  Happy to help.  To attempt to answer:
>>
>>  I think the newest version of GraphHopper allows the storage of way id's
>> with each edge.  Peter probably knows best, I can only guess from the
>> messages posted in the forum.  I haven't updated my version of GraphHopper
>> since early January, when I made the customization changes.
>>
>>  But you are correct, you will need the way id stored with every edge.
>>  And also yes, the way will be (as far as I know) that ways will be split
>> into multiple edges if they share a common node with another way (like at
>> crossings).  That's what I mentioned as granularity issues.  So, if you
>> want to only partially block a way, you will most likely do one of three
>> ways:
>>
>>  - a blocking node.  In this case in your weighting algorithm will pull
>> all the nodes from the edge as a line (don't need to get a way id in this
>> case, but it helps, see further down), then do a line/point intersection to
>> see if the blocking node is on the line.  If it is, then return infinity,
>> since you would consider that entire edge blocked.  This would still retain
>> a good bit of speed if the access cost for blocking nodes is kept low.  You
>> could keep that cost low if you store the blocking node location along with
>> the way id (that way you filter the returned blocking nodes to only those
>> relevant for the way).  I don't know much about Postgress sorry, we're an
>> Oracle shop, but if your database doesn't do caching, you can implement
>> your own cache in memory with a hashmap and update it from the database
>> every so often.
>>
>>  - a line.  This is for blocking spans along a way.  The reason why this
>> may be needed is for blockages that may span over more than one edge or
>> even more than one way (say, construction).  In this case you won't care
>> about way id's at all, but for each edge you would have to calculate the
>> intersection of the edge geometry with every blocking span.  There are ways
>> to speed this up, but it will be slower, maybe significantly so if there
>> are lots of spans.
>>
>>  - a polygon.  This would be a valid option for blockages that are areas
>> rather than specific spans along a way.  Same thing as above, you would do
>> an intersection of the edge geometry and all the blocking polygons.  This
>> would probably be the slowest of the three.
>>
>>  Btw, I would not do the indexed file at all.  The best mechanism imho is
>> to create an internal memory structure (like I mentioned, maybe a hashmap),
>> and have it refreshed from the database periodically.  At program startup
>> it should query the database and build the initial cache.
>>
>>  Btw, aside from the part about assigning way id's to edges, which may
>> already be present in the current coed, the weighing function would not
>> need to be part of the released code.  Peter provides a very elegant and
>> simple mechanism to tie in your own weighting algorithm with the
>> GraphHopper solver (I think he has an example in the released code).  As we
>> all have more or less unique needs for the cost function, implementing your
>> own weighting class is really the best way to go.
>>
>>  Hope this helps.
>>
>> Daniel
>>
>>
>>
>> On Thu, Jul 3, 2014 at 8:01 PM, Markware Software Services <
>> markwaresoftware at gmail.com> wrote:
>>
>>> Hi Daniel
>>>
>>> First, many thanks for the detailed reply. This is definitely worth
>>> investigating
>>>
>>> A couple of questions if I may. I am NOT a Java person at all but may
>>> have to invest some time learning it for this project if it pans out. A few
>>> questions if I may to make sure I understand the process correctly ..
>>>
>>> 1. The solution would mean a custom version of Graphhopper which would
>>> need to be updated every time a new version of Graphhopper is released? IS
>>> that correct? I was hoping to avoid this, but may not be able to.
>>> 2. The approach would be to make sure the way Id's were in the edges
>>> when the graph was built, correct?
>>> 3. Graphhopper would need to be modified to do the following, Change the
>>> OSM reader to read the cost form an external table. I would presume that
>>> this could be a Postgres Database, but it may have some performance
>>> limitations on the look-up. IN this case, we would need to write some kind
>>> of indexed file that would contain the cost data
>>> 4. If not the database, this cost file would need to be written out on a
>>> periodic basis. I would guess that writing it a temp file then renaming it
>>> to the correct file name may minimize the liklihood the file will be
>>> unavailable to graphhopper, however some logic may be needed to get
>>> graphhopper to lop a few times to allow for the file rename period before
>>> it bombs out.
>>> 5. PG_Routing segments all ways to intersection points so it should be
>>> enough to simply add a high cost to one or more segments (say a bridge that
>>> is out, road section flooded, etc)
>>> 6. The algorithm change would basically just need to add the retrieved
>>> cost from the file which would most likely be 0 if way is usable or a high
>>> number if it is not
>>> 7. I would guess that the Reverse Cost should also be considered in the
>>> same manner
>>>
>>> One issue that came t mind whilst I was typing this was the fact that
>>> pg_routing splits all the ways into small segments for intersection points.
>>> I presume that Graphhopper does the same, that means that multiple segments
>>> will have the same OSMid. This would only be a problem if it was a long
>>> road, for example a freeway. Flooding on part of a freeway should cause a
>>> detour, not take make the whole road unavailable.
>>>
>>> How realistic would it be to have a database lookup to obtain this
>>> information on each routing pass? Would kill the speed? I am unsure what
>>> sort of table should then be used if Postgres is not an option
>>>
>>> Could/Should this be made part of the standard Graphopper release?
>>>
>>> Again, many thanks for you reponse and ideas. Any observations or
>>> suggestions are very welcome.
>>>
>>> Kind Regards
>>>
>>>
>>> Mark Cupitt
>>>
>>> "If we change the world, let it bear the mark of our intelligence"
>>>
>>> See me on Open Street Map
>>> <https://www.openstreetmap.org/user/Mark_Cupitt>
>>>
>>> See me on LinkedIn <http://ph.linkedin.com/in/markcupitt>
>>>
>>>
>>>
>>> *See me on StackExchange
>>> <http://gis.stackexchange.com/users/17846/mark-c> *
>>>
>>> ===============================================================================================
>>> The contents of this email are intended only for the individual(s) to
>>> whom it is addressed and may contain
>>> confidential or privileged information. If you are not the intended
>>> recipient, you must not disclose, copy, distribute,
>>> or use the contents of this email. If you have received this email in
>>> error, please notify the sender immediately and
>>> delete the email and any attachments.
>>> ===============================================================================================
>>>
>>>
>>>
>>> On Fri, Jul 4, 2014 at 6:11 AM, Ciobota <ciobota at gmail.com> wrote:
>>>
>>>> Hi all,
>>>>
>>>>  By way of introducing myself I will attempt to offer maybe a
>>>> suggestion for a solution to this.  First off, I work for a railroad
>>>> company, and we have decided to migrate our routing code from a well known
>>>> commercial vendor to Graphhopper, which has turned out really well.  Many
>>>> thanks to Peter and all who have contributed.  So, as you can see, we don't
>>>> route on normal roads.  ;-)
>>>>
>>>>  Anyway, I think the version we use is from sometime in January, so
>>>> it's probably before there was a change to allow to store way id's as part
>>>> of the graph edges.  So we implemented our own by overriding the osm reader
>>>> and some minor changes to graphhopper (mostly exposing some private
>>>> variables).  We wanted to do this so we could do some custom routing, which
>>>> included considering some ways as barriers.  We created our own weighting
>>>> algorithm that pulled the way id from the edge, then looked up the needed
>>>> attributes from the way to determine whether the edge could be crossed or
>>>> not.
>>>>
>>>>  Which brings me to my suggestion.  I think the new version of
>>>> Graphhopper now natively allows the storage of way id's for each edge.
>>>>  Peter, correct me if I'm wrong.  So, Mark, you could create a table that
>>>> would be populated with way id's and a flag associated with each way that
>>>> would say it blocks or not.  Then your custom weighting algorithm can query
>>>> that table with the way id obtained from each edge passed in, then return
>>>> infinity (I think) if it should be a barrier.
>>>>
>>>>  If that is not granular enough (say, only part of a way should be
>>>> blocked) you may have to also store the blocking node location(s) for each
>>>> way that has blockage in your table, then do some geometry intersects to
>>>> see if the edge contains a blocking node.  This will not be as fast as the
>>>> "regular" routing solution, but if you maintain those dynamic blocking
>>>> ways/nodes in memory somewhere (say a hashmap?) then it should still retain
>>>> good speed.
>>>>
>>>>  I could be totally off on this of course.
>>>>
>>>>  Hope it helps.
>>>>
>>>> Daniel
>>>>
>>>>
>>>>
>>>> On Thu, Jul 3, 2014 at 9:44 AM, Markware Software Services <
>>>> markwaresoftware at gmail.com> wrote:
>>>>
>>>>> Hi Guys, to be a little more specific, (I cannot type much on my
>>>>> android), we imported the planet file into Postgres/PostGis using
>>>>> osm2pgsql. We then use Osmosis to get minutely diff updates from osm and
>>>>> apply to the database. So far, it has worked very well.
>>>>>
>>>>> Our intention is to use osmosis to extract from the planet database a
>>>>> subset for a particular disaster area, on a regular basis during a disaster
>>>>> (eg: haiyan in the philippies) We would like to create a routing graph
>>>>> based on user input gathered from mobile devices and satellite imagery via
>>>>> HOT OSM, eg: floods, downed power lines, collapsed bridges, etc and make
>>>>> that latest map available to the mobile devices along with a new routing
>>>>> graph
>>>>>
>>>>> The advantage of pg_routng is it is quite simple to increase the
>>>>> weight of a segment for routing. It is also easy to add a NEW node into the
>>>>> database weighted so that it makes that way impassable. NO need to deal
>>>>> with OSM XML Files.
>>>>>
>>>>> So far, I have been unable to find a way to make graphhopper do this,
>>>>> but the speed of graphhoper is so impressive we really want to use it on
>>>>> mobile devices and web based applications!.
>>>>>
>>>>> So my challenge is to somehow to dump an extract of the postgres
>>>>> database form Pg_routing into a graphopper file, without the use of an osm
>>>>> file and supply that updated graph to users in the field, or wherever. It
>>>>> will be of immense value to planners and decision makers in disasters, etc.
>>>>> I can see the update needing to be done several times per day, but creating
>>>>> a pbf or xml file and then processing it via graphhoper is not really an
>>>>> option, especially if the size of the area is significant.
>>>>>
>>>>> I am totally open to suggestions, discussion on this and I am sure
>>>>> that a number of other uses will manifest as a result of discussion and need
>>>>>
>>>>> In my simple mind, taking an extract of a pg_routng database and
>>>>> creating a graphhopper file is probably the simplest apprroach, but perhaps
>>>>> I am being too simplistic
>>>>>
>>>>> Cheers
>>>>>
>>>>> Mark
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Regards
>>>>>
>>>>> Mark Cupitt
>>>>>
>>>>> "If we change the world, let it bear the mark of our intelligence"
>>>>>
>>>>> See me on Open Street Map
>>>>> <https://www.openstreetmap.org/user/Mark_Cupitt>
>>>>>
>>>>> See me on LinkedIn <http://ph.linkedin.com/in/markcupitt>
>>>>>
>>>>>
>>>>>
>>>>> *See me on StackExchange
>>>>> <http://gis.stackexchange.com/users/17846/mark-c> *
>>>>>
>>>>> ===============================================================================================
>>>>> The contents of this email are intended only for the individual(s) to
>>>>> whom it is addressed and may contain
>>>>> confidential or privileged information. If you are not the intended
>>>>> recipient, you must not disclose, copy, distribute,
>>>>> or use the contents of this email. If you have received this email in
>>>>> error, please notify the sender immediately and
>>>>> delete the email and any attachments.
>>>>> ===============================================================================================
>>>>>
>>>>>
>>>>>
>>>>> On Thu, Jul 3, 2014 at 10:27 PM, Markware Software Services <
>>>>> markwaresoftware at gmail.com> wrote:
>>>>>
>>>>>> Vivek. We put it the osm data postgres db using osm2pgsql but use
>>>>>> osmosis for 5min diff updates
>>>>>> Cheers mark
>>>>>>
>>>>>> Sent from my android. Please excuse typos.
>>>>>> On Jul 3, 2014 9:45 PM, "Vivek Nallur" <vivek.nallur at scss.tcd.ie>
>>>>>> wrote:
>>>>>>
>>>>>>> On a related note (I know this isn't the right mailing list), but
>>>>>>> does
>>>>>>> anyone have any experience using Osmosis to update existing tags in
>>>>>>> OSM
>>>>>>> maps? I've been trying for a while now, but without success.
>>>>>>> regs
>>>>>>> Vivek
>>>>>>>
>>>>>>> On Thu, Jul 03, 2014 at 02:51:25PM +0100, Vivek Nallur wrote:
>>>>>>>
>>>>>>>> Hi guys,
>>>>>>>>
>>>>>>>> I have almost the exact requirements as Mark! However, what I'm
>>>>>>>> trying
>>>>>>>> to do is integrate sensor data (like pollution) onto the map, and
>>>>>>>> then
>>>>>>>> allow the user the ability to either take it into account or go
>>>>>>>> with the
>>>>>>>> default (car).
>>>>>>>>
>>>>>>>> The problem is that sensor data might update the map a few times a
>>>>>>>> day.
>>>>>>>>
>>>>>>>> My current idea is as follows (Peter, you may have read this
>>>>>>>> already!):
>>>>>>>>
>>>>>>>> 1) Grab the sensor data and push it into Redis (or any datastore. I
>>>>>>>> don't really care)
>>>>>>>> 2) Using a cron job, convert the sensor data into weights, and
>>>>>>>> create/update a tag inside the OSM file
>>>>>>>> 3) Re-start Graphhopper so that it can re-read the updated OSM file
>>>>>>>>
>>>>>>>> Mark, this might work for you, if you have a flooding sensor in
>>>>>>>> place
>>>>>>>> (or similar). Peter, is this a sane plan, in the first place?
>>>>>>>>
>>>>>>>> So, my big question is: would it be easy/feasible to create a
>>>>>>>> postgres/neo4j bridge,
>>>>>>>> that graphhopper can read from? It'll save me doing
>>>>>>>> cron....update.....restartGraphhopper process. Also, it might make
>>>>>>>> it
>>>>>>>> easier to combine preferences like 'cycling route' + 'least
>>>>>>>> polluted'
>>>>>>>>
>>>>>>>> regs
>>>>>>>> Vivek
>>>>>>>>
>>>>>>>>
>>>>>>>> On Thu, Jul 03, 2014 at 02:06:02PM +0200, Peter wrote:
>>>>>>>>
>>>>>>>>> Hi,
>>>>>>>>>
>>>>>>>>> There was work done where neo4j was used as storage and so you
>>>>>>>>> could do
>>>>>>>>> with pg routing (although I think it would be even less suited as
>>>>>>>>> pg is
>>>>>>>>> not a graph database). But you'll need solid Java skills:
>>>>>>>>> https://github.com/graphhopper/graphhopper-
>>>>>>>>> experiments/blob/master/src/main/java/com/graphhopper/
>>>>>>>>> compare/neo4j/Neo4JGraphImpl.java
>>>>>>>>>
>>>>>>>>> Besides this it is probably easier to change the edge costs
>>>>>>>>> directly in
>>>>>>>>> GraphHopper but I'm with you that a postgres or neo4j bridge would
>>>>>>>>> be a
>>>>>>>>> very interesting thing.
>>>>>>>>>
>>>>>>>>> Regards,
>>>>>>>>> Peter.
>>>>>>>>>
>>>>>>>>>  Hi All
>>>>>>>>>>
>>>>>>>>>> I have been looking at Graphhopper for our routing needs and also
>>>>>>>>>> looking at Pg_Routing and both packages are very impressive.
>>>>>>>>>>
>>>>>>>>>> In a Nutshell, if you want to compare the two, Graphhopper's best
>>>>>>>>>> feature is it speed, PG_Routing's best feature is flexibility
>>>>>>>>>> (speed
>>>>>>>>>> is not it .. that is for sure)
>>>>>>>>>>
>>>>>>>>>> It struck me last night that there may be a way to get the best
>>>>>>>>>> form
>>>>>>>>>> both environments. I have been looking at how I can use
>>>>>>>>>> Graphhopper in
>>>>>>>>>> a Dynamic and Changing environment for our Disaster Network as
>>>>>>>>>> well as
>>>>>>>>>> a few other possibilities, but I need the ability to be able to
>>>>>>>>>> quickly update road unavailability due to flooding, etc so that
>>>>>>>>>> routing will not be used on those areas.
>>>>>>>>>>
>>>>>>>>>> PG_Routing makes this quite easy by simply adding a high cost to
>>>>>>>>>> that
>>>>>>>>>> bridge or segment of road Whereas Graphhopper requires the
>>>>>>>>>> rebuilding
>>>>>>>>>> of the entire graph. (at the moment anyway)
>>>>>>>>>>
>>>>>>>>>> My thought was, why not use both!! Use PG_Routing to maintain the
>>>>>>>>>> graph design and costs but make a program that builds the
>>>>>>>>>> graphhopper
>>>>>>>>>> graph based on the pg_routing database and not the osm file ..
>>>>>>>>>>
>>>>>>>>>> My gut feel tells me that this might be quite feasible from a
>>>>>>>>>> timing
>>>>>>>>>> standpoint, but I am not sure if the structure of the routing
>>>>>>>>>> database
>>>>>>>>>> is suited to sequential scanning and building a graphhopper
>>>>>>>>>> graph. If
>>>>>>>>>> it was, this would be a relative painless process that could be
>>>>>>>>>> done
>>>>>>>>>> daily (or less) or on demand for disaster prone applications
>>>>>>>>>>
>>>>>>>>>> Unfortunately my Java and C skills are virtually non existent (I
>>>>>>>>>> am a
>>>>>>>>>> VB and Windows guy) and pulling the code apart to look at this is
>>>>>>>>>> going to be extremely difficult for me
>>>>>>>>>>
>>>>>>>>>> I would be interested in your thoughts and if you see any
>>>>>>>>>> immediate
>>>>>>>>>> ShowStoppers in this or any reason that it should not be done.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Regards
>>>>>>>>>>
>>>>>>>>>> Mark Cupitt
>>>>>>>>>>
>>>>>>>>>> "If we change the world, let it bear the mark of our intelligence"
>>>>>>>>>>
>>>>>>>>>> See me on Open Street Map <https://www.openstreetmap.
>>>>>>>>>> org/user/Mark_Cupitt>
>>>>>>>>>>
>>>>>>>>>> See me on LinkedIn <http://ph.linkedin.com/in/markcupitt>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> *See me on StackExchange <http://gis.stackexchange.com/
>>>>>>>>>> users/17846/mark-c>
>>>>>>>>>> *
>>>>>>>>>> ============================================================
>>>>>>>>>> ===================================
>>>>>>>>>> The contents of this email are intended only for the
>>>>>>>>>> individual(s) to
>>>>>>>>>> whom it is addressed and may contain
>>>>>>>>>> confidential or privileged information. If you are not the
>>>>>>>>>> intended
>>>>>>>>>> recipient, you must not disclose, copy, distribute,
>>>>>>>>>> or use the contents of this email. If you have received this
>>>>>>>>>> email in
>>>>>>>>>> error, please notify the sender immediately and
>>>>>>>>>> delete the email and any attachments.
>>>>>>>>>> ============================================================
>>>>>>>>>> ===================================
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> GraphHopper mailing list
>>>>>>>>>> GraphHopper at openstreetmap.org
>>>>>>>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>  _______________________________________________
>>>>>>>>> GraphHopper mailing list
>>>>>>>>> GraphHopper at openstreetmap.org
>>>>>>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> GraphHopper mailing list
>>>>>>>> GraphHopper at openstreetmap.org
>>>>>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>>>>>
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> GraphHopper mailing list
>>>>>>> GraphHopper at openstreetmap.org
>>>>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>>>>
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> GraphHopper mailing list
>>>>> GraphHopper at openstreetmap.org
>>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> GraphHopper mailing list
>>>> GraphHopper at openstreetmap.org
>>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>>
>>>>
>>>
>>> _______________________________________________
>>> GraphHopper mailing list
>>> GraphHopper at openstreetmap.org
>>> https://lists.openstreetmap.org/listinfo/graphhopper
>>>
>>>
>>
>> _______________________________________________
>> GraphHopper mailing list
>> GraphHopper at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/graphhopper
>>
>>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/graphhopper
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140705/d709a4b3/attachment.html>

More information about the GraphHopper mailing list