Как использовать ориентированный граф BGL как ненаправленный (для использования в алгоритме компоновки)? - PullRequest
Новая
       19

Как использовать ориентированный граф BGL как ненаправленный (для использования в алгоритме компоновки)?

3 голосов
/ 16 февраля 2009

Я работаю над ориентированным графом (фактически двунаправленным) с Boost.Graph. Я хотел бы использовать существующие алгоритмы компоновки (Камада-Каваи или Фрухтерман-Рейнгольд), но они принимают только неориентированные графы в качестве параметров.

Какой самый простой способ использовать эти алгоритмы компоновки? В более общем смысле, как правильно заставить алгоритм думать, что ориентированный граф на самом деле не является ненаправленным?

Спасибо, Benoît

1 Ответ

4 голосов
/ 16 февраля 2009

Вы уверены, что алгоритм Fruchterman-Reingold принимает только неориентированные графы? Я попытался запустить небольшой пример из документации Boost , используя двунаправленный граф вместо ненаправленного, и он скомпилировался и работал очень хорошо.

Чтобы ответить на ваш вопрос, я не уверен, что в 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);
...