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); } ``` On Sun, May 11, 2025, at 12:41 AM, Steven Watanabe via Boost wrote:
AMDG
On 5/10/25 1:49 PM, Andrzej Krzemienski via Boost wrote:
<snip> The task is to enumerate all paths between two given vertices U and V, in an efficient way naturally, given the following constraints:
That could be a lot of paths.
1. The path cannot be composed of more than N edges 2. The path cannot contain a vertex "too far away from U and V", that is, there would be a predicate P that tells for a given vertex W the value P(U, V, W) that tells if vertex W is acceptable.
So, I would need a tool that instructs the algorithm that when a certain vertex or an edge is encountered, an algorithm should be skipped on a given branch of the graph, but resume from the next branch. Is there a tool like that in Boost.Graph?
filtered_graph?
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost