Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

[Mario B. <mar...@gm...>]

Oh wow, it is fast!

Totally worth using even with the high startup cost. Again I used a very
dense road network to obtain the results below and the returned paths of
both chbDijkstra and Dijkstra are exactly the same:

1.2 km search : 0m0.039s (chbDijkstra) : 0m0.041s (Dijkstra)

 15 km search : 0m0.047s (chbDijkstra) : 0m0.211s (Dijkstra)

 52 km search : 0m0.052s (chbDijkstra) : 0m1.265s (Dijkstra)

109 km search : 0m0.077s (chbDijkstra) : 0m2.020s (Dijkstra)

175 km search : 0m0.083s (chbDijkstra) : 0m2.252s (Dijkstra)

229 km search : 0m0.099s (chbDijkstra) : 0m2.289s (Dijkstra)


Thanks.

On Thu, Oct 8, 2020 at 8:16 PM Dimitrios Michail <
dim...@gm...> wrote:

> 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
>>>>
>>>