Re: [graph] which algorithm/visitor to use?

From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2025-05-11 19:53:52

niedz., 11 maj 2025 o 02:46 Seth via Boost <boost_at_[hidden]>
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;