path expansion endpoint #1849

kevinkreiser · 2019-06-14T18:32:09Z

this adds a new endpoint to valhalla called /expansion which takes a normal /route style request but returns geojson. the geojson is a time-series dataset of which edges of the routing graph were touched by the path algorithm (only bidirectional a* implemented so far) in the order they were touched and what type of label was assigned to them.

the geojson is a small as possible (for such a verbose format). it returns only a single feature which has a geometry of type MultiLineString. Each LineString represents the beginning and end points (so only two coordinates) of each edge the algorithm touched.

the properties of the feature contain two parallel arrays (which match the number of edges/linestrings in the geometry). the first array is a list of the edge_ids and the second array is a list of the statuses. the statuses can be one of r (reached), s (settled) or c (connected).

this should work for multileg routes as well but there is no signifier of when one legs expansion history ends and the next one begins.

there should be little to no performance impact on the /route endpoint as the function that tracks this data is both inlined and wrapped in an if that says don't track this if we werent called from the /expansion action/endpont.

…st yet.

src/thor/bidirectional_astar.cc

dnesbitt61

Any impact on performance when not tracking expansion?

kevinkreiser · 2019-06-14T18:36:47Z

src/thor/route_action.cc

+  rapidjson::Pointer("/features/0/geometry/type").Set(*expansion_, "MultiLineString");
+  rapidjson::Pointer("/features/0/geometry/coordinates").Create(*expansion_).SetArray();
+  rapidjson::Pointer("/features/0/properties/edge_ids").Create(*expansion_).SetArray();
+  rapidjson::Pointer("/features/0/properties/statuses").Create(*expansion_).SetArray();


here we fill out a template of the feature collection and the one feature that holds all the linestrings. if its a multileg route we have a problem where the last leg will win on setting which algorithm wsa used. seems like in the future we should ahve a separate feature for each leg

src/thor/route_action.cc

kevinkreiser · 2019-06-14T18:38:42Z

src/thor/route_action.cc

+  // serialize it
+  auto json = rapidjson::to_string(*expansion_, 5);
+  // tell the path algorithms to stop tracking the expansion at all
+  expansion_.reset();


so when we do this reset the algorithms will see that their weak_ptr doesnt point to anything and so wont track

kevinkreiser · 2019-06-14T18:41:00Z

valhalla/baldr/rapidjson_utils.h

  rapidjson::StringBuffer buffer;
  rapidjson::Writer<rapidjson::StringBuffer> writer(buffer);
+  if (decimal_places >= 0)
+    writer.SetMaxDecimalPlaces(decimal_places);


this makes it easy for us to truncate all precision to a certain value, which is nice for geojson where we can just say we only care about 5 places for example

valhalla/thor/pathalgorithm.h

kevinkreiser · 2019-06-14T18:44:27Z

@dnesbitt61 shouldnt be any performance impact, i was very careful about that. i can do performance testing on my own but would there but a specific test suite that you would recommend to verify that?

dnesbitt61 · 2019-06-14T18:56:14Z

I always check Lancaster to San Diego as my long test route, though any long route would work. valhalla_run_route with multi-run option works best (N successive path generation times are averaged to give the result - I usually use 100). I tried to keep a running tally of where this was, but now I have a new machine. I could try before and after with this branch but I have data without hierarchies and shortcuts.

dnesbitt61

Tested performance and looks fine (just a very small drop 1-2%). Code looks good to me, but didn't test the actual generation of GeoJSON. Will leave that to others!

…pansion

kevinkreiser · 2019-06-14T21:01:05Z

I noticed a little bit more of a performance penalty locally using std::weak_ptr so i changed the whole thing around and decided to pass an std::function into the path algorithm that allows you to track what the algorithm is doing from the outside. this is cool for few reasons.

its more general. we are using it to do make some geojson but you could do lots of other stuff with it
it keeps the logic out of the path algorithm an in the action/api layer
its faster. in my tests there was no difference with this code and master:

BEFORE:
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/master$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:49:13.476930 [INFO] PathAlgorithm GetBestPath average: 120 ms
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/master$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:49:27.358655 [INFO] PathAlgorithm GetBestPath average: 119 ms
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/master$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:49:41.409925 [INFO] PathAlgorithm GetBestPath average: 119 ms

AFTER:
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/build$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:48:29.718511 [INFO] PathAlgorithm GetBestPath average: 118 ms
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/build$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:48:43.827638 [INFO] PathAlgorithm GetBestPath average: 118 ms
kkreiser@kcarbon:~/sandbox/valhalla/valhalla/build$ ./valhalla_run_route --config ../valhalla.json --multi-run 100 -j '{"locations":[{"lat":32.697958,"lon":-117.174648,"street":"Park Boulevard"},{"lat":40.042553,"lon":-76.299115}],"costing":"auto"}' | grep -F average
2019/06/14 20:48:57.987518 [INFO] PathAlgorithm GetBestPath average: 120 ms

kevinkreiser · 2019-06-14T21:03:07Z

src/thor/bidirectional_astar.cc

@@ -181,6 +181,10 @@ void BidirectionalAStar::ExpandForward(GraphReader& graphreader,
                                     (pred.not_thru_pruning() || !directededge->not_thru()));
    adjacencylist_forward_->add(idx);
    *es = {EdgeSet::kTemporary, idx};
