c++ - 有效地在 Boost BGL 图中找到所有可达的顶点

Question

我是 boost 图形库的新手，正在尝试解决以下问题问题:

在图表中 (boost::adjacency_list) 我有 3 个不同的顶点类型(使用 std::variant 实现)和当前无向边:

1. 连接器 (1)
2. 开关 (2)
3. 开关状态 (3) -(开/关)

我图中的典型层次结构是这样的:

(1a) - (2a) - (1b) - (1d) - (2b) - (1e)
        |                    |
       (3a)                 (3b)
        |                    |
       (1c)

我需要做的是找到所有可达的顶点从某个起点(例如 1a)开始:

1a -> 2a -> 1b -> 1d -> 2b -> 1e

当然会立即想到使用 BFS 或 DFS! :-)

然而:顶点的状态(2)(开关或继电器)由直接连接的状态( bool 值)控制顶点 (3)。这意味着没有办法遍历从 (1a) 到 (1b) 通过顶点 (2a) 如果 (3a) 是(比方说)假。最后:不能从类型 (2) 遍历类型 (3) 顶点。

我的问题是:有没有人对如何有效地实现这样的图遍历？我已经使用大量 vector/映射等和 DFS 在普通 C++ 中实现了这一点，但我想将代码移动到底层图形的更高、更抽象(但希望仍然有效)的实现中!

我不确定我是否应该:

1. 使用一个filtered_graph，只使用BFS或DFS遍历？
2. 然后根据类型 3 顶点状态创建子图并应用 BFS/DFS？
3. 有一种方法可以在通过 BFS/DFSvisitor 进行搜索时“即时”实现这一目标吗？
4. 另一个解决方案？

非常欢迎有帮助的想法!

PS:该代码用于模拟电网 - 以防万一。

Answer 1

Use a filtered_graph and just use BFS or DFS to traverse?

“隐藏”关闭边缘的过滤图在我看来在概念上最简单。如果您的属性包足够简单(没有动态分配，也没有引用来帮助别名规则)，编译器将在优化它方面做得非常出色。

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.

如果没有，在基于未记录的实现细节进行优化之前，我会三思而后行。它可能会在未来的版本中中断，或者与例如库中隐藏的特例。