有效扩展图边集
我有一组图中的边，并且希望将其扩展为与任何边共享顶点的所有边。我怎样才能用 boost::graph 有效地做到这一点？
我能想到的唯一方法是提取所有源顶点和目标顶点的简单解决方案，使用boost::adjacent_vertices获取所有邻接，然后使用<创建所有新边代码>boost::edge。有更好的方法吗？
上下文：图顶点是地形三角剖分的质心，边连接对应三角形相邻的顶点（因此有点像对偶图）。我想要扩展的边集对应于被阻止的三角形间路径，并且被阻止的区域正在扩展。该区域有点圆形，因此我使用上面的天真的方法看到的大部分边缘都已经是该集合的一部分。
I have a set of edges from a graph, and would like to expand it with all edges that share a vertex with any edge. How could I do this efficiently with boost::graphs?
The only way I've been able to come up with is the naive solution of extracting all the source and target vertices, using boost::adjacent_vertices to get all adjacencies and then creating all the new edges with boost::edge. Is there a better way of doing this?
Context: The graph vertices are centroids of a terrain triangulation, the edges connect vertices whose corresponding triangles are adjacent (so sort of a dual graph). The set of edges I'm looking to expand corresponds to inter-triangle paths which are blocked, and the blocked area is expanding. The area is sort-of circular, so most of the edges I'll see using my naive approach above will already be part of the set.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不要在每个步骤中考虑所有相邻顶点来生成新边，而是使用属性映射来标记已经遇到的边。因此，您只需在每个步骤中考虑未标记的边缘。将所有与该顶点相关的边添加到集合中后，就会对顶点进行标记。
鉴于 boost::graph 使用的内部数据结构要么是邻接列表，要么是邻接矩阵，我认为不可能有任何进一步的改进。
Instead of considering all adjacent vertices in each step to generate the new edges, use a property map to mark edges already encounterd. Thus, you need to consider unmarked edges in each step only. A vertex is marked after adding all edges incident to it to your set.
Given the fact that the internal data structure used by boost::graph is either an adjacency list or an adjacency matrix, I do not think that any further improvement is possible.