+
+    // setting this edge as reached
+    if (expansion_callback_)


std::function<> has an operator bool which lets you check if its actually assigned to something callable, this check is way faster than std::weak_ptr<>::lock

kevinkreiser · 2019-06-14T21:04:12Z

src/thor/bidirectional_astar.cc

@@ -754,7 +787,7 @@ std::vector<PathInfo> BidirectionalAStar::FormPath(GraphReader& graphreader) {
      cost += edgelabel.cost() - edgelabels_reverse_[predidx].cost();
    }
    cost += tc;
-    path.emplace_back(edgelabel.mode(), cost.secs, oppedge, 0, cost.cost);
+    path.emplace_back(edgelabel.mode(), cost.secs, edgelabel.opp_edgeid(), 0, cost.cost);


this was a simplification. notice above that we go fetch the opposing edge id the hard way. the edge labels for bidirectional already have the opposing edge id on them so i just used that instead. @dnesbitt61 there's not a gotcha here right?

kevinkreiser · 2019-06-14T21:04:38Z

src/thor/route_action.cc

+  rapidjson::Pointer("/features/0/geometry/type").Set(dom, "MultiLineString");
+  rapidjson::Pointer("/features/0/geometry/coordinates").Create(dom).SetArray();
+  rapidjson::Pointer("/features/0/properties/edge_ids").Create(dom).SetArray();
+  rapidjson::Pointer("/features/0/properties/statuses").Create(dom).SetArray();


so we start by prepopulating the feature

kevinkreiser · 2019-06-14T21:06:07Z

src/thor/route_action.cc

+        .Get(dom)
+        ->GetArray()
+        .PushBack(rapidjson::Value{}.SetString(status, a), a);
+  };


we inject this lambda into the path algorithm and it calls us back with it. here we are building geojson but we could do something else with this information if we wanted.

kevinkreiser · 2019-06-14T21:06:37Z

src/thor/route_action.cc

+           &bidir_astar,
+       }) {
+    alg->set_track_expansion(track_expansion);
+  }


this is where we tell all the algorithms to actually use our lambda to track stuff as the algorithm progresses

kevinkreiser · 2019-06-14T21:07:01Z

src/thor/route_action.cc

+           &astar,
+           &bidir_astar,
+       }) {
+    alg->set_track_expansion(nullptr);


this is where we tell all the algorithms that they no longer have a callback to call

kevinkreiser added 3 commits June 14, 2019 09:09

code to track the expansion in bidirectional A*. not adding others ju…

240b5ea

…st yet.

add expansion action for debugging path algorithms. only bda* for now

93eda97

minify the geojson as much as possible

f721d5d

kevinkreiser requested review from dnesbitt61 and danpaz June 14, 2019 18:32

kevinkreiser commented Jun 14, 2019

View reviewed changes

src/thor/bidirectional_astar.cc Outdated Show resolved Hide resolved

dnesbitt61 reviewed Jun 14, 2019

View reviewed changes

kevinkreiser commented Jun 14, 2019

View reviewed changes

src/thor/route_action.cc Outdated Show resolved Hide resolved

kevinkreiser commented Jun 14, 2019

View reviewed changes

update comments

bcc6c7d

kevinkreiser commented Jun 14, 2019

View reviewed changes

valhalla/thor/pathalgorithm.h Outdated Show resolved Hide resolved

Merge branch 'master' into kk_pathexpansion

14f2005

dnesbitt61 previously approved these changes Jun 14, 2019

View reviewed changes

kevinkreiser added 3 commits June 14, 2019 16:56

refactor how the tracking happens to be more general. header cleanup

6ecb68b

Merge remote-tracking branch 'origin' into kk_pathexpansion

83bcbb0

Merge remote-tracking branch 'origin/kk_pathexpansion' into kk_pathex…

68b0f22

…pansion

kevinkreiser dismissed dnesbitt61’s stale review via 68b0f22 June 14, 2019 20:57

kevinkreiser commented Jun 14, 2019

View reviewed changes

kevinkreiser merged commit 8db2ade into master Jun 17, 2019

kevinkreiser mentioned this pull request Jul 22, 2019

Use bike share station in Valhalla #1762

Open

kevinkreiser deleted the kk_pathexpansion branch September 10, 2019 13:25

kevinkreiser mentioned this pull request Oct 9, 2019

Street Network View with Valhalla #1963

Closed

danpaz mentioned this pull request Dec 1, 2020

Adds initial expansion demo valhalla/demos#233

Merged

kevinkreiser mentioned this pull request May 12, 2024

last backwards incompatible improvements to /expansion ;) #4601

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

path expansion endpoint #1849

path expansion endpoint #1849

kevinkreiser commented Jun 14, 2019

dnesbitt61 left a comment

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser commented Jun 14, 2019

dnesbitt61 commented Jun 14, 2019

dnesbitt61 left a comment

kevinkreiser commented Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

kevinkreiser Jun 14, 2019

path expansion endpoint #1849

path expansion endpoint #1849

Conversation

kevinkreiser commented Jun 14, 2019

dnesbitt61 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

kevinkreiser commented Jun 14, 2019

dnesbitt61 commented Jun 14, 2019

dnesbitt61 left a comment

Choose a reason for hiding this comment

kevinkreiser commented Jun 14, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment