search

LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
46 stars 5 forks source link

[BUG] Benchmarks run same test 12 times #28

Closed magnushiie closed 1 year ago

magnushiie commented 1 year ago

Describe the bug The benchmarks (like BenchmarkShortestPath) execute 12 iterations with k = 0..11, calculate an n = 2^k, but then don't use either of them in the benchmark except for the title.

To Reproduce Run the benchmarks and read source code.

Expected behavior Either n or k should be used in the benchmark core (not sure what these could be for BenchmarkShortestPath, for BenchmarkShortestPathOneToMany it could be the number of target nodes).

LdDl commented 1 year ago

Wow, we did miss that. Thank you Started #29

  1. For One-To-One bench we suggest generate graph vertices based on n=2^k - You can take a look already.

Other works in that PR would be:

  1. For One-To-Many it depends. May be 2 benchmarks: one is for different graph sizes; second - number of target nodes
  2. We need to re-evaluate BenchmarkShortestPathOneToMany and BenchmarkOldWayShortestPathOneToMany (we need to take a look at #27 also) since we've changed PC specs of developer machine
LdDl commented 1 year ago

Well, we've just updated PR. Summary:

  1. BenchmarkShortestPath - generates graph with n=2^k, computes its contraction hierarchies, takes two random vertices and computes shortest path between them.
  2. BenchmarkStaticCaseShortestPath - just single run on predefined graph (187k vertices) with computing of contraction hierarchies
  3. BenchmarkShortestPathOneToMany (and old derivative ...OldWay...) - generates graph with n=2^k, computes its contraction hierarchies, takes one random vertex as source and five random vertices as targets and computes shortest paths
  4. BenchmarkTargetNodesShortestPathOneToMany (and old derivative ...OldWay...) - takes predefined graph (187k vertices), computes its contraction hierarchies, takes predefined vertex as source, takes random number (1 up to 2^k) of random vertices, computes shortest paths
  5. BenchmarkStaticCaseShortestPathOneToMany (and old derivative ...OldWay...) - just single run (1 predefined source - 5 predefined targets) on predefined graph (187k vertices) with computing of contraction hierarchies

I believe bug has been fixed, but for sure now we can improve tests (e.g. better random graph generation)