Comment utiliser un graphe orienté BGL comme un non orienté (pour une utilisation dans l'algorithme de mise en page)?

Question

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

Quelle est la façon la plus simple d'utiliser ces algorithmes de mise en page? De manière plus générale, quelle est la bonne façon d'attirer un algorithme en pensant qu'un graphe orienté est en fait plus guidées?

Merci, Benoît

Answer 1

Êtes-vous sûr que l'algorithme Fruchterman-Reingold accepte uniquement les graphes non orientés? J'ai essayé de lancer le petit exemple de la documentation Boost l'aide d'un graphique bi-directionnel au lieu d'un non orienté, et il a compilé et a couru très bien.

---

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 est la création d'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 peut y avoir une meilleure façon d'atteindre votre objectif, mais je ne suis pas un expert en BGL, de sorte que c'est tout je peux vous donner: -)

---

Comme Benoît a souligné dans un commentaire, la BGL fournir une copy_graph fonction 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);