niedz., 11 maj 2025 o 02:46 Seth via Boost <boost@lists.boost.org> napisał(a):
Slightly less terse, concurring.
Is this a useful start?
Note absolutely bogus data for the demo. You would want to use proper map projections for the distance calulations (TODO).
Ideas: - Perhaps emply astar_search to get "all" the paths (very unlikely you really want *all* possible paths?) - calculating min hops beforehand is optional required as you should filter out overlong paths at the last steps anyways - if graphs are big and `filtered_graph` ends up invoking the predicate too much, consider `copy_graph` first - using `adjacency_matrix` instead of `adjacency_list` facilitaties looking up edges by (source,target); this way the initialization of distmatrix and `Flight::leg_` could be combined efficiently
[Coliru](https://coliru.stacked-crooked.com/a/611d990f363a7895)
```c++ #include <boost/geometry.hpp> #include <boost/graph/adjacency_list.hpp> // adjacency_list #include <boost/graph/breadth_first_search.hpp> // breadth_first_search #include <boost/graph/filtered_graph.hpp> // filtered_graph #include <boost/graph/graph_utility.hpp> // print_graph #include <boost/graph/johnson_all_pairs_shortest.hpp> #include <fmt/ranges.h>
namespace bg = boost::geometry; // TODO use correct geospatial projection? using Location = bg::model::point<double, 2, bg::cs::cartesian>; using Distance = double;
struct Airport { std::string name_ = {}, code_ = {}; Location location_ = {}; };
struct Flight { std::string flight_number_; std::string operator_; Distance leg_ = 0; };
// internal name property "code", just for readability here: template <> struct boost::graph::internal_vertex_name<Airport> { struct type { using result_type = std::string; constexpr std::string const& operator()(Airport const& airport) const { return airport.code_; } }; };
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Airport, Flight>; using V = boost::graph_traits<G>::vertex_descriptor; using E = boost::graph_traits<G>::edge_descriptor;
int main() { G g; auto const iata = get(&Airport::code_, g); auto const distance = [loc = get(&Airport::location_, g)](V v, V u) { return bg::distance(loc[v], loc[u]); };
// imaginary 6 airports: add_vertex({"Los Angeles International Airport", "LAX", {34.0522, -118.2437}}, g); add_vertex({"Chicago O'Hare International Airport", "ORD", {41.9742, -87.9073}}, g); add_vertex({"Hartsfield-Jackson Atlanta International Airport", "ATL", {33.6407, -84.4279}}, g); add_vertex({"Denver International Airport", "DEN", {39.8561, -104.6737}}, g); add_vertex({"Dallas/Fort Worth International Airport", "DFW", {32.8968, -97.0379}}, g); add_vertex({"John F. Kennedy International Airport", "JFK", {40.6413, -73.7781}}, g);
// imaginary flights: add_edge("ORD", "ATL", {"DL456", "Delta Airlines"}, g); add_edge("ORD", "DEN", {"SW456", "Southwest Airlines"}, g); add_edge("DEN", "DFW", {"SW123", "Southwest Airlines"}, g); add_edge("LAX", "ORD", {"AA123", "American Airlines"}, g); add_edge("JFK", "LAX", {"DL789", "Delta Airlines"}, g); add_edge("DFW", "JFK", {"AA456", "American Airlines"}, g); add_edge("LAX", "ATL", {"UA123", "United Airlines"}, g); add_edge("ATL", "DEN", {"UA789", "United Airlines"}, g); add_edge("ATL", "DFW", {"DL123", "Delta Airlines"}, g); add_edge("ATL", "ORD", {"AA456", "American Airlines"}, g);
// manually set flight distances
for (E e : boost::make_iterator_range(edges(g))) g[e].leg_ = distance(source(e, g), target(e, g));
print_graph(g, iata);
// cache the number of vertices size_t const numv = num_vertices(g);
// get all straight-line distances std::vector distmatrix(numv, std::vector<Distance>(numv)); for (auto v : boost::make_iterator_range(vertices(g))) for (auto u : boost::make_iterator_range(vertices(g))) distmatrix[v][u] = distance(v, u);
// For effective PATH distances instead: // ok = johnson_all_pairs_shortest_paths(g, distmatrix, weight_map(get(&Flight::distance_, g)));
// for dense graphs, prefer floyd_warshall_all_pairs_shortest_paths std::vector hops(numv, std::vector<unsigned>(numv)); bool ok = johnson_all_pairs_shortest_paths(g, hops, weight_map(boost::make_constant_property<E>(1u))); assert(ok); // no negative cycles
fmt::print("hops: {}\n", hops); fmt::print("distmatrix: {:::4.2f}\n", distmatrix);
static size_t constexpr MaxHops = 3; // max path length
auto paths = [&](auto from, auto to, Distance threshold) { // TODO error handling V v = *g.vertex_by_property({.code_ = from}); V u = *g.vertex_by_property({.code_ = to});
if (hops[v][u] > MaxHops) return;
boost::filtered_graph eligible( g, boost::keep_all(), // std::function([&](V w) { return distance(u, w) < threshold && distance(v, w) < threshold; }));
fmt::print("Eligible sub-graph from {} (#{}) to {} (#{}) at threshold: {}\n", from, v, to, u, threshold); print_graph(eligible, iata);
// TODO enumerate actual paths };
paths("LAX", "DFW", 150.0); paths("LAX", "DFW", 35.0); paths("LAX", "DFW", 32.8); } ```
Thanks Seth. This is indeed a solution. But I think it is too heavy for the task at hand. If I understand this correctly, it will first compute *every* path between every two airports, only to later discard the too long ones. The constraint that my problem has -- allow only four or less edges in the path -- should be able to make the task computationally smaller. Regards, &rzej;