どのように（レイアウトアルゴリズムで使用するため）無向一つとしてBGL有向グラフを使用するには？

Question

私はBoost.Graphと有向グラフ（実際には双方向の1）に取り組んでいます。私は（カマダ、河合のいずれか又はFruchterman-Reingold）が存在するが、それらは唯一のパラメータとして無向グラフを受け入れるレイアウトアルゴリズムを使用したいと思います。

これらのレイアウトアルゴリズムを使用する最も簡単な方法は何ですか？ より一般的には、有向グラフが実際に無向であることを考えることにするアルゴリズムをおびき寄せるための正しい方法は何ですか？

おかげで、 ブノワ

Answer 1

あなたはFruchterman-Reingoldアルゴリズムのみ無向グラフを受け入れることを確認していますか？私はブーストのドキュメントから少し例を実行しようとしました双方向グラフの代わりに、無向1を使用して、それがコンパイルされ、うまく走っています。

<時間>

あなたの質問に答えるために、私は無向1に有向グラフを変換するために、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);