Re: [Boost-users] BGL : Undirected graph form a directed graph

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2006-02-14 07:33:28

boost-users-request_at_[hidden] wrote:

>
> Hello,
>
> I want to find the (weakly) connected components and the biconnected 
> components of a directed(bidirectional) graph.
> But these methods need a undirected graph as input. Does anyone know a 
> simple way to create a undirected graph from a directed graph or a 
> undirected view of a directed graph?
>
> Thanks a lot,
>
> Jean-Noël
>
>
> ------------------------------------------------------------------------
>
Hi,
Probably this could help

#include <boost/graph/copy.hpp>
boost::copy_graph()

if not  something like this should work

template <class TGraph1, class TGraph2> void    
directed2undirected(const TGraph1& directed_graph,    TGraph2&  
undirected_graph)
{
    typedef typename boost::graph_traits<TGraph1>::vertex_descriptor 
vertex1;
    typedef typename boost::graph_traits<TGraph2>::vertex_descriptor 
vertex2;
    typedef typename boost::graph_traits<TGraph1>::edge_iterator 
edge_iterator;

    std::vector<vertex1> orig_vertices;
    std::copy(vertices(directedt_graph).first, 
vertices(directed_graph).second, std::back_inserter(orig_vertices));
    std::map<vertex1, vertex2> vertex_map;
   
   // undirected = TGraph2(boost::num_vertices(directed_graph));
    for (std::size_t i = 0; i < num_vertices(directed_graph); ++i) {
        vertex_map[orig_vertices[i]] = boost::add_vertex(undirected_graph);
       ///Also would be good to copy properties, but it isn't necessary 
as far as I understand
    }

    for (edge_iterator e = edges(directed_graph).first; e != 
edges(directed_graph).second; ++e) {
        boost::add_edge(vertex_map[source(*e, directed_graph)], 
vertex_map[target(*e, directed_graph)], /*directed_graph[*e],*/ 
undirected_graph);
    }
}

I don't know if there is some way to do it without copying. If some, 
please let me know.
Regards,
--dmitry