Como usar um grafo dirigido BGL como um não-direcionado (para uso no algoritmo de layout)?

Question

Eu estou trabalhando em um grafo direcionado (na verdade, um bidirecional) com Boost.Graph. Eu gostaria de usar os algoritmos de layout que existem (ou Kamada-Kawai ou Fruchterman-Reingold), mas eles só aceitam gráficos sem direção como parâmetros.

O que é a maneira mais simples de usar esses algoritmos de layout? De modo mais geral, qual é o caminho certo para atrair um algoritmo em pensar que um grafo direcionado é realmente não dirigida?

Obrigado, Benoît

Answer 1

Você tem certeza que o algoritmo Fruchterman-Reingold só aceita gráficos sem direção? Tentei executar o pequeno exemplo do documentação impulso usando um gráfico bidirecional em vez de um sem direção, e ele compilou e funcionou muito bem.

---

Para responder à sua pergunta, eu não estou certo que há quaisquer instalações construídas para o BGL para converter um gráfico dirigido a um já não direcionado. A única solução que eu encontrei é a criação de um novo gráfico e adicionando todas as bordas do original:

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

No entanto, eu acho que essa solução poderia levantar algum problema de desempenho ao lidar com grandes gráficos. Pode haver uma melhor maneira de atingir o seu objetivo, mas eu não sou um especialista em BGL, então isso é tudo que eu posso dar-lhe: -)

---

Como Benoit apontado em um comentário, o BGL proporcionar uma função copy_graph que copia todos os vértices e as bordas de um gráfico em outro. Portanto, o código acima pode se resumem a isso:

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