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;