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

From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2025-05-13 11:10:46

pon., 12 maj 2025 o 00:49 Seth <bugs_at_[hidden]> napisał(a):

> On Sun, May 11, 2025, at 9:53 PM, Andrzej Krzemienski wrote:
>
> 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.
>
>
> It feels like this as a "concern" really has nothing to do with graphs,
> and everything with geometry? How about you stuff all the airports in a
> boost::geometry::index::rtree and query the nearest until you cross the
> threshold distance for both airports (the query results will be in
> ascending order of distance - see
> https://stackoverflow.com/a/22910024/85371 (include the comments from the
> BG devs).
>
> That moves all the distance calculations out of your hand and puts the
> onus of spatial indexing on the BG library.
>
> I think the rest could be simplified even without the filtered_graph with
> just some custom heuristics on astar_search. IIRC the heuristics allow you
> to control which edges to examine or skip [Aas opposed to the DFS/BFS
> visitors, as you correctly noted.]. I have't used A* as much myself, to be
> completely frank.
>
> Good luck
>

Thanks. This is an important observation that although I am using
something that can be modeled as a graph, using Boost.Graph may be a bad
choice.

On the other hand, this geographical constraint seems to have drawn most of
the attention. But I also expressed another problem: being able to
constrain the search to paths limited by the number of edges. Is this also
something beyond the scope of Boost.Graph? Is my use case too simplistic
for a grah library to be useful?

Regards,
&rzej;