views:

560

answers:

1

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

+2  A: 

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);
Luc Touraille
The documentation says it is not designed for this, but i guess i should have tried ! I am still interested in the answer though, because such a need will probably come back up
Benoît
Thanks. That's all i came up with as well. I just hoped there would be some kind of adapter for that. Anyway. I'll mark your answer as "accepted" as soon as you'll have used copy_graph :-)
Benoît
You're right, I totally missed this function! I edited my answer to include that.
Luc Touraille