[GraphHopper] Graphhopper and Pg_Routing Bridge

[Markware Software Services]

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140705/94e9f651/attachment.html>