Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] ContractionHierarchyBidirectionalDijkstra with pgrServer
|
From: Dimitrios M. <dim...@gm...> - 2020-10-07 09:45:52
|
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 > |
