Merge branch 'master' into access_psv

valhalla · May 26, 2021 · 7f7c1af · 7f7c1af
2 parents 990b0ca + 58e4424
commit 7f7c1af
Show file tree

Hide file tree

Showing 5 changed files with 108 additions and 10 deletions.
diff --git a/.circleci/config.yml b/.circleci/config.yml
@@ -157,7 +157,10 @@ workflows:
   version: 2
   build_test_publish:
     jobs:
-      - build-docker-images
+      - build-docker-images:
+          filters:
+            tags:
+              only: /.*/
       - lint-build-debug:
           filters:
             tags:

diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -1,4 +1,9 @@
-## Release Date: 2021-??-?? Valhalla 3.1.2
+## Release Date: 2021-??-?? Valhalla 3.1.3
+* **Removed**
+* **Bug Fix**
+* **Enhancement**
+
+## Release Date: 2021-05-26 Valhalla 3.1.2
 * **Removed**
 * **Bug Fix**
    * FIXED: Change unnamed road intersections from being treated as penil point u-turns [#3084](https://github.com/valhalla/valhalla/pull/3084)
@@ -10,6 +15,7 @@
    * FIXED: Continuous lane guidance fix [#3054](https://github.com/valhalla/valhalla/pull/3054)
    * FIXED: Fix reclassification for "shorter" ferries and rail ferries (for Chunnel routing issues) [#3038](https://github.com/valhalla/valhalla/pull/3038)
    * FIXED: Incorrect routing through motor_vehicle:conditional=destination. [#3041](https://github.com/valhalla/valhalla/pull/3041)
+   * FIXED: Allow destination-only routing on the first-pass for non bidirectional A* algorithms. [#3085](https://github.com/valhalla/valhalla/pull/3085)
    * FIXED: Highway/ramp lane bifurcation [#3088](https://github.com/valhalla/valhalla/pull/3088)
    * FIXED: out of bound access of tile hierarchy in base_ll function in graphheader [#3089](https://github.com/valhalla/valhalla/pull/3089)
    * FIXED: include shortcuts in avoid edge set for avoid_polygons [#3090](https://github.com/valhalla/valhalla/pull/3090)

diff --git a/src/thor/route_action.cc b/src/thor/route_action.cc
@@ -347,8 +347,10 @@ thor::PathAlgorithm* thor_worker_t::get_path_algorithm(const std::string& routet
   // find the proper connection).
   for (auto& edge1 : origin.path_edges()) {
     for (auto& edge2 : destination.path_edges()) {
-      if (edge1.graph_id() == edge2.graph_id() ||
-          reader->AreEdgesConnected(GraphId(edge1.graph_id()), GraphId(edge2.graph_id()))) {
+      bool same_graph_id = edge1.graph_id() == edge2.graph_id();
+      bool are_connected =
+          reader->AreEdgesConnected(GraphId(edge1.graph_id()), GraphId(edge2.graph_id()));
+      if (same_graph_id || are_connected) {
         return &timedep_forward;
       }
     }
@@ -363,12 +365,14 @@ std::vector<std::vector<thor::PathInfo>> thor_worker_t::get_path(PathAlgorithm*
                                                                  valhalla::Location& destination,
                                                                  const std::string& costing,
                                                                  const Options& options) {
-  // Find the path. If bidirectional A* disable use of destination only edges on the
-  // first pass. If there is a failure, we allow them on the second pass.
+  // Find the path.
   valhalla::sif::cost_ptr_t cost = mode_costing[static_cast<uint32_t>(mode)];
-  if (path_algorithm == &bidir_astar) {
-    cost->set_allow_destination_only(false);
-  }
+
+  // If bidirectional A* disable use of destination-only edges on the
+  // first pass. If there is a failure, we allow them on the second pass.
+  // Other path algorithms can use destination-only edges on the first pass.
+  cost->set_allow_destination_only(path_algorithm == &bidir_astar ? false : true);
+
   cost->set_pass(0);
   auto paths = path_algorithm->GetBestPath(origin, destination, *reader, mode_costing, mode, options);
 

diff --git a/test/gurka/test_route.cc b/test/gurka/test_route.cc
@@ -821,3 +821,88 @@ TEST(MultipointRoute, WithPointsOnDeadends) {
     gurka::assert::raw::expect_path(result, {"AB", "BC", "BC"});
   }
 }
+
+// prove that non-bidir A* algorithms allow destination-only routing in their first pass
+TEST(AlgorithmTestDest, TestAlgoSwapAndDestOnly) {
+  constexpr double gridsize = 100;
+
+  const std::string ascii_map = R"(
+      B---------------C
+      |               |
+      |               8
+      |               ↑
+      |               |
+      Y---------------Z
+      |               |
+      7               9
+      |               |
+      A---------------D
+           )";
+  const auto layout = gurka::detail::map_to_coordinates(ascii_map, gridsize);
+  const gurka::ways ways = {{"AB", {{"highway", "motorway"}}},
+                            {"BC", {{"highway", "primary"}}},
+                            {"CZ",
+                             {{"highway", "primary"}, {"oneway", "-1"}, {"access", "destination"}}},
+                            {"ZD", {{"highway", "primary"}, {"access", "destination"}}},
+                            {"DA", {{"highway", "primary"}}},
+                            {"AY", {{"highway", "primary"}}},
+                            {"YZ", {{"highway", "primary"}}}};
+  gurka::map map = gurka::buildtiles(layout, ways, {}, {}, "test/data/search_filter");
+
+  // Notes on this test:
+  // * We want the first leg to choose bidir A*:
+  // == The path from 7 to 8 cannot be directly/trivially connected, hence YZ exists. This ensures
+  //    the first leg of the route chooses bidir A*.
+  // * We want the second leg to choose unidir A*:
+  // == The path between 8 & 9 needs to be directly/trivially connected so unidir A* is chosen for
+  //    second leg.
+  // == However, to ensure the 8->9 route cannot be solved without destination_only=true, we have
+  //    "oneway" attribution on ZC. This forces a trip "around the block" for the second leg.
+  // == ZD & CZ need access=destination or second leg will use bidir A*.
+  // == Also, CZ needs access access=destination so we prove that unidir A* solves the route
+  //    from 8->9 in its first pass (we are trying to prove that non-bidir A* algorithms allow
+  //    destination-only routing in their first pass).
+  //
+  // * Below, see that a heading is specified. This ensures filtered-edges are added to the final
+  //   destination node (9). Another important part of the test, see more comments below.
+  auto from = "7";
+  auto mid = "8";
+  auto to = "9";
+  const std::string& request =
+      (boost::format(
+           R"({"locations":[{"lat":%s,"lon":%s},{"lat":%s,"lon":%s},{"lat":%s,"lon":%s,"heading":180,"heading_tolerance":45}],"costing":"auto"})") %
+       std::to_string(map.nodes.at(from).lat()) % std::to_string(map.nodes.at(from).lng()) %
+       std::to_string(map.nodes.at(mid).lat()) % std::to_string(map.nodes.at(mid).lng()) %
+       std::to_string(map.nodes.at(to).lat()) % std::to_string(map.nodes.at(to).lng()))
+          .str();
+
+  auto api = gurka::do_action(valhalla::Options::route, map, request);
+
+  ASSERT_EQ(api.trip().routes(0).legs_size(), 2);
+
+  EXPECT_EQ(api.trip().routes(0).legs(0).algorithms(0), "bidirectional_a*");
+  EXPECT_EQ(api.trip().routes(0).legs(1).algorithms(0), "time_dependent_forward_a*");
+
+  EXPECT_EQ(api.trip().routes(0).legs(0).node(0).edge().destination_only(), false);
+  EXPECT_EQ(api.trip().routes(0).legs(1).node(0).edge().destination_only(), true);
+
+  // These "expected_path_edge_sizes" are from the perspective of each node (7, 8, 9).
+  // Without the fix, the path-edge sizes are {2, 1, 2}. The third int is 2 because unidir A*
+  // would previously enter fallback logic to solve the second leg (8->9) and consequently
+  // add a "filtered edge". We prove we aren't entering fallback logic by asserting that the
+  // third int is 1.
+  //
+  // Honestly, this is a slightly convoluted way to test that "non-bidir A* algorithms allow
+  // destination only routing on their first-pass". This relies on some internal counts that
+  // imply some knowledge about the inner workings of Valhalla. Valhalla could evolve for
+  // the better, these numbers could change and this test could fail. But that doesn't mean
+  // your code is bad. Just consider this test's intent and whether what its testing still makes
+  // sense relative to your changes.
+  std::vector<int> expected_path_edge_sizes = {2, 1, 1};
+  std::vector<int> actual_path_edge_sizes;
+  actual_path_edge_sizes.reserve(api.options().locations_size());
+  for (int i = 0; i < api.options().locations_size(); i++) {
+    actual_path_edge_sizes.emplace_back(api.options().locations(i).path_edges().size());
+  }
+  ASSERT_EQ(expected_path_edge_sizes, actual_path_edge_sizes);
+}
diff --git a/valhalla/valhalla.h.in b/valhalla/valhalla.h.in
@@ -2,5 +2,5 @@
 
 #define VALHALLA_VERSION_MAJOR 3
 #define VALHALLA_VERSION_MINOR 1
-#define VALHALLA_VERSION_PATCH 1
+#define VALHALLA_VERSION_PATCH 2