有效地在 Boost BGL 图中找到所有可达的顶点
Find all reachable vertices in a Boost BGL graph efficiently
我是 boost 图形库的新手，正在尝试解决以下问题
问题：
在图表中 (boost::adjacency_list) 我有 3 个不同的
顶点类型（使用 std::variant 实现）和当前
无向边：
- 连接器 (1)
- 切换 (2)
- 开关状态 (3) - (ON/OFF)
我图中的典型层次结构是这样的：
(1a) - (2a) - (1b) - (1d) - (2b) - (1e)
| |
(3a) (3b)
| |
(1c)
我需要做的是找到所有可达的顶点
从某个起点（例如 1a）：
1a -> 2a -> 1b -> 1d -> 2b -> 1e
当然立刻想到使用 BFS 或 DFS！ :-)
然而：顶点的状态（2）（开关或继电器）
由直接连接的状态（布尔值）控制
顶点 (3)。这意味着没有办法遍历
从 (1a) 到 (1b) 通过顶点 (2a) 如果 (3a) 是（比方说）假。
最后：不能从类型 (2) 遍历类型 (3) 顶点。
我的问题是：有没有人对如何
有效地实现这样的图遍历？我已经使用大量 vectors/maps 等和 DFS 在纯 C++ 中实现了这一点，但我想将代码移动到底层图形的更高、更抽象（但希望仍然有效）的实现！
我不确定我是否应该：
- 用一个filtered_graph只用BFS或DFS遍历？
- 然后根据类型 3 顶点状态创建一个 sub_graph 并应用 BFS/DFS?
- 有一种方法可以在通过 BFS/DFSvisitor?
搜索时实现此 "on the fly"
- 另一个解决方案？
非常欢迎有帮助的想法！
PS：该代码用于模拟电网 - 以防万一。
Use a filtered_graph and just use BFS or DFS to traverse?
"hide" 关闭边缘的过滤图在我看来在概念上最简单。如果您的 属性 包足够简单（没有动态分配，也没有参考来帮助使用别名规则），编译器将在优化它方面做得非常出色。
Create a sub_graph depending on the type 3 vertices state then and apply BFS/DFS?
子图有相当大的开销，所以它们看起来不像你的票。
There's a way to achieve this "on the fly" while searching via BFS/DFSvisitor?
我也这么认为。您可以让访问者对 "examine_edge" 事件执行操作并在颜色图中标记下游顶点。您应该检查算法文档以查看是否记录了颜色映射的语义。
If so, this would seem to be likely the most optimal solution, even though conceptually it is a little bit more complex than the filtered_graph approach.
如果没有，我会在基于未记录的实施细节进行优化之前三思而后行。它可能会在未来的版本中中断，或者与例如图书馆隐藏特例
我是 boost 图形库的新手，正在尝试解决以下问题 问题：
在图表中 (boost::adjacency_list) 我有 3 个不同的 顶点类型（使用 std::variant 实现）和当前 无向边：
- 连接器 (1)
- 切换 (2)
- 开关状态 (3) - (ON/OFF)
我图中的典型层次结构是这样的：
(1a) - (2a) - (1b) - (1d) - (2b) - (1e)
| |
(3a) (3b)
| |
(1c)
我需要做的是找到所有可达的顶点 从某个起点（例如 1a）：
1a -> 2a -> 1b -> 1d -> 2b -> 1e
当然立刻想到使用 BFS 或 DFS！ :-)
然而：顶点的状态（2）（开关或继电器） 由直接连接的状态（布尔值）控制 顶点 (3)。这意味着没有办法遍历 从 (1a) 到 (1b) 通过顶点 (2a) 如果 (3a) 是（比方说）假。 最后：不能从类型 (2) 遍历类型 (3) 顶点。
我的问题是：有没有人对如何 有效地实现这样的图遍历？我已经使用大量 vectors/maps 等和 DFS 在纯 C++ 中实现了这一点，但我想将代码移动到底层图形的更高、更抽象（但希望仍然有效）的实现！
我不确定我是否应该：
- 用一个filtered_graph只用BFS或DFS遍历？
- 然后根据类型 3 顶点状态创建一个 sub_graph 并应用 BFS/DFS?
- 有一种方法可以在通过 BFS/DFSvisitor? 搜索时实现此 "on the fly"
- 另一个解决方案？
非常欢迎有帮助的想法！
PS：该代码用于模拟电网 - 以防万一。
Use a filtered_graph and just use BFS or DFS to traverse?
"hide" 关闭边缘的过滤图在我看来在概念上最简单。如果您的 属性 包足够简单（没有动态分配，也没有参考来帮助使用别名规则），编译器将在优化它方面做得非常出色。
Create a sub_graph depending on the type 3 vertices state then and apply BFS/DFS?
子图有相当大的开销，所以它们看起来不像你的票。
There's a way to achieve this "on the fly" while searching via BFS/DFSvisitor?
我也这么认为。您可以让访问者对 "examine_edge" 事件执行操作并在颜色图中标记下游顶点。您应该检查算法文档以查看是否记录了颜色映射的语义。
If so, this would seem to be likely the most optimal solution, even though conceptually it is a little bit more complex than the filtered_graph approach.
如果没有，我会在基于未记录的实施细节进行优化之前三思而后行。它可能会在未来的版本中中断，或者与例如图书馆隐藏特例