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

Sat Jul 25 10:24:09 UTC 2015

Then probably I will be working on extending the functionality of the
QueryGraph to support this scenario. just seeking the easiest way :)

Regards,

On 24 July 2015 at 14:30, Peter <graphhopper at gmx.de> wrote:

>  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> 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> 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> 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,
>>>>
>>>>
> _______________________________________________
> 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/20150725/09c1ab58/attachment.html>