作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在使用 Boost.Graph 处理有向图(实际上是双向图)。我想使用现有的布局算法(Kamada-Kawai 或 Fruchterman-Reingold),但它们只接受无向图作为参数。
使用这些布局算法的最简单方法是什么?更一般地说,引诱算法认为有向图实际上是无向图的正确方法是什么?
谢谢,贝努瓦
最佳答案
您确定 Fruchterman-Reingold 算法只接受无向图吗?我尝试运行 Boost documentation 中的小示例使用双向图而不是无向图,它编译并运行得很好。
为了回答您的问题,我不确定 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 方面的专家,所以我只能告诉您 :-)!
正如 Benoît 在评论中指出的那样,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);
关于c++ - 如何将 BGL 有向图用作无向图(用于布局算法)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/552854/
我是一名优秀的程序员,十分优秀!