BGL 지시 된 그래프를 방정 된 그래프로 사용하는 방법 (레이아웃 알고리즘에 사용)?

Question

나는 boost.graph와 함께 지시 된 그래프 (실제로 양방향 그래프)를 작업 중입니다. 존재하는 레이아웃 알고리즘 (Kamada-Kawai 또는 Fruchterman-Reingold)을 사용하고 싶지만 방향되지 않은 그래프 만 매개 변수로 만 허용합니다.

이 레이아웃 알고리즘을 사용하는 가장 간단한 방법은 무엇입니까? 보다 일반적으로, 지시 된 그래프가 실제로 방향이 없다고 생각하는 데 알고리즘을 유혹하는 올바른 방법은 무엇입니까?

감사합니다, Benoît

Answer 1

Fruchterman-Reingold 알고리즘은 방향이없는 그래프만을 수용한다고 확신합니까? 나는 작은 예제를 실행하려고했다 문서를 높이십시오 방향이없는 그래프 대신 양방향 그래프를 사용하여 컴파일하고 잘 실행되었습니다.

---

귀하의 질문에 답하기 위해, 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);