boost - 使用提升图合并图

Question

如何使用 Boost Graph Library 在两个不同的图形之间添加边。我已经看到了合并/收缩两个顶点的代码，但我不想这样做。我想将一个图的结束顶点链接到另一个图的起始顶点并使其成为一个图。两张图属于同一类型。

请帮忙...

Answer 1

首先，我们必须承认结果图是一个 SINGLE 对象。我假设您希望它与原始的两个图 g1 和 g2 的类型相同。这意味着您可以选择执行以下操作之一：图形 g = g1 + g2 或 g1 += g2（当然，这两个选择都是伪代码）。

无论如何，结果将包含第二个图的副本，而不是图 g2 的“原始”对象。

BGL 实际上为您提供了一个函数来完全做到这一点，即函数“ copy_graph ”

您可以执行以下操作

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

另请参见将图 (adjacency_list) 复制到另一个