| 79 | } |
| 80 | |
| 81 | std::vector<Point_2> shorted_path(const Point_2& start, const Point_2& goal) const { |
| 82 | auto& adj = adjacency_list; |
| 83 | if (adj.count(start) == 0 || adj.count(goal) == 0) return {}; |
| 84 | |
| 85 | std::map<Point_2, Point_2> predecessor; |
| 86 | std::queue<Point_2> q; |
| 87 | |
| 88 | // seed BFS |
| 89 | predecessor[start] = start; // mark start as "seen" |
| 90 | q.push(start); |
| 91 | |
| 92 | // BFS |
| 93 | bool found = false; |
| 94 | while (!q.empty() && !found) { |
| 95 | Point_2 u = q.front(); q.pop(); |
| 96 | for (auto& v : adj.at(u)) { |
| 97 | // if v has no predecessor yet, it's unseen |
| 98 | if (!predecessor.count(v)) { |
| 99 | predecessor[v] = u; |
| 100 | q.push(v); |
| 101 | if (v == goal) { found = true; break; } |
| 102 | } |
| 103 | } |
| 104 | } |
| 105 | |
| 106 | if (!found) return {}; |
| 107 | |
| 108 | // reconstruct path |
| 109 | std::vector<Point_2> path; |
| 110 | for (Point_2 cur = goal; cur != start; cur = predecessor[cur]) |
| 111 | path.push_back(cur); |
| 112 | path.push_back(start); |
| 113 | std::reverse(path.begin(), path.end()); |
| 114 | return path; |
| 115 | } |
| 116 | |
| 117 | |
| 118 | std::vector<Point_2> shorted_path(const Point_2& start, const std::set<Point_2>& goal) const { |