ContractionHierarchyBidirectionalDijkstra with pgrServer

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

ContractionHierarchyBidirectionalDijkstra with pgrServer

Mario Basa
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: ContractionHierarchyBidirectionalDijkstra with pgrServer

John Sichi
Administrator
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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: ContractionHierarchyBidirectionalDijkstra with pgrServer

d-michail
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: ContractionHierarchyBidirectionalDijkstra with pgrServer

Mario Basa
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: ContractionHierarchyBidirectionalDijkstra with pgrServer

d-michail
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: ContractionHierarchyBidirectionalDijkstra with pgrServer

Mario Basa
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users