Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer

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

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