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

From: Seth (bugs_at_[hidden])
Date: 2025-05-11 00:37:35

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