Comment utiliser un graphe orienté BGL comme un graphe non orienté (à utiliser dans un algorithme de mise en page)?

Question

Je travaille sur un graphe orienté (en fait un graphe bidirectionnel) avec Boost.Graph. Je voudrais utiliser les algorithmes de mise en page qui existent (soit Kamada-Kawai ou Fruchterman-Reingold) mais ils n'acceptent que les graphes non orientés comme paramètres.

Quelle est la manière la plus simple d'utiliser ces algorithmes de mise en page? Plus généralement, quelle est la bonne façon d'attirer un algorithme en lui faisant croire qu'un graphe orienté est réellement non orienté?

Merci, Benoît

Answer 1

Etes-vous sûr que l'algorithme Fruchterman-Reingold accepte uniquement les graphes non orientés? J'ai essayé d'exécuter le petit exemple à partir du Boost documentation en utilisant un graphique bidirectionnel au lieu d'un graphique non orienté, et il a été compilé et exécuté correctement.

---

Pour répondre à votre question, je ne suis pas sûr qu'il ya des installations construites dans le BGL pour convertir un graphe orienté vers un un non orienté. La seule solution que je trouve crée un nouveau graphique et l'ajout de tous les bords de l'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); 
} 

Cependant, je pense que cette solution pourrait soulever des problèmes de performance lorsqu'ils traitent avec des graphiques énormes. Il y a peut-être un meilleur moyen d'atteindre ton objectif, mais je ne suis pas un expert en BGL, donc c'est tout ce que je peux te donner :-)!

---

Comme Benoît a souligné dans un commentaire, la BGL fournir une fonction copy_graph qui copie tous les sommets et arêtes d'un graphe dans l'autre. Par conséquent, le code ci-dessus peut se résumer à ceci:

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