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

StackOverflow https://stackoverflow.com/questions/552854

  •  23-08-2019
  •  | 
  •  

Вопрос

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

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

Спасибо, Бенуа

Это было полезно?

Решение

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


Отвечая на ваш вопрос, я не уверен, что в 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);
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top