我的程序首先创建一个图(约 1K-50K 个顶点),通常由几百个连接的组件组成。
程序只需要能够操作和可视化单个组件(使用力导向布局算法)。
如果能够将每个连接的组件进一步拆分为连接的子组件(通过删除边或顶点),那就太好了(但不是必需的)。
所以我的问题是,我可以使用 subgraph 或 filtered_graph 类模板来实现所需的功能(维护可以单独操作并可能通过删除边/顶点进一步 segmentation 的组件图集合)吗?还是有另一种更好的方法?
如果这个问题太基础了,我深表歉意。我刚开始学习 BGL,对这个库还不太熟悉。提前致谢!
最佳答案
使用connected_components
为每个组件分配一个唯一编号,将其存储在 property 中的节点。然后您可以在 filtered_graph
中使用该属性判断给定组件是否属于当前事件图的谓词。顶点谓词是直截了当的,而边谓词可以简单地查看任一端点来做出选择。子图的编号将存储在谓词对象本身中。
是否采用不同的方法更好取决于您的用例。如果组件变化不大,并且您必须执行大量遍历所有节点的操作,那么使用单独的图形对象可能会更好。您可以将它们创建为如上所述构造的过滤图的拷贝。如果图形被大量修改,一些不必扫描整个图形来更新连接组件的方法将很有用。如果没有删除边缘,incremental_components
可能会成功。
关于c++ - 将 boost 图拆分为连接的组件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16407791/