[graph] which algorithm/visitor to use?
Hi All, I have a graph-related problem that I thought was easy, but I do not seem to be able to find the right tools (algorithms, visitors) in the library to solve it. Maybe someone in the list can give me a hint. I represent airports and their air connections as a graph: * Each airport is a vertex. * There are geographical coordinates associated with each airport. * When there is at least one flight operating between airports A and B, this is represented as an edge. The task is to enumerate all paths between two given vertices U and V, in an efficient way naturally, given the following constraints: 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? Regards, &rzej;
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
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
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;
niedz., 11 maj 2025 o 00:41 Steven Watanabe via Boost <boost@lists.boost.org> napisał(a):
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?
Thanks! So, to the extent that I understand `filtered_graph` (the documentation doesn't address all my questions), this view will handle one of my constraints: the predicate P(U, V, W) which tells that a given airport (edge) W is not too far away from airports U and V. But it will not address my other constraint that the paths must be composed of no more with N edges. (BTW, the N will be `3` and the other predicate will further filter down the search space, so I do not expect the result to be huge.) I guess that "being the fourth edge in the path" is not a good candidate for a predicate, as it would have to give different answers depending on the context. I would have expected that the graph library for the DFS iteration would have an instruction like "stop processing this sub-tree, move on to the next one", or that finding paths no longer than a given value is so common that there is a dedicated algorithm for it. Regards, &rzej;
participants (3)
-
Andrzej Krzemienski -
Seth -
Steven Watanabe