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

From: Andrzej Krzemienski (akrzemi1_at_[hidden])
Date: 2025-05-11 19:49:15

niedz., 11 maj 2025 o 00:41 Steven Watanabe via Boost <boost_at_[hidden]>
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;