[GraphHopper] can I add nodes and edges to the graph on the fly?

[Peter]

Hi Wesam,

To inject car points additional to the user query you'll need a custom
getPaths method in GraphHopper (via subclassing). E.g. see here how
custom weighting is done, similarly I would propose to try with customer
QueryGraph:
https://github.com/graphhopper/graphhopper/blob/master/docs/core/weighting.md

If something is missing for this to work in the GraphHopper class please
let us know.


> Problems with this approach: 
> 1) everything is done at query time (number of vehicles GHPoints is usually large)

in which range is it? 1K, 10K 100K?
Still I would try with the QueryGraph first and only if speed is
degraded try a more complex solution.


> 2) Cannot differentiate between vehicles’ nodes and the nodes representing the user given GHPoints in
the QueryGraph.

Either handle that in your custom GraphHopper class or see my proposed
methods in QueryGraph for the mapping.


> 3) The vehicles QueryResults will be considered as intermediate nodes for the routing algorithm. 

Yes, you need a custom setup but query only the points you need not with
all:
qGraph = new QueryGraph(graph);
qGraph.lookup(allCarAndUserPoints);

loop over user points only {
   path = createAlgo(qGraph, ..).createPath(userPoint1,userPoint2)
}

Kind Regards,
Peter

On 28.07.2015 09:53, wesam Herbawi wrote:
>
> The short answer is that you need to avoid the higher level API getPaths: 
> https://github.com/graphhopper/graphhopper/blob/master/docs/core/low-level-api.md 
>
> and instead create your storage and algorithms on your own. 
>
> OR subclass the GraphHopper class to know which are car points and
> which ones are user defined query points. 
>
> Also to better identify locations in QueryGraph we could introduce a
> mapping to find out the virtual nodes e.g. via 
> int /*virtualNode*/ QueryGraph.getNodeId(int lookupIndex) 
> int /*lookupIndex*/ QueryGraph.getLookupIndex(int virtualNode)
>
> Kind Regards, 
> Peter 
>
> Am 27.7.15 12:54 schrieb Wesam Herbawi: 
> -------------------- 
> Hi peter 
> Very sorry for this prolonged email. It is just the brainstorming
> phase where I am trying to figure out how can the easiest way for the
> implementation look like. 
>
> Here is a summary of my understanding of the existing code and the way
> that I might follow for the implementation of my use case. I have also
> highlited some problems that one might face. Your opinion is highly
> appreciated. 
>
> in method protected List<Path> getPaths( GHRequest request, GHResponse
> rsp ) 
> The request contains, among other things, a list of GHPoints
> representing the sources and destinations coordinates as given by the
> end user. For each of these GHPoints, a QueryResult object is obtained
> representing the snapping of the given GHPoints to the base graph
> nodes (base graph is the original street graph). This results in a
> list of QueryResult objects. Using the base graph and the list of
> QueryResult objects, a QueryGraph is created by adding virtual nodes
> and edges to the base graph. The routing algorithm is then fed with
> the QueryGraph to find the shortest path for each two consecutive
> points in the list of QueryResult objects (when the number of
> QueryResult objects>2 then this probably represents way nodes). 
>
> The implementation that came to my mind is just to handle the
> carsharing vehicles as list of GHPoints (exactly as the coordinates
> given by the end user when asking for a shortest path). Then use these
> carsharing vehicles GHPoints + the user given GHPoints for source and
> destination to create the QueryGraph 
> QueryGraph queryGraph = new QueryGraph(routingGraph); 
> queryGraph.lookup(qResults); 
>
> where qResults contains both the vehicles QueryResults + the user
> given GHPoints QueryResults. 
>
> Problems with this approach: 
> 1) everything is done at query time (number of vehicles GHPoints is
> usually large) 
> 2) Cannot differentiate between vehicles’ nodes and the nodes
> representing the user given GHPoints in the QueryGraph. 
> 3) The vehicles QueryResults will be considered as intermediate nodes
> for the routing algorithm. 
>
> To avoid problem number 3, I can maintain two QueryResult lists one
> for the vehicles QueryResults and one for those representing the user
> given GHPoints. However this requires playing in class
> GraphHopper.java which is a central one. Still I cannot tell which
> node in the QueryGraph is a vehicle node and which one is a node
> representing the user given coordinates. 
>
> Any hints, suggestions? 
>
>
>
> _______________________________________________
> 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/20150729/9384f058/attachment.html>