如何使用BGL向图作为一个无向(用于布局算法中使用)?
-
23-08-2019 - |
题
我正在一个有向图(实际上是一个双向的一个)与Boost.Graph。我想使用的布局算法,存在(镰-河合或Fruchterman-莱因戈尔德),但他们仅接受无向图作为参数。
什么是使用这些布局算法最简单的方法? 更一般地,什么是引诱的算法,以为有向图实际上是无向的路吗?
谢谢, 伯努瓦
解决方案
您确定Fruchterman-莱因戈尔德算法只接受无向图?我试图从 Boost文档运行的小例子使用双向图形代替无向一个,它编译和运行得很好。
要回答你的问题,我不知道有内置的BGL为有向图转换成无向一个任何设施。我发现是创建一个新图形,并从原来的添加所有边缘的唯一解决方案:
typedef adjacency_list<vecS, vecS, bidirectionalS> BidirectionalGraph;
typedef adjacency_list<setS, vecS, bidirectionalS> UndirectedGraph;
// UndirectedGraph uses a set to avoid parallel edges
BidirectionalGraph bdg;
// use bdg
// create an undirected graph with the edges of the first one
typedef graph_traits<BidirectionalGraph>::vertex_iterator vi_beg, vi_end;
tie(vbeg, vend) = vertices(bdg);
UndirectedGraph ug(std::distance(vbeg, vend));
typedef graph_traits<BidirectionalGraph>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(bdg) ; ei != ei_end ; ++ei)
{
add_edge(source(*ei,bdg), target(*ei,bdg), ug);
}
不过,我想有巨大的图形处理时,该解决方案,可能引起一些性能问题。有可能是一个更好的方式来实现自己的目标,但我不是在BGL的专家,所以这就是我可以给你: - - !)
作为伯努瓦在评论指出,则BGL提供一个函数copy_graph
那份所有顶点和的曲线图到另一个的边缘。因此,上面的代码可以归结为这样:
#include <boost/graph/copy.hpp>
Bidirectional bdg;
// use bdg
// create an undirected graph with the vertices and edges of the first one
UndirectedGraph g;
copy_graph(bdg, g);
不隶属于 StackOverflow