Perform timing comparison between different kinds of heaps as well as with
equivalent igraph
routine distances
. To do this, a random
subgraph containing a defined number of vertices is first selected.
Alternatively, this random subgraph can be pregenerated with the
dodgr_sample
function and passed directly.
compare_heaps(graph, nverts = 100, replications = 2)
graph 


nverts  Number of vertices used to generate random subgraph. If a nonnumeric value is given, the whole graph will be used. 
replications  Number of replications to be used in comparison 
Result of rbenachmar::benchmark
comparison in
data.frame
form.
igraph caches intermediate results of graph processing, so the igraph comparisons will be faster on subsequent runs. To obtain fair comparisons, run only once or restart the current R session.
#>compare_heaps (graph, nverts = 100, replications = 1)#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#>#> test #> 12 d < igraph::distances(igr, v = from_id, to = to_id, mode = "out") #> 6 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "BHeap") #> 7 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "FHeap") #> 8 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "TriHeap") #> 10 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "Heap23") #> 9 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "TriHeapExt") #> 11 d < dodgr_dists(graph_contracted, from = from_id, to = to_id, heap = "set") #> 1 d < dodgr_dists(graph, from = from_id, to = to_id, heap = "BHeap") #> 2 d < dodgr_dists(graph, from = from_id, to = to_id, heap = "FHeap") #> 3 d < dodgr_dists(graph, from = from_id, to = to_id, heap = "TriHeap") #> 5 d < dodgr_dists(graph, from = from_id, to = to_id, heap = "Heap23") #> 4 d < dodgr_dists(graph, from = from_id, to = to_id, heap = "TriHeapExt") #> replications elapsed relative user.self sys.self user.child sys.child #> 12 10 0.011 1.000 0.012 0.000 0 0 #> 6 10 0.018 1.636 0.024 0.000 0 0 #> 7 10 0.019 1.727 0.024 0.000 0 0 #> 8 10 0.019 1.727 0.024 0.000 0 0 #> 10 10 0.019 1.727 0.024 0.000 0 0 #> 9 10 0.021 1.909 0.020 0.000 0 0 #> 11 10 0.023 2.091 0.032 0.000 0 0 #> 1 10 0.025 2.273 0.028 0.004 0 0 #> 2 10 0.027 2.455 0.036 0.000 0 0 #> 3 10 0.027 2.455 0.036 0.000 0 0 #> 5 10 0.028 2.545 0.036 0.000 0 0 #> 4 10 0.031 2.818 0.032 0.000 0 0