拆分升压图分成连接组件 [英] splitting a boost graph into connected components

问题描述

我的程序通过创建一个图（〜1K-50K顶点），通常是由几百个连接组件的开出。

My program starts out by creating a graph (~1K-50K vertices) that usually consists of a few hundred connected components.

程序只需要能够操纵和可视化各个组件（使用力导向布局算法）。

The program only needs to be able to manipulate and visualize individual components (using force-directed layout algorithm).

这将（通过去除边或顶点）是伟大的（但不是必须）有进一步分裂的能力各连接部件插入连接子。

It would be great (but not essential) to have the capability of further splitting each connected component into connected subcomponents (by removing edges or vertices).

所以我的问题是，我可以使用使用子或filtered_graph类模板来实现所需的功能（维护可以通过删除边/顶点单独操作，并可能进一步细分组件图形的集合）？还是有一个其他更好的方法？

So my question is, can I use use subgraph or filtered_graph class templates to achieve the required functionality (maintain a collection of component graphs that can be individually manipulated and possibly further subdivided by removing edges/vertices)? Or is there an another, better approach?

我道歉，如果这个问题是太基本。我刚开始学BGL，而不是与此库舒适又不失。在此先感谢！

I apologize if this question is too basic. I've just started to learn BGL and not comfortable with this library yet. Thanks in advance!

推荐答案

使用的 connected_components 以一个唯一的编号分配给每个组成部分，其存储在一个的节点的属性。然后你可以使用这个属性在 filtered_graph predicate决定给定的组件是否属于当前活动的图形或没有。顶点predicate是直线前进，而边缘predicate可以简单地看一下两个端点做出的选择。子图的数量将存储在predicate对象本身。

Use connected_components to assign a unique number to each component, storing it in a property of the nodes. Then you can use that property in the filtered_graph predicate to decide whether a given component belongs to the currently active graph or not. The vertex predicate would be straight-forward, whereas the edge predicate could simply look at either endpoint to make its choice. The number of the subgraph would be stored in the predicate objects themselves.

无论采用不同的方法将尤为明显取决于你的使用情况。如果组件不发生大的变化，你必须执行大量其中遍历所有的节点，然后有单独的图形对象可能会更好操作。如上所述的构造图过滤的副本，您可以创建它们。如果图被修改了很多，一些方法，将不具有扫描整个图形来更新连接组件将是有益的。如果没有得到边去掉， incremental_components 可能做的伎俩。

Whether a different approach would be beter depends on your use case. If the components don't change much, and you have to perform a lot of operations which iterate over all nodes, then having separate graph objects might be better. You could create them as copies of filtered graphs constructed as described above. If the graph gets modified a lot, some approach which will not have to scan the whole graph to update connected components would be useful. If no edges get removed, incremental_components might do the trick.

这篇关于拆分升压图分成连接组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！