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

[Peter]

Hi Wesam,

> do you think that the QueryGraph approach will work for multiple
vehicles distributed on the graph?

It could be that the QueryGraph is not the most performant solution, but
if you only have a few hundreds or even thousands, it might work. I have
tested it up to 10K without having problems but it could be that there
are problems for more locations.

Also the QueryGraph is intended to be as much lightweight as possible so
'frequent throw aways' should be fine.

> will try to find the closest street node to the vehicle and mark it
(in a seperate hashtable)
> to be a vehicle representative node and will be handled differently in
the routing algorithm

For that just use QueryResult.getClosestNode obtained from the location
index.


> The disadvantage here is clearly that the street node might be far
away from the vehicle position.

Yes, you'll need to calculate the splitted weight, geometry etc ...
which is done in QueryGraph already

> Later on I might think of splitting the street edge. I thought this
might be easier to start with. what do you think?

Yes, this is exactly what we are doing in QueryGraph and it is not easy :)
Assume you have multiple vehicles on the same edge ... this should be
all supported from QueryGraph already. Probably the first trial could be
indeed with QueryGraph and switch to something else if this won't work
or is too slow.

Would be interesting to make the QueryGraph useful for this kind of use
case too.

Regards,
Peter

On 24.07.2015 11:17, wesam Herbawi wrote:
> Many thanks Peter,
> do you think that the QueryGraph approach will work for multiple
> vehicles distributed on the graph? I am thinking of updating the
> QueryGraph on regular basis, e.g. every 10 minutes, not per query.
>
>
> Away from the QueryGraph approach, as a start, I will try to find the
> closest street node to the vehicle and mark it (in a seperate
> hashtable) to be a vehicle representative node and will be handled
> differently in the routing algorithm. The disadvantage here is clearly
> that the street node might be far away from the vehicle position.
> Later on I might think of splitting the street edge. I thought this
> might be easier to start with. what do you think? 
>
>
>
> On 23 July 2015 at 20:38, Peter <graphhopper at gmx.de
> <mailto:graphhopper at gmx.de>> wrote:
>
>     Hi anonymous,
>
>
>     > So during the time of creating the street graph, the vehicles'
>     nodes will be
>     > considered and have their own indecies in the original nodes array.
>
>     Yes, that was what I meant.
>
>     But now I know better what you mean with this kind of car sharing.
>     Then it is indeed a bit different and I would assign the position
>     to the two nodes of the edge, but associated with a different
>     weight in the algorithm reflecting the precise position and
>     skipping node(s) in case of one ways.
>
>     The problematic is indeed very similar to the "QueryGraph vs.
>     precise GPS routing" discussion:
>     https://github.com/graphhopper/graphhopper/issues/27
>     https://github.com/graphhopper/graphhopper/pull/115
>
>
>     > sorry for the long discussion. just trying to understand the alternatives before going further.
>
>     No problem. Interesting use case.
>
>     Regards,
>     Peter
>
>
>     On 23.07.2015 18:52, graphhopper newbie wrote:
>>     If I correctly understand you, this would solve the problem of
>>     adding vehicle representative nodes. So during the time of
>>     creating the street graph, the vehicles' nodes will be considered
>>     and have their own indecies in the original nodes array. However,
>>     what I miss is how to maintain the dynamic edges. when a vehicle
>>     is parked somewhere, an edge has to be added to connect it to the
>>     closest street node and the previous connecting edges have to be
>>     removed.
>>
>>
>>     Another interpretation that might be what you mean is that not to
>>     add vehicle nodes at all and consider the closest original street
>>     node to the vehicle to be the vehicle representative node and to
>>     add it to the data structure you mentioned earlier. if this is
>>     the case then I would miss some information I was planning to
>>     model using the edge connecting the street node and the vehicle
>>     node (still can be done implicitly) 
>>
>>     sorry for the long discussion. just trying to understand the
>>     alternatives before going further.
>>
>>     Regards
>>
>>     On 23 July 2015 at 16:58, Peter <graphhopper at gmx.de
>>     <mailto:graphhopper at gmx.de>> wrote:
>>
>>         I would just mark (in a different data structure) that these
>>         nodes are special e.g. in an array or (RAM)DataAccess which
>>         is more complex but also storable and scales to GB.
>>
>>         This way you don't need to remove/re-add them and instead can
>>         just remove the marker from the array. A lot easier IMO.
>>
>>         Regards,
>>         Peter
>>
>>         On 23.07.2015 16:17, graphhopper newbie wrote:
>>>         Thanks for the reply,
>>>         The use case makes the situation dynamic. Assume that you
>>>         have free floating carsharing vehicles. Let us assume that
>>>         these vehicles can be parked everywehere. what I wanted to
>>>         do is to periodically link these vehicles to the closest
>>>         nodes in the original street graph (remove old links when
>>>         vehicles change their positions). This way the vehicles will
>>>         be represented as nodes in the graph and routing will be
>>>         easier later. My routing algorithm has to be able to switch
>>>         from walk to drive mode when such vehicle node is found. the
>>>         goal is to have walk-drive-walk route in one Dijkstra run.
>>>
>>>         Regards,
>>>
>>>         On 23 July 2015 at 15:47, Peter <graphhopper at gmx.de
>>>         <mailto:graphhopper at gmx.de>> wrote:
>>>
>>>             Hi,
>>>
>>>             you can, but there is currently no way to remove such
>>>             edges (efficiently).
>>>
>>>             Another workaround would be to use the QueryGraph for
>>>             this like we use to introduce virtual nodes and edges to
>>>             incorporate the start+end GPS point into the graph. But
>>>             never tried this.
>>>
>>>             Why not always add all such points to the graph, why is
>>>             a dynamic scenario needed here?
>>>
>>>             Kind Regards,
>>>             Peter
>>>
>>>
>>>             On 23.07.2015 15:42, graphhopper newbie wrote:
>>>>             Hi everybody,
>>>>             I am wondering if I can add nodes and edges to the
>>>>             graph after its creation in a dynamic way. I need this
>>>>             functionality to deal with dynamic scenarios like
>>>>             representing available bikesharing/carsharing points
>>>>             which changes often. The simpist case I need is to add
>>>>             an edge from a newly added node ( representing the
>>>>             available bike) to the closest node in the graph and
>>>>             the reverse edge. i.e. from the closest node to the the
>>>>             bike node. 
>>>>
>>>>             Thank you very much,
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20150724/d96f16e1/attachment.html>