OmniSciDB  b28c0d5765
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GraphTableFunctions.hpp
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc., Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #ifndef __CUDACC__
20 #ifdef HAVE_TBB
21 
22 #include <tbb/parallel_for.h>
23 
24 #include <boost/config.hpp>
25 #include <boost/graph/adjacency_list.hpp>
26 #include <boost/graph/dijkstra_shortest_paths.hpp>
27 #include <boost/graph/graph_traits.hpp>
28 #include <boost/property_map/property_map.hpp>
29 
30 #include "ThirdParty/robin_hood/robin_hood.h"
31 
33 
34 template <class T>
35 struct get_mapped;
36 
37 template <>
38 struct get_mapped<int32_t> {
39  typedef int32_t type;
40 };
41 
42 template <>
43 struct get_mapped<int64_t> {
44  typedef int64_t type;
45 };
46 
47 template <>
48 struct get_mapped<TextEncodingDict> {
49  typedef int32_t type;
50 };
51 
52 template <typename T>
53 struct AttrIdxMap {
54  typedef typename get_mapped<T>::type T2;
55  bool must_be_unique;
56  std::vector<T2> idx_to_attr_map;
57  using AttrMap = robin_hood::unordered_flat_map<T2, int32_t>;
58  // std::map<T, int32_t> attr_to_idx_map;
59  AttrMap attr_to_idx_map;
60  int32_t unique_idx = 0;
61 
62  inline int32_t size() const { return static_cast<int64_t>(idx_to_attr_map.size()); }
63 
64  inline int32_t get_idx_for_key(const T2& key) const {
65  // Note this is not safe if key doesn't exist
66  return attr_to_idx_map.at(key);
67  }
68 
69  inline int64_t get_idx_for_key_safe(const T2& key) const {
70  // Note this is not safe if key doesn't exist
71  const auto key_itr = attr_to_idx_map.find(key);
72  if (key_itr == attr_to_idx_map.end()) {
73  return -1; // Invalid sentinel
74  }
75  return key_itr->second;
76  }
77 
78  inline T get_key_for_idx(const int32_t idx) const {
79  // Note this is not safe if key doesn't exist
80  return idx_to_attr_map[idx];
81  }
82 
83  AttrIdxMap(const bool must_be_unique) : must_be_unique(must_be_unique) {}
84 
85  void add_column(const Column<T>& col) {
86  auto timer = DEBUG_TIMER(__func__);
87  const int64_t num_rows = col.size();
88  if (idx_to_attr_map.empty()) {
89  // Only reserve space for the first batch, with the logic being
90  // that most of the unique values will be seen in the first
91  // column, excepting extreme edge cases
92  idx_to_attr_map.reserve(num_rows);
93  attr_to_idx_map.reserve(num_rows);
94  }
95  for (int64_t row_idx = 0; row_idx < num_rows; ++row_idx) {
96  if (!col.isNull(row_idx)) {
97  const bool is_new_elem = attr_to_idx_map.emplace(col[row_idx], unique_idx).second;
98  if (is_new_elem) {
99  idx_to_attr_map.emplace_back(col[row_idx]);
100  unique_idx++;
101  } else {
102  if (must_be_unique) {
103  throw std::runtime_error(
104  "Expected unique elements but found duplicates for column.");
105  }
106  }
107  }
108  }
109  CHECK_EQ(attr_to_idx_map.size(), idx_to_attr_map.size());
110  CHECK_EQ(idx_to_attr_map.size(), static_cast<size_t>(unique_idx));
111  }
112 };
113 
114 template <typename N>
115 std::vector<std::pair<N, N>> construct_key_normalized_edge_list(
116  const Column<N>& node1,
117  const Column<N>& node2,
118  const AttrIdxMap<N>& attr_idx_map) {
119  auto timer = DEBUG_TIMER(__func__);
120  const int32_t num_edges = node1.size();
121  std::vector<std::pair<N, N>> key_normalized_edge_list(num_edges);
123  tbb::blocked_range<int32_t>(0, num_edges),
124  [&](const tbb::blocked_range<int32_t>& r) {
125  const int32_t r_end = r.end();
126  for (int32_t e = r.begin(); e < r_end; ++e) {
127  key_normalized_edge_list[e].first = attr_idx_map.get_idx_for_key(node1[e]);
128  key_normalized_edge_list[e].second = attr_idx_map.get_idx_for_key(node2[e]);
129  }
130  });
131  return key_normalized_edge_list;
132 }
133 
134 template <typename S>
135 struct TerminalNodes {
136  S start_node;
137  S end_node;
138  bool end_node_is_valid;
139 
140  // In the first constructor we set end_node to start_node to squash a
141  // maybe_uninitialized warning (harmless as we have the end_node_is_valid sentinel)
142  TerminalNodes(const S start_node)
143  : start_node(start_node), end_node(start_node), end_node_is_valid(false) {}
144  TerminalNodes(const S start_node, const S end_node)
145  : start_node(start_node), end_node(end_node), end_node_is_valid(true) {}
146 };
147 
148 template <typename N, typename D>
149 struct GraphTraversalResults {
150  typedef boost::adjacency_list<boost::listS,
151  boost::vecS,
152  boost::directedS,
153  boost::no_property,
154  boost::property<boost::edge_weight_t, int32_t>>
155  graph_t;
156  typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
157  AttrIdxMap<N> attr_idx_map;
158  int32_t start_node_idx, end_node_idx;
159  graph_t edge_graph;
160  std::vector<vertex_descriptor> parents;
161  std::vector<D> graph_distances;
162  int64_t num_vertices{0};
163  boost::graph_traits<graph_t>::vertex_iterator vi, vend;
164 
165  GraphTraversalResults() : attr_idx_map(false) {}
166 
167  void buildEdgeGraph(const std::vector<std::pair<N, N>>& edge_list,
168  const Column<D>& distance) {
169  auto timer = DEBUG_TIMER(__func__);
170  edge_graph = graph_t(edge_list.data(),
171  edge_list.data() + edge_list.size(),
172  distance.ptr_,
173  attr_idx_map.size());
174  num_vertices = boost::num_vertices(edge_graph);
175  parents.resize(num_vertices);
176  graph_distances.resize(num_vertices);
177  boost::tie(vi, vend) = boost::vertices(edge_graph);
178  }
179 };
180 
181 template <typename N, typename D, typename S>
182 GraphTraversalResults<N, D> graph_shortest_path_impl(
183  const Column<N>& node1,
184  const Column<N>& node2,
185  const Column<D>& distance,
186  const TerminalNodes<S>& terminal_nodes) {
187  auto func_timer = DEBUG_TIMER(__func__);
188  typedef boost::adjacency_list<boost::listS,
189  boost::vecS,
190  boost::directedS,
191  boost::no_property,
192  boost::property<boost::edge_weight_t, int32_t>>
193  graph_t;
194  typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
195  typedef std::pair<int32_t, int32_t> Edge;
196  const int64_t num_edges = node1.size();
197  auto new_node2 = Column<N>(node2);
198  std::vector<N> translated_node2_data;
199  N start_node_translated;
200  N end_node_translated;
201  if constexpr (std::is_same_v<N, TextEncodingDict>) {
202  const auto node1_sdp = node1.string_dict_proxy_;
203  const auto node2_sdp = node2.string_dict_proxy_;
204  if (node1_sdp->getDictId() != node2_sdp->getDictId()) {
205  auto translation_timer = DEBUG_TIMER("Dictionary Translation");
206  const auto translation_map =
207  node2_sdp->buildUnionTranslationMapToOtherProxy(node1_sdp, {});
208  translated_node2_data.resize(num_edges);
209  for (int64_t edge_idx = 0; edge_idx < num_edges; ++edge_idx) {
210  const N original_val = node2[edge_idx];
211  translated_node2_data[edge_idx] =
212  original_val == inline_null_value<N>()
213  ? original_val
214  : static_cast<N>(translation_map[original_val]);
215  }
216  new_node2 = Column<N>(
217  translated_node2_data.data(), node2.num_rows_, node1.string_dict_proxy_);
218  }
219  if constexpr (!std::is_same_v<S, TextEncodingNone>) {
220  throw std::runtime_error(
221  "Starting node should be of text type to match graph nodes.");
222  } else {
223  start_node_translated =
224  node1.string_dict_proxy_->getIdOfString(terminal_nodes.start_node);
225  if (terminal_nodes.end_node_is_valid) {
226  end_node_translated =
227  node1.string_dict_proxy_->getIdOfString(terminal_nodes.end_node);
228  }
229  }
230  if (start_node_translated == StringDictionary::INVALID_STR_ID) {
231  throw std::runtime_error("Starting node not found.");
232  }
233  } else {
234  if constexpr (std::is_same_v<S, TextEncodingNone>) {
235  throw std::runtime_error(
236  "Starting node should be of integer type to match graph nodes.");
237  } else {
238  start_node_translated = terminal_nodes.start_node;
239  end_node_translated = terminal_nodes.end_node;
240  }
241  }
242 
243  GraphTraversalResults<N, D> graph_traversal_results;
244  graph_traversal_results.attr_idx_map.add_column(node1);
245  graph_traversal_results.attr_idx_map.add_column(new_node2);
246 
247  const auto edge_list = construct_key_normalized_edge_list(
248  node1, new_node2, graph_traversal_results.attr_idx_map);
249  graph_traversal_results.buildEdgeGraph(edge_list, distance);
250  graph_traversal_results.start_node_idx =
251  graph_traversal_results.attr_idx_map.get_idx_for_key_safe(start_node_translated);
252  graph_traversal_results.end_node_idx =
253  terminal_nodes.end_node_is_valid
254  ? graph_traversal_results.attr_idx_map.get_idx_for_key_safe(end_node_translated)
255  : -1;
256 
257  if (graph_traversal_results.start_node_idx < 0) {
258  throw std::runtime_error("Starting node not found.");
259  }
260  if (terminal_nodes.end_node_is_valid && graph_traversal_results.end_node_idx < 0) {
261  throw std::runtime_error("End node not found.");
262  }
263  vertex_descriptor start_vertex = boost::vertex(graph_traversal_results.start_node_idx,
264  graph_traversal_results.edge_graph);
265  {
266  auto shortest_paths_timer = DEBUG_TIMER("Djikstra Shortest Paths");
267  boost::dijkstra_shortest_paths(
268  graph_traversal_results.edge_graph,
269  start_vertex,
270  boost::predecessor_map(
271  boost::make_iterator_property_map(
272  graph_traversal_results.parents.begin(),
273  boost::get(boost::vertex_index, graph_traversal_results.edge_graph)))
274  .distance_map(boost::make_iterator_property_map(
275  graph_traversal_results.graph_distances.begin(),
276  boost::get(boost::vertex_index, graph_traversal_results.edge_graph))));
277  }
278  return graph_traversal_results;
279 }
280 
281 // clang-format off
282 /*
283  UDTF: tf_graph_shortest_path__cpu_template(TableFunctionManager,
284  Cursor<Column<N> node1, Column<N> node2, Column<D> distance> edge_list,
285  S origin_node, S destination_node) ->
286  Column<int32_t> path_step, Column<N> node | input_id=args<0>, Column<D> cume_distance,
287  N=[int32_t, int64_t, TextEncodingDict], D=[int32_t, int64_t, float, double],
288  S=[int64_t, TextEncodingNone]
289 */
290 // clang-format on
291 
292 template <typename N, typename D, typename S>
293 int64_t tf_graph_shortest_path__cpu_template(TableFunctionManager& mgr,
294  const Column<N>& node1,
295  const Column<N>& node2,
296  const Column<D>& distance,
297  const S& start_node,
298  const S& end_node,
299  Column<int32_t>& output_path_step,
300  Column<N>& output_node,
301  Column<D>& output_distance) {
302  auto func_timer = DEBUG_TIMER(__func__);
303  GraphTraversalResults<N, D> graph_traversal_results;
304  TerminalNodes<S> terminal_nodes(start_node, end_node);
305  try {
306  graph_traversal_results =
307  graph_shortest_path_impl(node1, node2, distance, terminal_nodes);
308  } catch (std::exception& e) {
309  return mgr.ERROR_MESSAGE(e.what());
310  }
311  auto output_timer = DEBUG_TIMER("Output shortest path results");
312  int32_t current_node_idx = graph_traversal_results.end_node_idx;
313  // Doing this first to determine how large the array is
314  int32_t num_hops = 0;
315  const D total_distance_to_origin_node =
316  graph_traversal_results.graph_distances[current_node_idx];
317  // Per the boost graph docs infinity distances are by default represented
318  // by std::numeric_limits<D>::max()
319  // https://www.boost.org/doc/libs/1_79_0/libs/graph/doc/dijkstra_shortest_paths.html
320  if (total_distance_to_origin_node != std::numeric_limits<D>::max()) {
321  while (current_node_idx != graph_traversal_results.start_node_idx) {
322  current_node_idx = graph_traversal_results.parents[current_node_idx];
323  num_hops++;
324  }
325  mgr.set_output_row_size(num_hops + 1);
326  current_node_idx = graph_traversal_results.end_node_idx;
327  int32_t path_step_idx = num_hops;
328  const auto last_node_key =
329  graph_traversal_results.attr_idx_map.get_key_for_idx(current_node_idx);
330  output_path_step[path_step_idx] = path_step_idx + 1;
331  output_node[path_step_idx] = last_node_key;
332  output_distance[path_step_idx] = total_distance_to_origin_node;
333  while (current_node_idx != graph_traversal_results.start_node_idx) {
334  current_node_idx = graph_traversal_results.parents[current_node_idx];
335  path_step_idx--;
336  output_path_step[path_step_idx] = path_step_idx + 1;
337  output_node[path_step_idx] =
338  graph_traversal_results.attr_idx_map.get_key_for_idx(current_node_idx);
339  output_distance[path_step_idx] =
340  graph_traversal_results.graph_distances[current_node_idx];
341  }
342  return num_hops + 1;
343  } else {
344  mgr.set_output_row_size(0);
345  return 0;
346  }
347 }
348 
349 // clang-format off
350 /*
351  UDTF: tf_graph_shortest_paths_distances__cpu_template(TableFunctionManager,
352  Cursor<Column<N> node1, Column<N> node2, Column<D> distance> edge_list,
353  S origin_node) ->
354  Column<N> origin_node | input_id=args<0>, Column<N> destination_node | input_id=args<0>,
355  Column<D> distance, Column<int32_t> num_edges_traversed, N=[int32_t, int64_t, TextEncodingDict],
356  D=[int32_t, int64_t, float, double], S=[int64_t, TextEncodingNone]
357 */
358 // clang-format on
359 
360 template <typename N, typename D, typename S>
361 int64_t tf_graph_shortest_paths_distances__cpu_template(TableFunctionManager& mgr,
362  const Column<N>& node1,
363  const Column<N>& node2,
364  const Column<D>& distance,
365  const S& start_node,
366  Column<N>& out_node1,
367  Column<N>& out_node2,
368  Column<D>& out_distance,
369  Column<int32_t>& out_num_hops) {
370  auto func_timer = DEBUG_TIMER(__func__);
371  GraphTraversalResults<N, D> graph_traversal_results;
372  TerminalNodes<S> terminal_nodes(start_node);
373  try {
374  graph_traversal_results =
375  graph_shortest_path_impl(node1, node2, distance, terminal_nodes);
376  } catch (std::exception& e) {
377  return mgr.ERROR_MESSAGE(e.what());
378  }
379  auto output_timer = DEBUG_TIMER("Output shortest paths results");
380  mgr.set_output_row_size(graph_traversal_results.num_vertices);
381  const N node1_val = graph_traversal_results.attr_idx_map.get_key_for_idx(
382  graph_traversal_results.start_node_idx);
384  tbb::blocked_range<int32_t>(0, graph_traversal_results.num_vertices),
385  [&](const tbb::blocked_range<int32_t>& r) {
386  const int32_t r_end = r.end();
387  for (int32_t vertex_idx = r.begin(); vertex_idx < r_end; ++vertex_idx) {
388  out_node1[vertex_idx] = node1_val;
389  out_node2[vertex_idx] =
390  graph_traversal_results.attr_idx_map.get_key_for_idx(vertex_idx);
391  out_distance[vertex_idx] = graph_traversal_results.graph_distances[vertex_idx];
392  if (out_distance[vertex_idx] == std::numeric_limits<D>::max()) {
393  out_distance.setNull(vertex_idx);
394  out_num_hops.setNull(vertex_idx);
395  } else {
396  int32_t num_hops = 0;
397  int32_t current_node_idx = vertex_idx;
398  while (current_node_idx != graph_traversal_results.start_node_idx) {
399  current_node_idx = graph_traversal_results.parents[current_node_idx];
400  num_hops++;
401  }
402  out_num_hops[vertex_idx] = num_hops;
403  }
404  }
405  });
406 
407  return graph_traversal_results.num_vertices;
408 }
409 
410 template <typename Z>
411 struct RasterGraphEdges {
412  std::vector<int32_t> bins_1;
413  std::vector<int32_t> bins_2;
414  std::vector<Z> distances;
415 };
416 
417 template <typename Z>
418 struct RasterGraphEdgeGenerator {
419  const Z slope_weight_exponent;
420  const Z slope_pct_max;
421  RasterGraphEdges<Z> raster_graph_edges;
422  std::atomic<int32_t> num_edges{0};
423 
424  RasterGraphEdgeGenerator(const int64_t max_size,
425  const Z slope_weight_exponent,
426  const Z slope_pct_max)
427  : slope_weight_exponent(slope_weight_exponent), slope_pct_max(slope_pct_max) {
428  raster_graph_edges.bins_1.resize(max_size);
429  raster_graph_edges.bins_2.resize(max_size);
430  raster_graph_edges.distances.resize(max_size);
431  }
432 
433  int64_t size() const { return num_edges; }
434 
435  inline void conditionally_write_edge_slope(const std::pair<int64_t, Z>& bin_1_idx_and_z,
436  const std::pair<int64_t, Z>& bin_2_idx_and_z,
437  const Z x_distance) {
438  // Only checks bin2's z val for nullness, so its up to the caller
439  // to enforce that bin1 is not null
440  if (bin_2_idx_and_z.second == inline_null_value<Z>()) {
441  return;
442  }
443  const Z slope = (bin_2_idx_and_z.second - bin_1_idx_and_z.second) / x_distance;
444  if (slope * 100.0 > slope_pct_max) {
445  return;
446  }
447  const int32_t edge_idx = num_edges++;
448  raster_graph_edges.bins_1[edge_idx] = static_cast<int32_t>(bin_1_idx_and_z.first);
449  raster_graph_edges.bins_2[edge_idx] = static_cast<int32_t>(bin_2_idx_and_z.first);
450  const Z abs_slope = 1.0 + abs(slope);
451  raster_graph_edges.distances[edge_idx] =
452  x_distance * pow(abs_slope, slope_weight_exponent);
453  }
454 
455  void trim_to_size() {
456  raster_graph_edges.bins_1.resize(num_edges);
457  raster_graph_edges.bins_2.resize(num_edges);
458  raster_graph_edges.distances.resize(num_edges);
459  }
460 };
461 
462 template <typename T, typename Z>
463 RasterGraphEdges<Z> generate_raster_graph_edges(const GeoRaster<T, Z>& geo_raster,
464  const Z slope_weight_exponent,
465  const Z slope_pct_max) {
466  RasterGraphEdgeGenerator<Z> raster_graph_edge_generator(
467  geo_raster.num_bins_ * 8, slope_weight_exponent, slope_pct_max);
468  const Z x_distance = static_cast<Z>(geo_raster.bin_dim_meters_);
469  const Z x_distance_diag = sqrt(2.0 * x_distance * x_distance);
471  tbb::blocked_range<int64_t>(0, geo_raster.num_y_bins_),
472  [&](const tbb::blocked_range<int64_t>& r) {
473  const int64_t end_y_bin = r.end();
474  for (int64_t y_bin = r.begin(); y_bin != end_y_bin; ++y_bin) {
475  for (int64_t x_bin = 0; x_bin < geo_raster.num_x_bins_; ++x_bin) {
476  const auto bin_1_idx_and_z =
477  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin, y_bin);
478  if (bin_1_idx_and_z.second == inline_null_value<Z>()) {
479  continue;
480  }
481  raster_graph_edge_generator.conditionally_write_edge_slope(
482  bin_1_idx_and_z,
483  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin, y_bin - 1),
484  x_distance);
485  raster_graph_edge_generator.conditionally_write_edge_slope(
486  bin_1_idx_and_z,
487  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin, y_bin + 1),
488  x_distance);
489  raster_graph_edge_generator.conditionally_write_edge_slope(
490  bin_1_idx_and_z,
491  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin - 1, y_bin),
492  x_distance);
493  raster_graph_edge_generator.conditionally_write_edge_slope(
494  bin_1_idx_and_z,
495  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin + 1, y_bin),
496  x_distance);
497  raster_graph_edge_generator.conditionally_write_edge_slope(
498  bin_1_idx_and_z,
499  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin - 1, y_bin - 1),
500  x_distance_diag);
501  raster_graph_edge_generator.conditionally_write_edge_slope(
502  bin_1_idx_and_z,
503  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin - 1, y_bin + 1),
504  x_distance_diag);
505  raster_graph_edge_generator.conditionally_write_edge_slope(
506  bin_1_idx_and_z,
507  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin + 1, y_bin + 1),
508  x_distance_diag);
509  raster_graph_edge_generator.conditionally_write_edge_slope(
510  bin_1_idx_and_z,
511  geo_raster.get_bin_idx_and_z_val_for_xy_bin(x_bin + 1, y_bin - 1),
512  x_distance_diag);
513  }
514  }
515  });
516  raster_graph_edge_generator.trim_to_size();
517  return raster_graph_edge_generator.raster_graph_edges;
518 }
519 
520 // clang-format off
521 /*
522  UDTF: tf_raster_graph_shortest_slope_weighted_path__cpu_template(TableFunctionManager,
523  Cursor<Column<T> x, Column<T> y, Column<Z> z> raster, TextEncodingNone agg_type,
524  T bin_dim | require="bin_dim > 0", bool geographic_coords,
525  int64_t neighborhood_fill_radius | require="neighborhood_fill_radius >= 0",
526  bool fill_only_nulls, T origin_x, T origin_y, T destination_x, T destination_y,
527  Z slope_weight_exponent, Z slope_pct_max) -> Column<int32_t> path_step, Column<T> x,
528  Column<T> y, T=[float, double], Z=[float, double]
529 */
530 // clang-format on
531 template <typename T, typename Z>
532 TEMPLATE_NOINLINE int32_t tf_raster_graph_shortest_slope_weighted_path__cpu_template(
534  const Column<T>& input_x,
535  const Column<T>& input_y,
536  const Column<Z>& input_z,
537  const TextEncodingNone& agg_type_str,
538  const T bin_dim_meters,
539  const bool geographic_coords,
540  const int64_t neighborhood_fill_radius,
541  const bool fill_only_nulls,
542  const T origin_x,
543  const T origin_y,
544  const T dest_x,
545  const T dest_y,
546  const Z slope_weight_exponent,
547  const Z slope_pct_max,
548  Column<int32_t>& output_path_step,
549  Column<T>& output_x,
550  Column<T>& output_y) {
551  const auto raster_agg_type = get_raster_agg_type(agg_type_str, false);
552  if (raster_agg_type == RasterAggType::INVALID) {
553  const std::string error_msg =
554  "Invalid Raster Aggregate Type: " + agg_type_str.getString();
555  return mgr.ERROR_MESSAGE(error_msg);
556  }
557 
558  GeoRaster<T, Z> geo_raster(input_x,
559  input_y,
560  input_z,
561  raster_agg_type,
562  bin_dim_meters,
563  geographic_coords,
564  true);
565 
566  // Check that origin and dest bin fall inside raster early
567  // to avoid needless work if we're out of bounds
568  const auto origin_x_bin = geo_raster.get_x_bin(origin_x);
569  const auto origin_y_bin = geo_raster.get_y_bin(origin_x);
570  const auto dest_x_bin = geo_raster.get_x_bin(dest_x);
571  const auto dest_y_bin = geo_raster.get_y_bin(dest_y);
572  if (geo_raster.is_bin_out_of_bounds(origin_x_bin, origin_y_bin)) {
573  return mgr.ERROR_MESSAGE("Origin coordinates are out of bounds.");
574  }
575  if (geo_raster.is_bin_out_of_bounds(dest_x_bin, dest_y_bin)) {
576  return mgr.ERROR_MESSAGE("Destination coordinates are out of bounds.");
577  }
578 
579  const auto origin_bin =
580  static_cast<int32_t>(geo_raster.get_bin_idx_for_xy_coords(origin_x, origin_y));
581  const auto dest_bin =
582  static_cast<int32_t>(geo_raster.get_bin_idx_for_xy_coords(dest_x, dest_y));
583  // Our CHECK macros don't parse the templated class properly, so fetch
584  // out of bounds value before calling CHECK_NE macro
585  const auto bin_out_of_bounds_idx = GeoRaster<T, Z>::BIN_OUT_OF_BOUNDS;
586  CHECK_NE(origin_bin, bin_out_of_bounds_idx);
587  CHECK_NE(dest_bin, bin_out_of_bounds_idx);
588 
589  if (neighborhood_fill_radius > 0) {
590  geo_raster.fill_bins_from_neighbors(
591  neighborhood_fill_radius, fill_only_nulls, RasterAggType::GAUSS_AVG);
592  }
593  auto raster_graph_edges =
594  generate_raster_graph_edges(geo_raster, slope_weight_exponent, slope_pct_max);
595  const Column<int32_t> node1(raster_graph_edges.bins_1);
596  const Column<int32_t> node2(raster_graph_edges.bins_2);
597  const Column<Z> distance(raster_graph_edges.distances);
598  GraphTraversalResults<int32_t, Z> graph_traversal_results;
599  TerminalNodes<int32_t> terminal_nodes(origin_bin, dest_bin);
600  try {
601  graph_traversal_results =
602  graph_shortest_path_impl(node1, node2, distance, terminal_nodes);
603  } catch (std::exception& e) {
604  return mgr.ERROR_MESSAGE(e.what());
605  }
606  auto output_timer = DEBUG_TIMER("Output shortest path results");
607  // const auto node1_val = graph_traversal_results.attr_idx_map.get_key_for_idx(
608  // graph_traversal_results.start_node_idx);
609  const auto node2_val = graph_traversal_results.attr_idx_map.get_key_for_idx(
610  graph_traversal_results.end_node_idx);
611  const int64_t vertex_idx = graph_traversal_results.end_node_idx;
612  int32_t current_node_idx = vertex_idx;
613  // Doing this first to determine how large the results are
614  int32_t num_hops = 0;
615  const auto distance_to_origin_node =
616  graph_traversal_results.graph_distances[vertex_idx];
617  if (distance_to_origin_node != std::numeric_limits<Z>::max()) {
618  while (current_node_idx != graph_traversal_results.start_node_idx) {
619  current_node_idx = graph_traversal_results.parents[current_node_idx];
620  num_hops++;
621  }
622  mgr.set_output_row_size(num_hops + 1);
623  current_node_idx = vertex_idx;
624  int32_t path_step_idx = num_hops;
625  const auto end_bin_idx =
626  graph_traversal_results.attr_idx_map.get_key_for_idx(current_node_idx);
627  CHECK_EQ(end_bin_idx, node2_val);
628  output_path_step[path_step_idx] = path_step_idx + 1;
629  const auto [end_path_x, end_path_y] =
630  geo_raster.get_xy_coords_for_bin_idx(end_bin_idx);
631  output_x[path_step_idx] = end_path_x;
632  output_y[path_step_idx] = end_path_y;
633  while (current_node_idx != graph_traversal_results.start_node_idx) {
634  current_node_idx = graph_traversal_results.parents[current_node_idx];
635  path_step_idx--;
636  const auto bin_idx =
637  graph_traversal_results.attr_idx_map.get_key_for_idx(current_node_idx);
638  output_path_step[path_step_idx] = path_step_idx + 1;
639  const auto [path_x, path_y] = geo_raster.get_xy_coords_for_bin_idx(bin_idx);
640  output_x[path_step_idx] = path_x;
641  output_y[path_step_idx] = path_y;
642  }
643  return num_hops + 1;
644  } else {
645  mgr.set_output_row_size(0);
646  return 0;
647  }
648 }
649 
650 #endif // #ifdef HAVE_TBB
651 #endif // #ifdef __CUDACC__
void set_output_row_size(int64_t num_rows)
#define CHECK_EQ(x, y)
Definition: Logger.h:230
int64_t get_bin_idx_for_xy_coords(const T x, const T y) const
std::pair< T, T > get_xy_coords_for_bin_idx(const int64_t bin_idx) const
std::string getString() const
Definition: heavydbTypes.h:276
DEVICE int64_t size() const
Definition: heavydbTypes.h:716
T * ptr_
Definition: heavydbTypes.h:690
void fill_bins_from_neighbors(const int64_t neighborhood_fill_radius, const bool fill_only_nulls, const RasterAggType raster_agg_type=RasterAggType::GAUSS_AVG)
T get_y_bin(const T input) const
T get_x_bin(const T input) const
bool is_bin_out_of_bounds(const int64_t x_bin, const int64_t y_bin) const
static constexpr int32_t INVALID_STR_ID
#define CHECK_NE(x, y)
Definition: Logger.h:231
int64_t num_rows_
Definition: heavydbTypes.h:691
bool g_enable_smem_group_by true
std::pair< int64_t, Z > get_bin_idx_and_z_val_for_xy_bin(const int64_t x_bin, const int64_t y_bin) const
DEVICE bool isNull(int64_t index) const
Definition: heavydbTypes.h:719
DEVICE void setNull(int64_t index)
Definition: heavydbTypes.h:720
void parallel_for(const blocked_range< Int > &range, const Body &body, const Partitioner &p=Partitioner())
constexpr unsigned N
Definition: Utm.h:110
bool g_enable_watchdog false
Definition: Execute.cpp:79
#define DEBUG_TIMER(name)
Definition: Logger.h:374
RasterAggType get_raster_agg_type(const std::string &agg_type_str, const bool is_fill_agg)
#define TEMPLATE_NOINLINE
Definition: heavydbTypes.h:54