我是 boost 图形库的新手,正在尝试解决以下问题 问题:
在图表中 (boost::adjacency_list) 我有 3 个不同的 顶点类型(使用 std::variant 实现)和当前 无向边:
- 连接器 (1)
- 开关 (2)
- 开关状态 (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++ 中实现了这一点,但我想将代码移动到底层图形的更高、更抽象(但希望仍然有效)的实现中!
我不确定我是否应该:
- 使用一个filtered_graph,只使用BFS或DFS遍历?
- 然后根据类型 3 顶点状态创建子图并应用 BFS/DFS?
- 有一种方法可以在通过 BFS/DFSvisitor 进行搜索时“即时”实现这一目标吗?
- 另一个解决方案?
非常欢迎有帮助的想法!
PS:该代码用于模拟电网 - 以防万一。
最佳答案
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.
如果没有,在基于未记录的实现细节进行优化之前,我会三思而后行。它可能会在未来的版本中中断,或者与例如库中隐藏的特例。
关于c++ - 有效地在 Boost BGL 图中找到所有可达的顶点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53724307/