Merging graphs using boost graph

Question

How do I add edge between two different graphs using Boost Graph Library. I have seen code for merging/contracting two vertices, but I do not want to do that. I want to link end vertex of one graph to the starting vertex of another graph and make it one single graph. Both the graphs are of same type.

Please Help...

I don't think there is a function that allows you to do that, I think you will have to merge them manually, but I'm no expert. In order to maximize your chances to get a good answer you should probably add the boost-graph tag. — llonesmiz

Michael Simbirsky Michael Simbirsky · Accepted Answer · 2013-10-14T10:00:22

First of all, we have to admit that the resulting graph is a SINGLE object. I assume you want it to be of the same type Graph as your original two graphs g1 and g2. It means you have a choice to do one of the following: Graph g = g1 + g2 or g1 += g2 (both choices are in pseudo-code, of course).

In any case, the result will contain a copy of the second graph, not the "original" object of the graph g2.

BGL actually provides you with a function to exactly do that, namely, the function "copy_graph"

You can do something like the following

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/copy.hpp>


typedef boost::adjacency_list<> Graph;
typedef Graph::vertex_descriptor vertex_t;

void merging(Graph & g1, vertex_t v_in_g1, const Graph & g2, vertex_t u_in_g2)
{
    typedef boost::property_map<Graph, boost::vertex_index_t>::type index_map_t;


    //for simple adjacency_list<> this type would be more efficient:
    typedef boost::iterator_property_map<typename std::vector<vertex_t>::iterator,
        index_map_t,vertex_t,vertex_t&> IsoMap;

    //for more generic graphs, one can try  //typedef std::map<vertex_t, vertex_t> IsoMap;
    IsoMap mapV;
    boost::copy_graph( g2, g1, boost::orig_to_copy(mapV) ); //means g1 += g2

    vertex_t u_in_g1 = mapV[u_in_g2]; 
    boost::add_edge(v_in_g1, u_in_g1, g1);
}

See also copy a graph (adjacency_list) to another one

Merging graphs using boost graph

1 Answers