当前位置：文江博客话题详情

如何将 BGL 有向图用作无向图（用于布局算法）？

发布于 2024-07-13 12:55:09 字数 190 浏览 6 评论 0原文

我正在使用 Boost.Graph 制作有向图（实际上是双向图）。我想使用现有的布局算法（Kamada-Kawai 或 Fruchterman-Reingold），但它们只接受无向图作为参数。

使用这些布局算法的最简单方法是什么？更一般地说，引诱算法认为有向图实际上是无向的正确方法是什么？

谢谢，伯努瓦

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

安穩 2024-07-20 12:55:09

您确定 Fruchterman-Reingold 算法只接受无向图吗？我尝试运行 Boost 文档< 中的小示例/a> 使用双向图而不是无向图，它编译并运行得很好。

为了回答你的问题，我不确定 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);

Are you sure that Fruchterman-Reingold algorithm only accepts undirected graphs? I tried to run the little example from the Boost documentation using a bidirectional graph instead of an undirected one, and it compiled and ran just fine.

To answer your question, I'm not sure there is any facilities built into the BGL to convert a directed graph to an undirected one. The only solution I found is creating a new graph and adding all the edges from the original one:

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);
}

However, I guess this solution might raise some performance issue when dealing with huge graphs. There may be a better way to achieve your goal, but I'm not an expert in BGL, so that's all I can give you :-)!

As Benoît pointed in a comment, the BGL provide a function copy_graph that copies all the vertices and edges of a graph into another one. Therefore, the code above can boil down to this:

#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);

回复收藏 0 原文

~没有更多了~