pon., 12 maj 2025 o 00:49 Seth <bugs@sehe.nl> 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;