如何使用BGL向图作为一个无向一（用于布局算法使用）？ [英] How to use a BGL directed graph as an undirected one (for use in layout algorithm)?

问题描述

我的工作有向图（实际上是一个双向的）与Boost.Graph。我想使用的布局算法存在（镰田，河合或Fruchterman-莱因戈尔德），但他们只接受无向图作为参数。<​​/ P>

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

谢谢，
伯努瓦

解决方案

您确定Fruchterman-莱因戈尔德算法只接受无向图？我试图运行从 Boost文档的小例子使用双向曲线，而不是一个无向之一，它编译并运行就好了。

---

要回答你的问题，我不知道有内置的BGL到有向图转换为无方向之一的任何设施。我发现是创建一个新的图，并从原来的添加所有边缘的唯一解决方案：

 的typedef的adjacency_list＆LT;血管内皮细胞，血管内皮细胞，bidirectionalS＆GT;双向图BidirectionalGraph;
的typedef的adjacency_list＆LT;设置，血管内皮细胞，bidirectionalS＆GT; UndirectedGraph;
// UndirectedGraph使用一组，以避免平行边双向图BidirectionalGraph BDG;
//使用BDG//创建与第一个的边缘的无向图
typedef的graph_traits＆LT;＆双向图BidirectionalGraph GT; :: vertex_iterator vi_beg，vi_end;
领带（vbeg，鬻）=顶点（BDG）;UndirectedGraph UG（性病::距离（vbeg，鬻））;typedef的graph_traits＆LT;＆双向图BidirectionalGraph GT; :: edge_iterator EI，ei_end;为（并列（EI，ei_end）=边缘（BDG）; EI = ei_end;！++ EI）
{
    的add_edge（来源（* EI，BDG），目标（* EI，BDG），UG）;
}
 

不过，我想巨大图形处理时，该解决方案可能会引发一些性能问题。有可能是一个更好的方式来实现自己的目标，但我不是在BGL的专家，所以这就是我可以给你： - - ！）

---

作为伯努瓦在评论中指出，在BGL提供一个函数 copy_graph 那份所有顶点和图形到另一个边缘。因此，code以上可以归结为这样：

 的#include＆LT;升压/图/ copy.hpp＆GT;双向BDG;
//使用BDG//创建与第一个的顶点和边的无向图
UndirectedGraph克;
copy_graph（BD​​G，G）;
 

I am working on a directed graph (actually a bidirectional one) with Boost.Graph. I'd like to use the layout algorithms that exist (either Kamada-Kawai or Fruchterman-Reingold) but they only accept undirected graphs as parameters.

What is the simplest way to use these layout algorithms ? More generally, what's the right way to lure an algorithm into thinking that a directed graph is actually undirected ?

Thanks, Benoît

解决方案

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

这篇关于如何使用BGL向图作为一个无向一（用于布局算法使用）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！