Como usar um grafo dirigido BGL como um não-direcionado (para uso no algoritmo de layout)?
-
23-08-2019 - |
Pergunta
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
Solução
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);