290 const GraphType& graph,
const std::vector<PathDistance>& arc_lengths,
291 typename GraphType::NodeIndex source,
292 typename GraphType::NodeIndex destination,
unsigned k) {
293 using NodeIndex =
typename GraphType::NodeIndex;
297 CHECK_GE(k, 0) <<
"k must be nonnegative. Input value: " << k;
298 CHECK_NE(k, 0) <<
"k cannot be zero: you are requesting zero paths!";
300 CHECK_GT(graph.num_nodes(), 0) <<
"The graph is empty: it has no nodes";
301 CHECK_GT(graph.num_arcs(), 0) <<
"The graph is empty: it has no arcs";
303 CHECK_GE(source, 0) <<
"The source node must be nonnegative. Input value: "
305 CHECK_LT(source, graph.num_nodes())
306 <<
"The source node must be a valid node. Input value: " << source
307 <<
". Number of nodes in the input graph: " << graph.num_nodes();
308 CHECK_GE(destination, 0)
309 <<
"The source node must be nonnegative. Input value: " << destination;
310 CHECK_LT(destination, graph.num_nodes())
311 <<
"The destination node must be a valid node. Input value: "
313 <<
". Number of nodes in the input graph: " << graph.num_nodes();
319 std::tuple<std::vector<NodeIndex>,
PathDistance> first_path =
321 if (std::get<0>(first_path).empty())
return paths;
322 paths.paths.push_back(std::move(std::get<0>(first_path)));
323 paths.distances.push_back(std::get<1>(first_path));
332 std::priority_queue<internal::PathWithPriority<GraphType>,
333 std::vector<internal::PathWithPriority<GraphType>>,
334 std::greater<internal::PathWithPriority<GraphType>>>>
340 VLOG(1) <<
"k: " << k;
343 const absl::Span<NodeIndex> last_shortest_path =
344 absl::MakeSpan(paths.paths.back());
349 for (
int spur_node_position = 0;
350 spur_node_position < last_shortest_path.size() - 1;
351 ++spur_node_position) {
352 VLOG(4) <<
" spur_node_position: " << spur_node_position;
353 VLOG(4) <<
" last_shortest_path: "
354 << absl::StrJoin(last_shortest_path,
" - ") <<
" ("
355 << last_shortest_path.size() <<
")";
356 if (spur_node_position > 0) {
357 DCHECK_NE(last_shortest_path[spur_node_position], source);
359 DCHECK_NE(last_shortest_path[spur_node_position], destination);
361 const NodeIndex spur_node = last_shortest_path[spur_node_position];
365 const absl::Span<NodeIndex> root_path =
366 last_shortest_path.subspan(0, spur_node_position + 1);
367 DCHECK_GE(root_path.length(), 1);
368 DCHECK_NE(root_path.back(), destination);
379 std::vector<PathDistance> arc_lengths_for_detour = arc_lengths;
380 for (absl::Span<const NodeIndex> previous_path : paths.paths) {
386 if (previous_path.size() <= root_path.length())
continue;
387 const bool has_same_prefix_as_root_path = std::equal(
388 root_path.begin(), root_path.end(), previous_path.begin(),
389 previous_path.begin() + root_path.length());
390 if (!has_same_prefix_as_root_path)
continue;
392 const typename GraphType::ArcIndex after_spur_node_arc =
394 previous_path[spur_node_position + 1]);
395 VLOG(4) <<
" after_spur_node_arc: " << graph.Tail(after_spur_node_arc)
396 <<
" - " << graph.Head(after_spur_node_arc) <<
" (" << source
397 <<
" - " << destination <<
")";
398 arc_lengths_for_detour[after_spur_node_arc] =
406 for (
int node_position = 0; node_position < spur_node_position;
408 for (
const int arc : graph.OutgoingArcs(root_path[node_position])) {
412 VLOG(3) <<
" arc_lengths_for_detour: "
413 << absl::StrJoin(arc_lengths_for_detour,
" - ");
418 std::tuple<std::vector<NodeIndex>,
PathDistance> detour_path =
420 spur_node, destination);
422 if (std::get<0>(detour_path).empty()) {
426 VLOG(2) <<
" detour_path: "
427 << absl::StrJoin(std::get<0>(detour_path),
" - ") <<
" ("
428 << std::get<0>(detour_path).size()
429 <<
"): " << std::get<1>(detour_path);
430 std::vector<NodeIndex> spur_path = std::move(std::get<0>(detour_path));
431 if (ABSL_PREDICT_FALSE(spur_path.empty()))
continue;
434 CHECK_EQ(root_path.back(), spur_path.front());
435 CHECK_EQ(spur_node, spur_path.front());
437 if (spur_path.size() == 1) {
438 CHECK_EQ(spur_path.front(), destination);
443 const bool root_path_leads_to_spur_path = absl::c_any_of(
444 graph.OutgoingArcs(root_path.back()),
445 [&graph, node_after_spur_in_spur_path = *(spur_path.begin() + 1)](
446 const typename GraphType::ArcIndex arc_index) {
447 return graph.Head(arc_index) == node_after_spur_in_spur_path;
449 CHECK(root_path_leads_to_spur_path);
454 for (absl::Span<const NodeIndex> previous_path : paths.paths) {
455 if (previous_path.size() <= spur_node_position + 1)
continue;
456 const bool has_same_prefix_as_root_path = std::equal(
457 root_path.begin(), root_path.end(), previous_path.begin(),
458 previous_path.begin() + root_path.length());
459 if (has_same_prefix_as_root_path) {
460 CHECK_NE(spur_path[1], previous_path[spur_node_position + 1])
461 <<
"Forbidden arc " << previous_path[spur_node_position]
462 <<
" - " << previous_path[spur_node_position + 1]
463 <<
" is present in the spur path "
464 << absl::StrJoin(spur_path,
" - ");
470 std::vector<NodeIndex> new_path;
471 absl::c_copy(root_path.subspan(0, spur_node_position),
472 std::back_inserter(new_path));
473 absl::c_copy(spur_path, std::back_inserter(new_path));
475 DCHECK_EQ(new_path.front(), source);
476 DCHECK_EQ(new_path.back(), destination);
481 absl::flat_hash_set<NodeIndex> visited_nodes(new_path.begin(),
483 CHECK_EQ(visited_nodes.size(), new_path.size());
499 const bool is_new_path_already_known = std::any_of(
500 variant_path_queue.container().cbegin(),
501 variant_path_queue.container().cend(),
503 return element.path() == new_path;
505 if (is_new_path_already_known)
continue;
509 VLOG(5) <<
" New potential path generated: "
510 << absl::StrJoin(new_path,
" - ") <<
" (" << new_path.size()
511 <<
")" <<
" with length " << path_length;
512 VLOG(5) <<
" Root: " << absl::StrJoin(root_path,
" - ") <<
" ("
513 << root_path.size() <<
")";
514 VLOG(5) <<
" Spur: " << absl::StrJoin(spur_path,
" - ") <<
" ("
515 << spur_path.size() <<
")";
516 variant_path_queue.emplace(
517 path_length, std::move(new_path));
524 if (variant_path_queue.empty())
break;
527 variant_path_queue.top();
528 VLOG(5) <<
"> New path generated: "
529 << absl::StrJoin(next_shortest_path.
path(),
" - ") <<
" ("
530 << next_shortest_path.
path().size() <<
")";
531 paths.paths.emplace_back(next_shortest_path.
path());
532 paths.distances.push_back(next_shortest_path.
priority());
533 variant_path_queue.pop();