Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Dimitrios M. <dim...@gm...>]

Please share your findings. I am rather curious about the speedup. I have
seen some papers with these techniques
where each query was more than 2 (if not 3) orders of magnitude faster than
plain Dijkstra.

Best,
Dimitrios



On Wed, Oct 7, 2020 at 5:36 PM Mario Basa <mar...@gm...> wrote:

> But at 13 minutes loading time, the preprocessing is very expensive
> considering that the entire graph is created in just around 3 minutes. Will
> test and compare it though with basic Dijkstra to see if it is worth the
> cost.
>
> Thanks,
>
> Mario.
>
>
> On Wed, Oct 7, 2020 at 6:45 PM Dimitrios Michail <
> dim...@gm...> wrote:
>
>> Indeed John is right. This is a preprocessing technique which has the
>> drawback of consuming memory, but is very fast when querying.
>> Not sure whether the preprocessing is lazily triggered but you should
>> keep the same instance around, as long as the graph
>> does not change.
>>
>>
>>
>> On Wed, Oct 7, 2020 at 6:01 AM John Sichi <js...@gm...> wrote:
>>
>>> Does that include the time to precompute the contraction hierarchy?  My
>>> understanding is that building the hierarchy is a cost to be paid once up
>>> front, and then after that you can use it to answer queries over and over
>>> (as long as the graph doesn't change).
>>>
>>> On Sun, Oct 4, 2020 at 3:35 PM Mario Basa <mar...@gm...> wrote:
>>>
>>>> Hello, I'm new here.
>>>>
>>>> I just tried ContractionHierarchyBidirectionalDijkstra and it seems it
>>>> is more suited for sparse graphs. I got this result with a very dense
>>>> graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/chbDijkstra?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 13m58.587s
>>>>
>>>> user 0m0.117s
>>>>
>>>> sys 0m0.168s
>>>>
>>>>
>>>> while I got this result from Dijkstra with the same graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/dijkstra?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 0m0.091s
>>>>
>>>> user 0m0.010s
>>>>
>>>> sys 0m0.010s
>>>>
>>>> and this from A-Star again with the same graph:
>>>>
>>>> Marios-MacBook-Pro:~ mbasa$ time curl -X GET "
>>>> http://localhost:8080/pgrServer/api/node/astar?source=1015422&target=979173"
>>>> -H "accept: application/json" > response_1601788501820.json
>>>>
>>>>
>>>> real 0m0.058s
>>>>
>>>> user 0m0.010s
>>>>
>>>> sys 0m0.011s
>>>>
>>>> Regards,
>>>>
>>>> Mario.
>>>>
>>>> _______________________________________________
>>>> jgrapht-users mailing list
>>>> jgr...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>