Cómo utilizar un grafo dirigido BGL como uno no dirigido (para su uso en algoritmo de diseño)?

Question

Estoy trabajando en un grafo dirigido (en realidad un ser bidireccional) con Boost.Graph. Me gustaría utilizar los algoritmos de diseño que existen (ya sea Kamada-Kawai o Fruchterman-Reingold) pero sólo aceptan grafos no dirigidos como parámetros.

¿Cuál es la forma más sencilla de utilizar estos algoritmos de diseño? De manera más general, ¿cuál es la manera correcta para atraer a un algoritmo en el pensamiento de que un grafo dirigido es en realidad no dirigido?

Gracias, Benoît

Answer 1

¿Está seguro de que Fruchterman-Reingold algoritmo sólo acepta grafos no dirigidos? Traté de correr el pequeño ejemplo de la href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/fruchterman_reingold.html" rel="nofollow noreferrer"> documentación usando una gráfica bidireccional en lugar de uno no dirigido, y es compilado y funcionó muy bien.

---

Para responder a su pregunta, no estoy seguro de que hay las instalaciones integradas en el BGL para convertir un grafo dirigido a uno no dirigido. La única solución que encontré es la creación de un nuevo gráfico y la adición de todos los bordes de la de origen:

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

Sin embargo, creo que esta solución podría plantear algunos problemas de rendimiento cuando se trabaja con grandes gráficos. Puede haber una mejor manera de lograr su objetivo, pero no soy un experto en BGL, así que eso es todo lo que puedo dar: -!)

---

Como Benoît señaló en un comentario, el BGL proporcionar un copy_graph función que copia todos los vértices y los bordes de un gráfico en otro. Por lo tanto, el código anterior se reduce a esto:

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