How to use a BGL directed graph as an undirected one (for use in layout algorithm) ?

Question

Hi

I am working on a directed graph (actually a bidirectional one) with Boost.Graph. I'd like to use the layout algorithms that exist (either Kamada-Kawai or Fruchterman-Reingold) but they only accept undirected graphs as parameters.

What is the simplest way to use these layout algorithms ? More generally, what's the right way to lure an algorithm into thinking that a directed graph is actually undirected ?

Thanks, Benoît

Answer 1

Are you sure that Fruchterman-Reingold algorithm only accepts undirected graphs? I tried to run the little example from the Boost documentation using a bidirectional graph instead of an undirected one, and it compiled and ran just fine.

---

To answer your question, I'm not sure there is any facilities built into the BGL to convert a directed graph to an undirected one. The only solution I found is creating a new graph and adding all the edges from the original one:

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

However, I guess this solution might raise some performance issue when dealing with huge graphs. There may be a better way to achieve your goal, but I'm not an expert in BGL, so that's all I can give you :-)!

---

As Benoît pointed in a comment, the BGL provide a function copy_graph that copies all the vertices and edges of a graph into another one. Therefore, the code above can boil down to this:

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